资讯专栏INFORMATION COLUMN

LinkedList源码解析(二)

Ashin / 1910人阅读

摘要:返回结合中存储的节点数量向集合末尾添加一个元素移除一个元素如果是从第一个节点指针指向的节点开始循环比较节点的值,的内存地址取消节点操作成功如果是不是从第一个节点指针指向的节点开始循环调用的方法和节点的值作比较取消节点操作成功操作失败向集合末

size()返回结合中存储的节点数量

public int size() {
        return size;
    }

add(E e)向集合末尾添加一个元素

 public boolean add(E e) {
        linkLast(e);
        return true;
    }

remove(Object o)移除一个元素

public boolean remove(Object o) {
        if (o == null) {//如果o是null
            for (Node x = first; x != null; x = x.next) {//从第一个节点指针指向的节点开始循环
                if (x.item == null) {//比较节点的值,的内存地址
                    unlink(x);//取消节点
                    return true;//操作成功
                }
            }
        } else {//如果o是不是null
            for (Node x = first; x != null; x = x.next) {//从第一个节点指针指向的节点开始循环
                if (o.equals(x.item)) {//调用o的equals方法和节点的值作比较
                    unlink(x);//取消节点
                    return true;//操作成功
                }
            }
        }
        return false;//操作失败
    }

addAll(Collection c)向集合末尾加入集合c

public boolean addAll(Collection c) {
        return addAll(size, c);
    }

clear()清空集合

 public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node x = first; x != null; ) {//从first指针指向的节点开始循环
            Node next = x.next;//获取x的next
            x.item = null;//x的值置空
            x.next = null;//x的next置空
            x.prev = null;//x的prev置空
            x = next;//x赋值为next下一次循环使用
        }
        first = last = null;//第一个节点指针和最后一个节点的指针置空
        size = 0;//数据长度0
        modCount++;//操作数不清空
    }

get(int index)获取index索引节点数据

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

set(int index, E element)设置index索引处的节点位数为element

public E set(int index, E element) {
        checkElementIndex(index);//index在范围内
        Node x = node(index);//获取索引处的节点
        E oldVal = x.item;//获取节点旧的值
        x.item = element;//给节点的值赋值新值
        return oldVal;//返回旧的值
    }

add(int index, E element)根据索引插入数据

 public void add(int index, E element) {
        checkPositionIndex(index);//index在范围内

        if (index == size)/、如果索引位index等于数据长度
            linkLast(element);//尾插入
        else
            linkBefore(element, node(index));//否则插入在index索引对应节点之前
    }

remove(int index)移除索引index处的数据

 public E remove(int index) {
        checkElementIndex(index);//index在范围内
        return unlink(node(index));
    }

isElementIndex(int index)判断参数是否是现有元素的索引

  private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

isPositionIndex(int index)判断参数是否是现有元素的索引(迭代器或添加操作)

  private boolean isPositionIndex(int index) {
        return index >= 0 && index < size;
    }

构造一个IndexOutOfBoundsException详细消息

 private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

lastIndexOf(Object o)返回指定元素最后一次出现的索引

 public int lastIndexOf(Object o) {
        int index = size;//初始下标赋值
        if (o == null) {//o为null
            for (Node x = last; x != null; x = x.prev) {//last指针指向的节点开始向前循环
                index--;
                if (x.item == null)//节点的值作内存比较
                    return index;//返回下标
            }
        } else {//o不为null
            for (Node x = last; x != null; x = x.prev) {//last指针指向的节点开始向前循环
                index--;
                if (o.equals(x.item))//调用o的equals方法和节点的值比较
                    return index;
            }
        }
        return -1;
    }

peek()索但不删除此列表的头部(null返回null)

 public E peek() {
        final Node f = first;
        return (f == null) ? null : f.item;//如果是null的话不返回对象,返回null
    }

element()检索但不删除此列表的头部(null会抛出异常)

public E element() {
        return getFirst();
    }

getFirst()返回此列表中的第一个元素(null会抛出异常)

public E getFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

poll()检索并删除此列表的头部(null返回null)

 public E poll() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f);//不为null时候,删除并返回第一个节点
    }

remove()检索并删除此列表的头部

  public E remove() {
        return removeFirst();
    }

offer(E e)将指定的元素添加为此列表的尾部

public boolean offer(E e) {
        return add(e);
    }

offerFirst(E e)在指定列表第一个节点前面插入e

 public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

offerLast(E e)在指定列表最后一个节点后面插入e

  public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

peekFirst()检索但不删除此列表的第一个节点(null返回null)

 public E peekFirst() {
        final Node f = first;
        return (f == null) ? null : f.item;
     }

peekFirst()检索但不删除此列表的最后一个节点(null返回null)

 public E peekLast() {
        final Node l = last;
        return (l == null) ? null : l.item;
    }

pollFirst()检索并删除此列表的第一个节点(null返回null)

public E pollFirst() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

pollLast()检索并删除此列表的第最后一个节点(null返回null)

 public E pollLast() {
        final Node l = last;
        return (l == null) ? null : unlinkLast(l);
    }

push(E e)将元素插入到第一个节点签名

public void push(E e) {
        addFirst(e);
    }

pop()移除第一个节点

  public E pop() {
        return removeFirst();
    }

removeFirstOccurrence(Object o)删除此中第一次出现的指定元素

public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

removeLastOccurrence(Object o)删除此中最后一次出现的指定元素

//和lastIndexOf类似,找到后直接调用unlink
 public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

ListIterator listIterator(int index)返回集合迭代器

 public ListIterator listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
