- 1. 概述
- 2. 底层实现
- 3. 常用方法介绍
- 3.1 add()
- 3.2 remove()
- 3.3 get()
- 3.4 set()
- 4. 遍历方法
- 4.1 Iterator方法遍历
- 4.2 for循环遍历
- 4.3 增强for循环遍历
- 4.4 用pollFirst()遍历
- 4.5 用pollLast()遍历
- 4.6 用removeFirst()遍历
- 4.7 用removeLast()遍历
- 5. 参考
linkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，linkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用linkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。关于栈或队列，现在的首选是ArrayDeque，它有着比linkedList（当作栈或队列使用时）有着更好的性能。
2. 底层实现
- linkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。linkedList通过first和last引用分别指向链表的第一个和最后一个元素。
//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; } }
3. 常用方法介绍
本节将着重讲解插入和删除元素时双向链表的维护过程，也即是直接跟List接口相关的函数。
3.1 add()add() 方法有两个版本，一个是 add(E e) ，该方法在 linkedList 的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是 add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。
结合上图，可以看出 add(E e) 的逻辑非常简单。
//add(E e)
public boolean add(E e) {
final Node l = last; // 先保留原来的尾节点
final Node newNode = new Node<>(l, e, null); // 声明并初始化待插入的节点
last = newNode; // 更新尾节点
if (l == null)
first = newNode; //原来链表为空，这是插入的第一个元素
else
l.next = newNode; // 原来的尾节点变为倒数第二个节点，更新其next指针
size++;
return true;
}
add(int index, E element) 的逻辑稍显复杂，可以分成两部分，1.先根据index找到要插入的位置；2.修改引用，完成插入操作。
//add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);//index >= 0 && index <= size;
if (index == size)//插入位置是末尾，包括列表为空的情况
add(element);
else {
Node succ = node(index);//1.先根据index找到要插入的位置
//2.修改引用，完成插入操作。
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)//插入位置为0
first = newNode;
else
pred.next = newNode;
size++;
}
}
上面代码中的 node(int index) 函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件 index < (size >> 1)，也即是 index 是靠近前端还是后端。
3.2 remove()
remove() 方法也有两个版本，一个是删除跟指定元素相等的第一个元素 remove(Object o)，另一个是删除指定下标处的元素 remove(int index)。
两个删除操作都要:1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候 remove(Object o) 调用的是元素的equals方法，而 remove(int index) 使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个 remove() 方法都是通过unlink(Node
//unlink(Nodex)，删除一个Node E unlink(Node x) { final E element = x.item; final Node next = x.next; final Node 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;//let GC work size--; return element; }
3.3 get()
get(int index) 得到指定下标处元素的引用，通过调用上文中提到的 node(int index) 方法实现。
public E get(int index) {
checkElementIndex(index);//index >= 0 && index < size;
return node(index).item;
}
Nodenode(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { // index在前半部分，从头指针开始查找 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // index在后半部分，从尾指针开始查找 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
3.4 set()
set(int index, E element) 方法将指定下标处的元素修改成指定值，也是先通过 node(int index) 找到对应下表元素的引用，然后修改 Node 中 item 的值。
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;//替换新值
return oldVal;
}
4. 遍历方法 4.1 Iterator方法遍历
for(Iterator it = list.iterator();it.hasNext();){
System.out.println(it.next());
}
遍历时不能使用list的删除方法，否则会报并发修改异常，但是可以使用迭代器的删除方法
4.2 for循环遍历
for(int i = 0;i < list.size(); i ++){
System.out.println(list.get(i));
}
遍历时可以修改list
4.3 增强for循环遍历
for(String tmp:list){
System.out.println(tmp);
}
底层基于迭代器实现，遍历时不能使用list的删除方法，否则会报并发修改异常，但是可以使用迭代器的删除方法
4.4 用pollFirst()遍历
while(list.pollFirst() != null) {
;
}
4.5 用pollLast()遍历
while(list.pollLast() != null) {
;
}
4.6 用removeFirst()遍历
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
}
4.7 用removeLast()遍历
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}
5. 参考
- 《深入理解Java集合框架》
- JAVAschool
