LinkedList和ArrayList都实现了List接口。因此有List的特性,同时LinkedList也实现了Deque,因此它也具备双端队列和栈的特性。java
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
//实际元素个数 transient int size = 0; //头结点 transient Node<E> first; //尾结点 transient Node<E> last;
transient表示该域不能被序列化。first,last初始值都是null.node
这里有一个内部类Node:数据结构
private static class Node<E> { //数据 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; } }
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
LinkedList内部的数据结构是一个双向链表,因此不会有ArrayList那样的指定容量构造器。函数
public boolean add(E e) { linkLast(e); return true; }
void linkLast(E e) { //final类型的l节点保存尾结点last final Node<E> l = last; //建立一个新的节点newNode,其前驱为l,后继为null final Node<E> newNode = new Node<>(l, e, null); //将尾结点赋值为新建立的节点。 last = newNode; //尾结点为空,第一次添加 if (l == null) //新建节点为头结点 first = newNode; else //不然之前的尾结点的后继指向新节点 l.next = newNode; //集合大小加1 size++; //结构性变化加一,目的和ArrayList同样,检查迭代过程当中结构变化。 modCount++; }
add()方法会将新添加的元素添加到链表的尾端。性能
让咱们经过debug看看LinkedList添加元素过程,其结构的变化。
测试代码:测试
public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(1); linkedList.add(2); linkedList.add(3); }
第一次添加后结构为:this
第二次添加后结构为:debug
第三次添加后结构为:code
public E remove(int index) { //检查是否越界 checkElementIndex(index); return unlink(node(index)); }
先经过node方法获取index处的节点:blog
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); //size >> 1 等于 size/2 if (index < (size >> 1)) { //index在前半部分,从头开始找 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //index在后半部分,从尾开始找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
而后再经过E unlink(Node
/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; //x节点的元素 final E element = x.item; //后继 final Node<E> next = x.next; //前驱 final Node<E> prev = x.prev; //x前驱为空,删除的节点是头节点 if (prev == null) { first = next; } else { //x前驱节点的后继节点变为x的后继节点 prev.next = next; //切断前驱链接 x.prev = null; } //x后继为空,删除的节点为尾结点 if (next == null) { last = prev; } else { //x后继节点的前驱变为x的前驱节点 next.prev = prev; //切断后继链接 x.next = null; } //删除节点元素置空 x.item = null; size--; modCount++; return element; }
public E get(int index) { //检查索引 checkElementIndex(index); return node(index).item; }
/** * Returns the (non-null) Node at the specified element index. */ 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; } }
经过node(int index)查找index对应的节点,而后返回对应的数据item。其中size >> 1这个是指size右移一位即size/2 。
Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x;
Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x;
LinkedList 是不能随机访问的,按照索引访问效率较低,时间复杂度为复杂度为 O(N/2) 所以,LinkedList 删除一个节点的时间复杂度为 O(N) ,效率很高。