LinkedList 实现原理

概述

LinkedList 是通过一个双向链表来实现的，它允许插入所有元素，包括 null，同时，它是线程不同步的。 1、 LinkedList 的底层结构是一个带头/尾指针的双向链表，可以快速的对头/尾节点进行操作。 2、相比数组，链表的特点就是在指定位置插入和删除元素的效率较高，但是查找的效率就不如数组那么高了

常用的方法

双向链表，头节点均指first，尾节点均指last

添加元素： add(E e)：将元素添加到表尾，返回布尔类型值 addFirst(E e)：添加新的头节点 addLast(E e)：添加新的尾节点 add(int index,E e)：在指定位置插入节点 push(E e)：将元素添加到头节点

获取元素： getFirst()：获取头节点 getLast()：获取尾部节点 node(int index)：获取指定下标的节点 get(int index)：获取指定下标的节点 peek()：返回头节点 element()：返回头节点

删除元素： remove(Object o）：删除指定节点，返回布尔类型值 remove(int index)：删除指定节点的下标，返回删除的值 removeFirst()：删除头节点，返回头节点的值 removeLast()：删除尾节点，返回尾节点的值 poll()：获取头节点，并删除头节点

替换元素： set(int index,E e)：将下标为index的节点替换为新的值，返回被替换的值

1.属性

//链表的节点个数 transient int size = 0; //指向头节点的指针 transient Node<E> first; //指向尾节点的指针 transient Node<E> last;

2.方法

1.节点结构 Node 是在 LinkedList 里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域 item，一个后置指针 next，一个前置指针 prev。

private static class Node{ E item;//节点内容 Node<E> next; Node<E> pre; //构造方法 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

2.添加元素 对于链表，添加元素的操作即在表头/表尾插入元素，又或者在指定位置插入元素。因为 LinkedList 有头指针和尾指针，所以在表头或表尾进行插入元素只需要 O(1) 的时间，而在指定位置插入元素则需要先遍历一下链表，所以复杂度为 O(n)。

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first指针指向的节点，当然还要修改 first 指针指向新的头节点。此外，原来的头节点变成了第二个节点，因此修改原来头节点的前驱指针，使它指向表头节点。

private void linkFirst(E e) { final Node<E> f = first; //当前节点的前驱指向 null，后继指针原来的头节点 final Node<E> newNode = new Node<>(null, e, f); //头指针指向新的头节点 first = newNode; //如果原来有头节点，则更新原来节点的前驱指针，否则更新尾指针 if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } //向表尾添加元素 void linkLast(E e) { final Node<E> l = last; //当前节点的前驱指向尾节点，后继指向 null final Node<E> newNode = new Node<>(l, e, null); //尾指针指向新的尾节点 last = newNode; //如果原来有尾节点，则更新原来节点的后继指针，否则更新头指针 if (l == null) first = newNode; else l.next=newNode; size++; modCount++; }

当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点

void linkBefore(E e, Node<E> succ) { // assert succ != null; //指定节点的前驱 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++; }

3.删除元素 需要把当前节点的前驱节点的后继修改为当前节点的后继，以及当前节点的后继结点的前驱修改为当前节点的前驱

//删除表头节点，并返回主体属性 private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; //头指针指向后一个节点 if (next == null) last = null;//当表头节点的next为null时，代表 last节点为null else next.prev = null; //新头节点的前驱为 null size--; modCount++; return element; } //删除表尾节点，并返回该元素 private E unLinkLast(Node<E> l) { //assert l=last&&l!=null final E element=l.item; final Node<E> prev=l.prev; l.item=null;//置空 便于GC l.prev=null;//GC last=prev;//尾指针指向前一个节点 if(prev==null)//代表first为null first=null; else prev.next=null; size--; modCount++; return element; } //删除指定节点，返回指定元素的值 //将指定元素的前驱节点的后继改为指定元素的后继节点，将指定元素的后继节点的前驱改为前驱节点 E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> pre=x.pre;//指定节点的前驱节点 final Node<E> next=x.next;//指定节点的后继节点 if(pre==null){ first=next; }else{ pre.next=next; x.pre=null; } if(next=null){ last=pre; }else{ next.pre=pre; x.next=null; } x.item=null; size--; modCount++; return element; }

4.获取元素

//获取表头元素 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } //获取表尾元素 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } //获取指定下标的元素 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; } }

5.常用方法 链表的删除和添加操作是private的，常用方法对其进行调用

//删除表头元素 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } //删除表尾元素 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unLinkLast(l); } //插入新的表头节点 public void addFirst(E e) { linkFirst(e); } //插入新的表尾节点 public void addLast(E e) { linkLast(e); } //链表的大小 public int size() { return size; } //添加元素到表尾 public boolean add(E e) { linkLast(e); return true; } //删除指定元素 public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //获取指定下标的元素 public E get(int index) { checkElementIndex(index); //先检查是否越界 return node(index).item; } //替换指定下标的值 public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } //在指定位置插入节点 public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } //删除指定下标的节点 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } //获取表头节点的值，表头为空返回 null public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } //获取表头节点的值，表头为空抛出异常 public E element() { return getFirst(); } //获取表头节点的值，并删除表头节点，表头为空返回 null public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //添加元素到表头 public void push(E e) { addFirst(e); } //删除表头元素 public E pop() { return removeFirst(); }