LinkedList 数据结构是双向链表，插入删除比较方便。
LinkedList 是线程不安全的，允许元素为null 。
构造函数：
构造函数是空的。
/**
* Constructs an empty list.
*/
public LinkedList() {
}
基本属性：
//transient表示不会被序列化
//集合元素数量
transient int size = 0;
//链表头节点
transient Node<E> first;
//链表尾节点
transient Node<E> last;
链表节点： Node<E>
链表节点通过内部类Node<E>表示，这是一个双向链表。
既可以从头开始遍历，也可以从尾开始遍历。
next是上一个节点，prev是下一个节点。
private static class Node<E> {
//链表存储的元素
E item;
//next表示下一个节点
Node<E> next;
//prev表示上一个节点
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
添加元素： add()
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
调用 linkLast()方法。在链表末尾添加新节点。
/**
* Links e as last element.
*/
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++;
}
查询链表： get(index)
使用get(int index)。如下：
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//检查下标，如果越界就抛异常
checkElementIndex(index);
//遍历双向链表返回结果
return node(index).item;
} private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} /**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
遍历链表： node(index)
在用get(index)查询元素时调用了node(index)方法来遍历。
如果下标小于链表长度的一半，就从头遍历。反之就从尾遍历。这样查找的效率比较高。
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// size右移1位，表示size的一半。
//如果下标小于链表长度的一半，就从头开始遍历。
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;
}
}
参考博客 ：