ArrayList LinkedList源码解析(6)

接着我们看下LinkedList,LinkedList是基于双向链表的方式来实现的,双向链表就是集合中的每个元素都知道其前面的一个元素的位置和它后的一个元素位置。

在LinkedList中,使用一个内部类Entry来表示集合中的节点,元素的值赋值给element属性,节点的next属性指向下一个节点,节点的previous属性指向前一个节点。

private static class Entry<E> {
    //element存放数据
    E element;
    //next属性指向当前节点的下一个节点
    Entry<E> next;
  //previous属性指向当前节点的上一个节点
    Entry<E> previous;

Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

/**
*维护了一个header节点,header节点的element属性为null,previouse属性为null,next属性为null,并且header节点是不存储数据的
*/
private transient Entry<E> header = new Entry<E>(null, null, null);
//size表示集合包含的元素个数
private transient int size = 0;

/**
* 构造一个空的集合,将header节点的next属性、previous属性都指向header节点,这样形成了一个双向链表的闭环
*/
public LinkedList() {
    header.next = header.previous = header;
}

新增操作

/**
*追加指定的元素e到集合尾部,其效果和方法 addLast(E e)是一致的,都是调用addBefore(e,header)方法。
*/
public boolean add(E e) {
    addBefore(e, header);
    return true;
}

/**
*将数据e 插入到元素entry前面(private级别,LinkedList内部调用,意味着不能直接在自己的应用程序中调用此方法,但是可以利用反射API来间接的调用(好想没必要这样做))
*/
private Entry<E> addBefore(E e, Entry<E> entry) {
    //创建一个新节点newEntry,newEntry.element属性设置为e,newEntry.next属性设置为entry,newEntry.previous属性设置为entry.previous
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    ///将newEntry.previous节点的next属性指向newEntry本身
    newEntry.previous.next = newEntry;
    //将newEntry.next节点的previous属性指向newEntry本身
    newEntry.next.previous = newEntry;
    //将集合大小size + 1
    size++;
    //集合大小影响次数modCount + 1
    modCount++;
  //返回新创建的节点
    return newEntry;
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/a28bd8cda7fd42444934c8d7ef084553.html