LinkedList
LinkedList底层数据结构通过双向链表来实现，也正因如此，对于头插和尾插操作以及删除元素的操作，其事件复杂度近似O(1)，所以，并非将LinkedList作为链表就最适合元素增删的场景，它在除了上述情况意外对元素进行增删操作的时间复杂度都是O(n)
为什么LinkedList不能实现RandomAccess接口？
RandomAccess接口是一个标记接口，用来表示实现了该接口的集合类可以通过随机访问元素的方式来提高访问效率，但是LinkedList的底层数据接口是链表，其内存地址并不连续，只能通过指针的方式来定位，不支持随机快速访问，所以不能实现RandomAccess接口
LinkedList源码
LinkedList类：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
// ......
}LinkedList与ArrayList有大部分方法相似是因为：LinkedList继承自AbstractSequentialList，AbstractSequentialList继承自AbstractList，而ArrayList也继承自AbstractList
LinkedList实现的接口：
List：表明LinkedList是一个列表，支持对元素增删改查等操作，且可以通过get(int index)方法使用下标获取元素。Deque：双端队列，继承了Queue，表明LinkedList具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。Cloneable：表明LinkedList可以进行深拷贝和浅拷贝
LinkedList中的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;
}
}构造器
空参构造器
/** * Constructs an empty list. */ public LinkedList() { }有参构造器
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
插入元素
add(E e)将元素插到
LinkedList的末尾，时间复杂度O(1)public boolean add(E e) { linkLast(e); return true; } // 将元素插入到链表末尾 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++; }
add(int index, E element)将元素插入到指定位置中，时间复杂度O(n)
public void add(int index, E element) { checkPositionIndex(index); // 如果索引等于链表长度，就把元素插入到链表的末尾 if (index == size) linkLast(element); else linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } // 将元素插入到链表末尾 void linkLast(E e) { // 获取最后一个节点 final Node<E> l = last; // 初始化新节点，指定其前驱节点为链表的末尾节点l，后继为null final Node<E> newNode = new Node<>(l, e, null); // 更新链表的最后一个节点为刚刚插入的新节点 last = newNode; // 如果最后一个节点为null则表示链表为空，将first设置为新节点 if (l == null) first = newNode; else // 链表不为空则将l的后继指向新节点 l.next = newNode; size++; modCount++; } // 在指定元素之前插入元素 void linkBefore(E e, Node<E> succ) { // assert succ != null; // 保存succ节点的上一个节点信息 final Node<E> pred = succ.prev; // 创建一个新节点，并指定其前驱和后继元素 final Node<E> newNode = new Node<>(pred, e, succ); // 设置succ的前驱节点为新节点 succ.prev = newNode; // 如果尾节点为空则表示当前链表内还没有节点，则首元结点就设置为新节点 if (pred == null) first = newNode; else // succ节点的后继指向新节点 pred.next = newNode; size++; modCount++; }
获取元素
getFirst()获取链表的第一个元素
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
getLast()获取链表的最后一个元素
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
get()获取链表指定位置的元素
// 获取链表指定位置的元素 public E get(int index) { // 下标越界检查，如果越界就抛异常 checkElementIndex(index); // 返回链表中对应下标的元素 return node(index).item; }
node方法
Node<E> node(int index) {
// assert isElementIndex(index);
// size>>1等价于size/2
// 如果对应的下标小于总长度的二分之一就从前往后找，否则就从后往前找
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;
}
}
node方法通过比较索引值与链表的size的一半大小来确定从表头还是表尾开始遍历，如果索引值小于size的一半，就从表头开始遍历查找，大于则从表尾开始遍历查找，可以实现这样的功能是基于LinkedList实现了Deque接口，是一个双向链表
删除元素
removeFirst()移除并返回链表的第一个元素
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
removeLast()删除并返回链表的最后一个元素
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
remove(int index)删除并返回指定索引的链表元素
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
remove(Object o)删除链表中首次出现的指定元素，删除成功返回
true，失败返回falsepublic boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
void clear()清空链表中的所有元素
public 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++; }
unlink方法
E unlink(Node<E> x) {
// assert x != null;
// x为待删节点
// 获取x的值、前驱和后继节点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果x的前驱节点为null则说明当前节点为头结点
if (prev == null) {
// 直接让表头指向当前节点的下一个节点
first = next;
} else {
// 如果当前节点不是头结点则将前驱节点的下一个节点指向当前节点的下一个节点
prev.next = next;
// 此时没有引用指向x节点，要将x的后继节点指向null方便gc回收
x.prev = null;
}
// 如果后继节点为null则说明当前节点为链表末尾节点
if (next == null) {
// 将指向链表末尾节点的引用指向前驱节点
last = prev;
} else {
// 如果当前节点不是链表的末尾节点则将下一个节点的前驱节点指向当前节点的前驱节点
next.prev = prev;
// 将x的后继节点指向null，方便gc回收
x.next = null;
}
// 将x的值置为null方便gc回收
x.item = null;
size--;
modCount++;
return element;
}
unlink方法
- 首先获取待删除节点
x的前驱和后继节点；- 判断待删除节点是否为头节点或尾节点：
- 如果
x是头节点，则将first指向x的后继节点next- 如果
x是尾节点，则将last指向x的前驱节点prev- 如果
x不是头节点也不是尾节点，执行下一步操作- 将待删除节点
x的前驱的后继指向待删除节点的后继next，断开x和x.prev之间的链接；- 将待删除节点
x的后继的前驱指向待删除节点的前驱prev，断开x和x.next之间的链接；- 将待删除节点
x的元素置空，修改链表长度。
遍历LinkedList
public static void main(String[] args){
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.forEach(i -> {
System.out.print(integer + " ");
});
}还可以这样写
for (Integer i : list) {
System.out.print(i + " ");
}输出结果都是一致的