迭代器类ListItr
  private class ListItr implements ListIterator {
        private Node lastReturned;//最后返回的节点
        private Node next;//下一个节点
        private int nextIndex;//下一个节点的索引
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);//构造下一个节点的索引
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;//判断是否有下一个节点
        }

        public E next() {
            checkForComodification();//线程安全
            if (!hasNext())
                throw new NoSuchElementException();//迭代器到尾部

            lastReturned = next;//迭代器越过next
            next = next.next;//next赋值为next的下一个节点
            nextIndex++;//下一个节点的索引+1
            return lastReturned.item;//返回迭代器越过节点的值
        }

        public boolean hasPrevious() {
            return nextIndex > 0;//是否有前一个节点
        }

        public E previous() {
            checkForComodification();//线程安全
            if (!hasPrevious())
                throw new NoSuchElementException();//迭代器到达头部

            lastReturned = next = (next == null) ? last : next.prev;//如果是空返回last指针指向的节点(不理解)
            nextIndex--;//下一个节点索引自减
            return lastReturned.item;//返回迭代器越过节点的值
        }

        public int nextIndex() {
            return nextIndex;//返回下一个索引
        }

        public int previousIndex() {
            return nextIndex - 1;//返回上一个索引
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)//迭代器没有越过任何元素
                throw new IllegalStateException();

            Node lastNext = lastReturned.next;//获取迭代器越过节点的下一个节点
            unlink(lastReturned);//移除越过的元素
            if (next == lastReturned)//不理解为什么会进去
                next = lastNext;
            else
                nextIndex--;//下一个节点索引自减
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)//迭代器没有越过任何元素
                throw new IllegalStateException();
            checkForComodification();//线程安全
            lastReturned.item = e;//迭代器越过节点的值
        }

        public void add(E e) {
            checkForComodification();//线程安全
            lastReturned = null;
            if (next == null)//尾巴插入
                linkLast(e);
            else
                linkBefore(e, next);//next节点前插入
            nextIndex++;//下一个节点的索引加1
            expectedModCount++;
        }

        public void forEachRemaining(Consumer action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {//下一个节点的索引小于节点数
                action.accept(next.item);//运行accept方法
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();//线程安全
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

descendingIterator()适配器通过ListItr.previous提供降序迭代器

 public Iterator descendingIterator() {
        return new DescendingIterator();
    }
降序迭代器DescendingIterato(调用的就是ListItr,反着调用)
 private class DescendingIterator implements Iterator {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }

superClone()超类复制

@SuppressWarnings("unchecked")
private LinkedList superClone() {
        try {
            return (LinkedList) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

clone()复制集合对象

 public Object clone() {
        LinkedList clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;//第一个节点和最后一个节点置空
        clone.size = 0;//数据数置0
        clone.modCount = 0;//操作数置0

        // Initialize clone with our elements
        for (Node x = first; x != null; x = x.next)//从first节点开始循环初始化clone对象
            clone.add(x.item);

        return clone;
    }

toArray()返回集合元素组成的数组

  public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

toArray(T[] a)返回集合元素组成的数组(传入数组的类型)

 @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);//创建数组
        int i = 0;
        Object[] result = a;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/74936.html

相关文章

  • LinkedList 基本示例及源码解析

    摘要:对于不可修改的列表来说,程序员需要实现列表迭代器的和方法介绍这个接口也是继承类层次的核心接口,以求最大限度的减少实现此接口的工作量,由顺序访问数据存储例如链接链表支持。 一、JavaDoc 简介 LinkedList双向链表,实现了List的 双向队列接口,实现了所有list可选择性操作,允许存储任何元素(包括null值) 所有的操作都可以表现为双向性的,遍历的时候会从首部到尾部进行...

    senntyou 评论0 收藏0
  • List集合就这么简单【源码剖析】

    摘要:线程不安全底层数据结构是链表。的默认初始化容量是,每次扩容时候增加原先容量的一半,也就是变为原来的倍删除元素时不会减少容量,若希望减少容量则调用它不是线程安全的。 前言 声明,本文用得是jdk1.8 前一篇已经讲了Collection的总览:Collection总览,介绍了一些基础知识。 现在这篇主要讲List集合的三个子类: ArrayList 底层数据结构是数组。线程不安全 ...

    cpupro 评论0 收藏0
  • LinkedList源码解析

    摘要:我们来看相关源码我们看到封装的和操作其实就是对头结点的操作。迭代器通过指针,能指向下一个节点,无需做额外的遍历,速度非常快。不同的遍历性能差距极大,推荐使用迭代器进行遍历。LinkedList类介绍 上一篇文章我们介绍了JDK中ArrayList的实现,ArrayList底层结构是一个Object[]数组,通过拷贝,复制等一系列封装的操作,将数组封装为一个几乎是无限的容器。今天我们来介绍JD...

    roundstones 评论0 收藏0
  • Java集合之LinkedList源码解析

    摘要:快速失败在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改增加删除修改,则会抛出。原理由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发。 原文地址 LinkedList 在Java.util包下 继承自AbstractSequentialList 实现 List 接口,能对它进行队列操作。 实现 Deque ...

    DC_er 评论0 收藏0
  • java源码

    摘要:集合源码解析回归基础,集合源码解析系列,持续更新和源码分析与是两个常用的操作字符串的类。这里我们从源码看下不同状态都是怎么处理的。 Java 集合深入理解:ArrayList 回归基础,Java 集合深入理解系列,持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMi...

    Freeman 评论0 收藏0

发表评论

0条评论

Ashin

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<