前言

LinkedList，常用的集合之一，基于链表实现，因此元素的插入、删除十分方便。但是元素的查找性能较差。在阅读LinkedList源码之前先简单地实现链表数据结构，有助于理解源码。

链表实现

接口定义

package com.xsn.container;public interface Linked<T> {T addFirst(T t);T addLast(T t);T add(T t, int index);T removeFirst();T removeLast();T remove(T t);boolean contain(T t);boolean isEmpty();int getSize();
}

定义链表接口，常用方法：头插入、尾插入、指定位置插入、头移除元素、尾移除元素、移除指定值元素、判断是否存在指定值元素、判断是否为空、获取链表长度

实现类

@Data
public class SingleLinked<T> implements Linked<T> {private int size;private Node<T> head;public SingleLinked() {size = 0;head = null;}private class Node<T> {Node<T> next;T data;Node(Node next, T data) {this.next = next;this.data = data;}Node(T data) {this(null, data);}@Overridepublic String toString() {return data + "----->" + next;}}@Overridepublic String toString() {return head.toString();}
}

链表有两个属性;
size：长度
head：头结点
维护节点内部类Node，同样两个属性
Node next：下一个节点
T data：储存元素

头插入

	public T addFirst(T t) {head = new Node(head, t);++ size;return t;}

new一个新节点作为头结点（将next指向之前的头结点），链表长度递增

指定位置插入

	public T add(T t, int index) {if (index < 0 || index > size) {throw new RuntimeException("error index");}if (index == 0) {return addFirst(t);}Node node = new Node(t);Node pre = head;for (int i = 0; i < index - 1; i++) {pre = pre.next;}node.next = pre.next;pre.next = node;++ size;return t;}

校验位置是否合法
当位置为0，即插入头元素
当位置不为0时，我们从头元素开始，找到要插入的位置index，将新节点的next指向原index节点的next，再将index - 1节点的next指向新节点，长度递增

尾插入

	public T addLast(T t) {add(t, size);return t;}

即在index = size处插入

移除头元素

	public T removeFirst() {if (head == null) {throw new RuntimeException("already empty");}T t = head.data;head = head.next;-- size;return t;}

将头元素指向头元素的next，长度 - 1

移除尾元素

	public T removeLast() {if (head == null) {throw new RuntimeException("already empty");}Node node = head;Node<T> next = head;while (next.next != null) {node = next;next = next.next;}T t = next.data;node.next = null;-- size;return t;}

从头节点向后找，当node的next的next为空时，则说明next是尾结点，将node的next置为null，长度 - 1

移除指定值元素

	public T remove(T t) {if (head == null) {throw new RuntimeException("already empty");}if (t.equals(head.data)) {return removeFirst();}Node pre = head;Node node = head;while (node != null && !t.equals(node.data)) {pre = node;node = pre.next;}if (node != null) {pre.next = node.next;-- size;return t;}throw new RuntimeException("no such element " + t);}

当值与头元素值相等时，即移除头元素
从头元素向后找，找到对应值元素则将前一元素的next指向该元素的next，长度 - 1，否则认为没找到

是否包含指定元素

	public boolean contain(T t) {Node node = head;while (node != null && !t.equals(node.data)) {node = node.next;}return node != null;}

从头元素开始找，找到最后节点（next == null）即不包含，否则为true

是否为空

	public boolean isEmpty() {return size == 0;}

LinkedList

实现一遍链表后再看LinkedList的源码

	transient int size = 0;transient Node<E> first;// 多一个属性last记录尾元素transient Node<E> last;

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;}}

LinkedList的Node节点多一个prev属性，用来指向前置节点

add()

	public boolean add(E e) {// 插入到最后linkLast(e);return true;}void linkLast(E e) {final Node<E> l = last;// 新节点prev指向last，next指向nullfinal Node<E> newNode = new Node<>(l, e, null);// 尾节点指向新节点last = newNode;if (l == null)// 原尾节点为null，即第一次插入，则头结点也为新节点first = newNode;else// 否则原尾节点的next指向新节点l.next = newNode;// 长度增加size++;modCount++;}

add(int index, E element)

	public void add(int index, E element) {// index校验checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}// 返回index处的Node节点，距离哪边近就从哪边遍历取出Node<E> node(int 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) {final Node<E> pred = succ.prev;// 新节点的prev指向index处节点的prev，next指向index处节点，即插在了index节点之前，index节点的prev指向index，如果index节点的prev为null，即index为头结点，则此时新节点为头结点，否则index节点的prev节点的next指向新节点。长度累加final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}

addAll(int index, Collection<? extends E> c)

	public boolean addAll(int index, Collection<? extends E> c) {// index校验checkPositionIndex(index);// 插入集合转为数组Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;// 确定插入的前后节点，当index == size时，插入尾部，则前节点指向last，后节点指向null。否则，后节点指向index处节点，前节点指向index处节点的prevNode<E> pred, succ;if (index == size) {succ = null;pred = last;} else {succ = node(index);pred = succ.prev;}// 遍历数组插入新节点for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;// 新节点的prev指向前节点Node<E> newNode = new Node<>(pred, e, null);// 如果前节点 == null，则该新节点为头结点。否则前节点的next指向新节点if (pred == null)first = newNode;elsepred.next = newNode;// 前节点指向新节点，插入下一个节点pred = newNode;}// 后节点 == null，则尾结点指向最后插入的节点。否则，最后插入节点的next指向尾结点，尾结点的prev指向最后插入的元素if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}// 计算长度size += numNew;modCount++;return true;}

addAll(Collection<? extends E> c)

	// 即向对位插入集合public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}

addFirst(E e)

	public void addFirst(E e) {linkFirst(e);}private void linkFirst(E e) {final Node<E> f = first;// 新节点的prev指向null，next指向头节点final Node<E> newNode = new Node<>(null, e, f);// 头结点指向新节点first = newNode;// 原头节点为null，即第一次插入，则尾节点也指向新节点。否则，原头节点的prev指向新节点if (f == null)last = newNode;elsef.prev = newNode;// 计算长度size++;modCount++;}

addLast(E e)

同add(E e)，只是没有返回元素

clear()

	// 从头节点开始，依次将节点的各属性置空，最后将链表属性置空，长度清0public void clear() {for (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null;size = 0;modCount++;}

contains(Object o)

	public boolean contains(Object o) {return indexOf(o) != -1;}// 相比于我们的实现，该方法支持查询是否包含nullpublic int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}

LinkedList同样实现了Deque接口，对于其中的方法我们不再解读。链表的实现大致思路一样，实现细节可能有所不同，同样也可以对属性进行相应的拓展（如源码中维护的尾节点，prev指针等）