一下分析皆以jdk1.8为准。

继承结构

首先我们来看一下LinkedList的继承结构类图：

可以看出LinkedList实现了List，Cloneable，Serializable，Deque接口。LinkedList是collections集合中功能最丰富的一个类，它不仅仅是一个List，还是一个队列，还是一个双向队列，还可以当栈来使用。LInkedlist是链表结构，内部通过一个一个相互链接的节点Node来存储数据，每个节点都有一个对与上一个节点和下一个节点的引用。所以对于频繁的插入删除操作比较方便（只要调整上下节点的引用），对于遍历，搜索查询效率比较低（需要从第一个节点一个个遍历）。

我们来看看LinkedList的基本数据成员。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; /** * Pointer to first node. //第一个节点引用 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. //最后一个节点引用 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; ...... }

LinkedList采用节点Node来存储实际数据，Node的结构非常简单

private static class Node { E item; Node next; //下一个节点 Node prev; //上一个节点 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }

无参构造函数

//创建一个空的linkedList，first和last都为null public LinkedList() { }

有参构造函数LinkedList(Collection<?extends E> c)

public LinkedList(Collection<? extends E> c) { this(); addAll(size,c); } // index参数指定collection中插入的第一个元素的位置 public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //检查索引范围是否合法：是否在0到size之间 Object[] a = c.toArray(); //将c转换为对象数组 int numNew = a.length; if (numNew == 0) return false; Node pred, succ; //succ为插入位置处的节点，pred为插入位置的前一个节点 if (index == size) { //从末尾插入，构造函数传入index=size=0; succ = null; pred = last; } else { //从中间插入 succ = node(index); pred = succ.prev; } //双向链表插入 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { //从末尾插入，将当前链表的最后一个节点赋值给last last = pred; } else { //从中间插入，将断开的部分重新链接上。 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }

从末尾添加元素add(E e)

public boolean add(E e) { linkLast(e); return true; } //从list末尾添加元素e void linkLast(E e) { final Node l = last; //将原来的末尾节点赋值给l final Node newNode = new Node<>(l, e, null);构造新节点，新节点的前置为原先的last last = newNode; //新节点设置为末尾节点 if (l == null) //list为空 first = newNode; else l.next = newNode; size++; modCount++; }

在指定位置添加节点add(int index,E element)

public void add(int index, E element) { checkPositionIndex(index); //检查索引范围是否在0到size之间 if (index == size) //从末尾添加 linkLast(element); else //从中间位置添加 linkBefore(element, node(index)); } void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { //如果index小于size的一半，从前往后遍历 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index大于等于size的一般，从后往前遍历。不需要从头到尾遍历一遍，提高效率 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 其余的一些添加，删除也是对于链表的操作，改变节点的前后引用。

LinkedList基于双向线性链表，内部表示就是一个一个相互链接的节点Node。而且它不像ArrayList,arraylist内部用数组来存储数据，还有扩容的问题。linkedList没有需要扩容，需要一个节点一个节点的链接下去。当然linkedList消耗的内存比ArrayList大一些。