五、LinkedList 内部结构以及基本元素声明
- LinkedList内部结构是一个双向链表，具体示意图如下
每一个链表都是一个Node节点，由三个元素组成
private static class Node<E> { // Node节点的元素 E item; // 指向下一个元素 Node<E> next; // 指向上一个元素 Node<E> prev; // 节点构造函数 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
first 节点也是头节点， last节点也是尾节点
- LinkedList 中有三个元素，分别是
transient int size = 0; // 链表的容量 transient Node<E> first; // 指向第一个节点 transient Node<E> last; // 指向最后一个节点
- LinkedList 有两个构造函数，一个是空构造函数，不添加任何元素，一种是创建的时候就接收一个Collection集合。
/** * 空构造函数 */ public LinkedList() {} /** * 创建一个包含指定元素的构造函数 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
六、LinkedList 具体源码分析
前言: 此源码是作者根据上面的代码示例一步一步跟进去的，如果有哪些疑问或者讲的不正确的地方，请与作者联系。
添加
添加的具体流程示意图：
包括方法有：
- add(E e)
- add(int index, E element)
- addAll(CollectionE> c)
- addAll(int index, CollectionE> c)
- addFirst(E e)
- addLast(E e)
- offer(E e)
- offerFirst(E e)
- offerLast(E e)
下面对这些方法逐个分析其源码：
add(E e) ：
// 添加指定元素至list末尾 public boolean add(E e) { linkLast(e); return true; } // 真正添加节点的操作 void linkLast(E e) { final Node<E> l = last; // 生成一个Node节点 final Node<E> newNode = new Node<>(l, e, null); last = newNode; // 如果l = null，代表的是第一个节点，所以这个节点即是头节点 // 又是尾节点 if (l == null) first = newNode; else // 如果不是的话，那么就让该节点的next 指向新的节点 l.next = newNode; size++; modCount++; }
- 比如第一次添加的是111，此时链表中还没有节点，所以此时的尾节点last 为null, 生成新的节点，所以 此时的尾节点也就是111，所以这个 111 也是头节点，再进行扩容，修改次数对应增加
- 第二次添加的是 222， 此时链表中已经有了一个节点，新添加的节点会添加到尾部，刚刚添加的111 就当作头节点来使用，222被添加到111的节点后面。
add(int index,E e) :
/** *在指定位置插入指定的元素 */ public void add(int index, E element) { // 下标检查 checkPositionIndex(index); if (index == size) // 如果需要插入的位置和链表的长度相同，就在链表的最后添加 linkLast(element); else // 否则就链接在此位置的前面 linkBefore(element, node(index)); } // 越界检查 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } // 判断参数是否是有效位置(对于迭代或者添加操作来说) private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } // linkLast 上面已经介绍过 // 查找索引所在的节点 Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } // 在非空节点插入元素 void linkBefore(E e, Node<E> succ) { // assert succ != null; // succ 即是插入位置的节点 // 查找该位置处的前面一个节点 final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
- 例如在位置为1处添加值为123 的元素，首先对下标进行越界检查，判断这个位置是否等于链表的长度，如果与链表长度相同，就往最后插入，如果不同的话，就在索引的前面插入。
- 下标为1 处并不等于索引的长度，所以在索引前面插入，首先对查找 1 这个位置的节点是哪个，并获取这个节点的前面一个节点，在判断这个位置的前一个节点是否为null，如果是null，那么这个此处位置的元素就被当作头节点，如果不是的话，头节点的next 节点就指向123
addFirst(E e) :
// 在头节点插入元素 public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { // 先找到first 节点 final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) // f 为null，也就代表着没有头节点 last = newNode; else f.prev = newNode; size++; modCount++; }
例如要添加top 元素至链表的首部，需要先找到first节点，如果first节点为null，也就说明没有头节点，如果不为null，则头节点的prev节点是新插入的节点。
addLast(E e) :
/** * 在末尾处添加节点 */ public void addLast(E e) { linkLast(e); } // 链接末尾处的节点 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
方法逻辑与在头节点插入基本相同
addAll(Collections c) :
/** * 在链表中批量添加数据 */ public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { // 越界检查 checkPositionIndex(index); // 把集合转换为数组 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; // 直接在末尾添加，所以index = size if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } // 遍历每个数组 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; // 先对应生成节点，再进行节点的链接 Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
Collection<String> collec = Arrays.asList("123","213","321"); list.addAll(collec);
- 例如要插入一个Collection为123,213,321 的集合，没有指定插入元素的位置，默认是向链表的尾部进行链接，首先会进行数组越界检查，然后会把集合转换为数组，在判断数组的大小是否为0，为0返回，不为0，继续下面操作
- 因为是直接向链尾插入，所以index = size，然后遍历每个数组，首先生成对应的节点，在对节点进行链接，因为succ 是null，此时last 节点 = pred，这个时候的pred节点就是遍历数组完成后的最后一个节点
- 然后再扩容数组，增加修改次数
addAll(Collections c) : 这个方法的源码同上
offer也是对元素进行添加操作，源码和add方法相同
offerFirst(E e)和addFirst(E e) 源码相同
offerLast(E e)和addLast(E e) 源码相同)
push(E e) 和addFirst(E e) 源码相同
后记 : 笔者才疏学浅，如果有哪处错误产生误导，请及时与笔者联系更正，一起共建积极向上的it氛围
