地图 添加到网站,哈尔滨网站制作建设,trs网站建设平台,刷单网站搭建在 Java 的集合框架中#xff0c;LinkedList是一个独特且常用的成员。它基于双向链表实现#xff0c;与数组结构的集合类如ArrayList有着显著差异。深入探究LinkedList的底层源码#xff0c;有助于我们更好地理解其工作原理和性能特点#xff0c;以便在实际开发中做出更合适… 在 Java 的集合框架中LinkedList是一个独特且常用的成员。它基于双向链表实现与数组结构的集合类如ArrayList有着显著差异。深入探究LinkedList的底层源码有助于我们更好地理解其工作原理和性能特点以便在实际开发中做出更合适的选择。 这里如何具体在idea里查看底层源码的教程在我ArrayList那篇文章有基本大差不差具体步骤我就不再演示了我直接把所有底层源码总结下来供大家参考。 咱们可以根据这个代码逻辑自己推一下捋清楚了思路就好理解多了。 一、基本结构与成员变量
LinkedList的底层核心是一个双向链表其内部通过节点来存储数据。以下是LinkedList源码中关键的成员变量定义
// 头节点
transient NodeE first;
// 尾节点
transient NodeE last;
// 元素数量
transient int size 0;
// 底层双向链表节点的内部类
private static class NodeE {// 当前节点的元素值E item;// 指向下一个节点的引用NodeE next;// 指向前一个节点的引用NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}first和last分别指向双向链表的头节点和尾节点通过它们可以方便地对链表进行遍历和操作。size变量用于记录链表中元素的个数。Node内部类则定义了链表节点的结构每个节点不仅存储了元素值item还持有指向前驱节点prev和后继节点next的引用这使得双向链表能够灵活地在两个方向上进行遍历和元素的插入、删除等操作。
二、构造函数剖析
无参构造函数
public LinkedList() {
}无参构造函数非常简洁它只是创建了一个空的LinkedList对象。此时first和last都为nullsize为 0链表中没有任何元素。
带集合参数的构造函数
public LinkedList(Collection? extends E c) {this();addAll(c);
}该构造函数先调用无参构造函数创建一个空链表然后通过addAll方法将传入集合中的所有元素添加到新创建的LinkedList中。这为我们在初始化LinkedList时提供了一种便捷的方式可以直接将其他集合中的元素导入进来。
三、元素添加操作
在链表尾部添加元素
add(E e)方法用于在链表尾部添加一个元素它是LinkedList中最常用的添加元素的方式之一。
public boolean add(E e) {linkLast(e);return true;
}
void linkLast(E e) {final NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;
}add(E e)方法内部调用了linkLast方法。linkLast方法首先记录原链表的尾节点l然后创建一个新的节点newNode使其前驱指向原尾节点l后继为null。接着更新last指向新节点如果原尾节点为空说明链表之前是空的此时first也指向新节点否则将原尾节点的后继指向新节点。最后更新元素数量size和修改次数modCount。这个过程使得在链表尾部添加元素的操作非常高效时间复杂度为 O (1)。
在指定位置插入元素
add(int index, E element)方法可以在链表的指定位置插入一个元素。
public void add(int index, E element) {checkPositionIndex(index);if (index size)linkLast(element);elselinkBefore(element, node(index));
}该方法首先调用checkPositionIndex方法检查索引是否越界要求0 index size。如果索引等于size说明要在链表尾部插入元素直接调用linkLast方法即可否则调用linkBefore方法在指定节点前插入元素。这里的node(index)方法用于获取指定索引位置的节点
NodeE node(int index) {if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
}node(index)方法通过判断索引与链表长度一半的大小关系决定从链表头部还是尾部开始遍历查找指定索引位置的节点。如果索引小于链表长度的一半从链表头部开始遍历否则从链表尾部开始遍历。这种优化策略可以减少遍历的节点数量提高查找效率。
四、元素删除操作
移除指定位置的元素
remove(int index)方法用于移除链表中指定位置的元素。
public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}该方法先调用checkElementIndex方法检查索引是否越界要求0 index size然后通过node(index)方法获取指定索引位置的节点最后调用unlink方法移除该节点并返回其存储的元素。
E unlink(NodeE x) {final E element x.item;final NodeE next x.next;final NodeE 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;
}unlink方法通过调整节点之间的引用关系将指定节点从链表中移除。它先保存要移除节点的元素值、后继节点和前驱节点然后根据前驱和后继节点的情况更新链表的头节点first或尾节点last以及相关节点的前驱和后继引用。最后将被移除节点的元素值置为null更新元素数量size和修改次数modCount并返回被移除的元素。
移除指定元素的第一个匹配项
remove(Object o)方法用于移除链表中指定元素的第一个匹配项。
public boolean remove(Object o) {if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);return true;}}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}该方法通过遍历链表分别处理要移除的元素为null和不为null的情况。找到匹配的元素后调用unlink方法将其移除并返回true如果遍历完链表都没有找到匹配元素则返回false。
五、元素查找操作
查找指定元素首次出现的索引
indexOf(Object o)方法用于返回指定元素在链表中首次出现的索引如果不存在则返回 -1。
public int indexOf(Object o) {int index 0;if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null)return index;index;}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item))return index;index;}}return -1;
}该方法从链表头部开始遍历分别处理查找元素为null和不为null的情况找到匹配元素时返回其索引遍历完链表都未找到则返回 -1。
查找指定元素最后一次出现的索引
lastIndexOf(Object o)方法用于返回指定元素在链表中最后一次出现的索引如果不存在则返回 -1。
public int lastIndexOf(Object o) {int index size;if (o null) {for (NodeE x last; x ! null; x x.prev) {index--;if (x.item null)return index;}} else {for (NodeE x last; x ! null; x x.prev) {index--;if (o.equals(x.item))return index;}}return -1;
}该方法从链表尾部开始遍历分别处理查找元素为null和不为null的情况找到匹配元素时返回其索引遍历完链表都未找到则返回 -1。 通过对LinkedList底层源码的剖析我们清楚地了解了它的结构和各种操作的实现原理。LinkedList在插入和删除元素时具有高效性尤其是在链表中间位置进行操作时不需要像ArrayList那样进行大量元素的移动。然而由于其基于链表结构随机访问元素的时间复杂度较高需要遍历链表来查找指定位置的元素。因此在实际开发中我们应根据具体的需求和操作场景合理选择使用LinkedList或其他集合类以达到最佳的性能和功能实现。
