本文共 5234 字,大约阅读时间需要 17 分钟。
通过前面的分析,我们知道了ArrayList是基于数组实现的,因此比较适合查询和修改比较多的操作。而LinkedList是基于双向链表实现的,因此比较适合添加和删除。
我们可以看见LinkedList是一个基于双向链表的数据结构(有指向前一个和指向后一个的引用),因此如果我们要遍历集合,可以进行双向遍历。
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable
LinkedList的类继承结构很有意思,我们着重要看是Deque接口,Deque接口表示是一个双端队列,那么也意味着LinkedList是双端队列的一种实现,所以,基于双端队列的操作在LinkedList中全部有效。
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; } }
上面的内部类就是实际的节点,用于存放数据的地方。
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ // 实际元素个数 transient int size = 0; // 头结点 transient Node first; // 尾结点 transient Node last;}
public LinkedList() {}
有参构造函数
public LinkedList(Collection c) { // 调用无参构造函数 this(); // 添加集合中所有的元素 addAll(c); }
我们可以看见上面两个构造函数,第二个构造函数最终调用了addAll来将所有的数据加入集合。
public boolean add(E e) { // 添加到末尾 linkLast(e); return true; }
通过上面我们能可以看出主要是调用了函数linkLast来讲元素添加到双向链表的末端。
void linkLast(E e) { // 保存尾结点,l为final类型,不可更改 final Nodel = last; // 新生成结点的前驱为l,后继为null final Node newNode = new Node<>(l, e, null); // 重新赋值尾结点 last = newNode; if (l == null) // 尾结点为空 first = newNode; // 赋值头结点 else // 尾结点不为空 l.next = newNode; // 尾结点的后继为新生成的结点 // 大小加1 size++; // 结构性修改加1 modCount++; }
可以看见添加元素的操作其实就是简单地创建节点,然后改变前驱和后继的引用。
// 添加一个集合 public boolean addAll(int index, Collection c) { // 检查插入的的位置是否合法 checkPositionIndex(index); // 将集合转化为数组 Object[] a = c.toArray(); // 保存集合大小 int numNew = a.length; if (numNew == 0) // 集合为空,直接返回 return false; Nodepred, succ; // 前驱,后继 if (index == size) { // 如果插入位置为链表末尾,则后继为null,前驱为尾结点 succ = null; pred = last; } else { // 插入位置为其他某个位置 succ = node(index); // 寻找到该结点 pred = succ.prev; // 保存该结点的前驱 } for (Object o : a) { // 遍历数组 @SuppressWarnings("unchecked") E e = (E) o; // 向下转型 // 生成新结点 Node newNode = new Node<>(pred, e, null); if (pred == null) // 表示在第一个元素之前插入(索引为0的结点) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { // 表示在最后一个元素之后插入 last = pred; } else { pred.next = succ; succ.prev = pred; } // 修改实际元素个数 size += numNew; // 结构性修改加1 modCount++; return true; }
从上面可以看出对addAll方法的操作其实就是从指定位置开始创建新节点,并遍历设置前驱和后继。
上面有一个函数node,我们查看源码
Nodenode(int index) { // 判断插入的位置在链表前半段或者是后半段 if (index < (size >> 1)) { // 插入位置在前半段 Node x = first; for (int i = 0; i < index; i++) // 从头结点开始正向遍历 x = x.next; return x; // 返回该结点 } else { // 插入位置在后半段 Node x = last; for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历 x = x.prev; return x; // 返回该结点 } }
可以看见函数根据index是否大于size的一半来判断从前还是从后开始遍历,这样就可以达到最快速遍历。
public boolean remove(Object o) { if (o == null) { for (Nodex = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
从上面我们可以看出remove方法其实就是根据元素在链表中遍历找到相等的元素,然后调用unlink方法。
E unlink(Nodex) { // 保存结点的元素 final E element = x.item; // 保存x的后继 final Node next = x.next; // 保存x的前驱 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; // 结点元素赋值为空 // 减少元素实际个数 size--; // 结构性修改加1 modCount++; // 返回结点的旧元素 return element; }
我们可以看出其实unlink方法实现的就是将节点从链表的断开,而要达到这个目的就是修改相应的前后节点引用。