定义
LinkedList是一个双向链表类型的集合。
所谓双向链表就是链表上的元素都有上一个，下一个
源码分析
通过源码查看LinkedList是如何实现双向循环列表的。
- LinkedList的全局变量
//总个数
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的静态内部类，也就是实际存放元素的类。LinkedList链表上的每个元素 都是一个Node<E>
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;
}
}
- add（E e） 方法，在链表最后加入一个元素。
ArrayList 的添加方法扩容为关键点，LinkedList的添加方法则是链表前后的关联为关键点
/**
* 调用添加方法后，直接会调用 linkLast 方法。
* 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;
}
/**
* 在链表的尾部添加一个元素
* Links e as last element.
*/
void linkLast(E e) {
//第一次添加时，最后的元素为空。last 为 null
//第n次添加时 last 已经有值了。（n>1）
final Node<E> l = last;
// Node 的构造器，传参为，上一个元素，该元素，和下一个元素，
//因为是向尾部添加，所以上一个元素为最后一个元素，下一个元素为空。
//第一次添加时，上一个和下一个都为空
//第n次添加时，上一个元素已经有值，下一个依然为空
final Node<E> newNode = new Node<>(l, e, null);
//创建完毕后，newNode成为了新的最后一个元素。
last = newNode;
//一般情况下，只有第一次添加，l才为null
//所以如果l==null则第一次添加，所以first = newNode .
//第一次添加成功后，last 为新加的元素，first也为新加的元素。
if (l == null)
first = newNode;
else
//第一次添加不会进入该判断。
//第n次添加时，把原来的最后一个元素的下一个元素赋为新的最后一个
l.next = newNode;
size++;
modCount++;
}
//可以这么说，在顺序添加的时候。只有当ArrayList此次添加正好到了扩容，否则还是ArrayList的添加效率要高于LinkedList的
//因为ArrayList的添加只是在创建好的数组中添加一个元素。而LinkedList还要new好几个对象。
//不过综合来说 LinkedList添加方法不会太慢。而ArrayList添加是有可能慢的
- addFirst(E e) 和 addLast(E e) 也都是相当快的，下边贴源码。可以发现是和add（E e）差不多的。都是要维护链表的前后关系。
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
//在上边已经有了。
linkLast(e);
}
/**
* 可以看到添加第一个元素和添加最后一个元素差不多，只是改变了下维护链表前后的关系
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
- get(int i) 方法，通过索引获取元素。
通过这个方法的源码可以看出，关于通过所以获取元素，LinkedList与ArrayList的差距还是比较大的
public E get(int index) {
//判断是否下标越界
checkElementIndex(index);
return node(index).item;
}
/**
* 获取该索引的Node
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//在看ArrayList扩容的时候就看到了位运算 ，右移一位就是 /2
//该判断就是看看该索引位置是在前半部分还是在后半部分，
//如果前半部分就从前往后找，后半部分就从后往前找
if (index < (size >> 1)) {
//把 x设置为第一个
Node<E> x = first;
for (int i = 0; i < index; i++)
//index 为多少，就从第一个下一个多少次。
x = x.next;
return x;
} else {
//同理，从最后往前找。
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//所以 ，从源码中可以看出，ArrayList是用数组的下标来获取的。
//而LinkedList是从第一个或最后一个通过链表一个一个找的。所以ArrayList的get方法吊打LinkedList的get方法。
- add(int index, E element)在指定的位置添加元素
/**
* 在指定位置添加元素
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
//如果正好指定位置是最后，那省事了。
if (index == size)
linkLast(element);
else
//这就很麻烦了。 可以看到node(index) 这个方法 正是get(int index)主要方法
//在指定位置添加元素，慢就慢在这个方法，LinkedList的寻址是很慢的。
linkBefore(element, node(index));
}
/**
* 在找到node(index)这个元素后 ，就很简单了。依然是维护好链表的前后关系
* Inserts element e before non-null Node succ.
*/
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++;
}
- set(int index, E element) 修改指定位置的元素，这个方法其实主要的方法也是node(index)
/**
* Replaces the element at the specified position in this list with the
* specified element.
* 寻址找到后，前后关系都不用变，直接改下item就行
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
- remove(int index) 按照索引删除。
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//检查索引是否越界，合法
checkElementIndex(index);
//删除该元素（还是用到node(index)方法了）
return unlink(node(index));
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
//element 做为返回值用
final E element = x.item;
//该元素的下一个元素
final Node<E> next = x.next;
//该元素的上一个元素
final Node<E> prev = x.prev;
//如果进入该判断，则该元素就是第一个元素，
//删除后，就把该元素的下一个元素赋值为第一个元素
if (prev == null) {
first = next;
} else {
//否则 不是第一个元素，
//则设置该元素的下一个元素为上一个元素的下一个元素。
//意思就是 取消该元素在链表中的前后关系。
prev.next = next;
x.prev = null;
}
//如果进入该判断，则该元素为最后一个元素。
//删除后，就把该元素的上一个元素设置为最后一个元素
if (next == null) {
last = prev;
} else {
//否则不是最后一个元素
//则设置该元素的上一个元素为下一个元素的上一个元素
//同理，取消该元素的前后关系。
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
//由此可以看出，增加，修改是维护前后关系，删除则是取消前后关系。
关于效率
LinkedList在增删改查中基本上都用到了node(index) 这个方法，在查询方面是肯定没有ArrayList的效率高的。
但是在增加，删除，修改方面也不一定就是比ArrayList效率高，因为这些方法都涉及到了寻址，LinkedList寻址的效率还是稍微低一点的。但是ArrayList在扩容，修改的时候都会使用System.arraycopy()这个方法，所以综合来说结论：查询ArrayList效率要高。修改的时候 大多数情况LinkedList的效率要高。
两个都有缺陷，所以有了Hash。
tip:这个LinkedList 还是很有意思的。但是由于语文不是很好，有很多表达的有点啰嗦了。
网友评论