Java LinkedList

什么是LinkedList

• LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 实现 List 接口，能对它进行列表操作。
• LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
• LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
• LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
• LinkedList 是非同步的。
• 适用于乱序插入, 删除. 指定序列操作则性能不如ArrayList, 这也是其数据结构决定的.

继承关系

继承关系

图解说明LinkedList操作

以下内容来自于 图解Java常用数据结构
add(E) / addLast(E)

image

add(index, E)

这边有个小的优化, 他会先判断index是靠近队头还是队尾, 来确定从哪个方向遍历链入.

if (index < (size >> 1)) {
   Node<E> x = first;
  for (int i = 0; i < index; i++)
  x = x.next;
  return x;6         
} else {
  Node<E> x = last;
  for (int i = size - 1; i > index; i--)
  x = x.prev;
  return x;
}

靠队头

image

靠队尾

image

get(index)

也是会先判断index, 不过性能依然不好, 这也是为什么不推荐用for(int i = 0; i < lengh; i++)的方式遍历linkedlist, 而是使用iterator的方式遍历.

靠队头

image
靠队尾
image

remove(E)

image

LinkedList内部做了查询优化：遍历时先判断索引是靠近队头还是队尾，如果靠近队头，从first开始遍历；否则从last遍历。