数字营销技术应用网站,北京app开发多少钱,wordpress首页屏蔽插件,网站开发 密码一、 继承体系
LinkedList类位于java.util包中#xff0c;它实现了List接口和Deque接口#xff0c;LinkedList可以被当做链表、双端队列使用#xff0c;并且继承自AbstractSequentialList类。在继承关系中#xff0c;它的父类是AbstractSequentialList#xff0c;而Abstr…一、 继承体系
LinkedList类位于java.util包中它实现了List接口和Deque接口LinkedList可以被当做链表、双端队列使用并且继承自AbstractSequentialList类。在继承关系中它的父类是AbstractSequentialList而AbstractSequentialList又继承自AbstractListAbstractList继承自AbstractCollectionAbstractCollection实现了Collection接口。
二、设计目的
LinkedList的设计目的是为了提供一个基于链表的动态数组实现它可以高效地进行插入、删除操作并且能够按照索引快速访问元素。与ArrayList不同LinkedList不需要预先分配固定大小的空间因此适用于频繁插入、删除操作的场景。
三、框架总结结构
LinkedList采用双向链表的数据结构来存储元素每个节点包含指向前一个节点和后一个节点的引用。它提供了add、remove、get等操作方法以及支持队列和栈的操作方法。LinkedList还实现了ListIterator接口可以进行双向迭代操作。
四、工作原理
在LinkedList中每次添加或删除元素时它会重新调整节点之间的引用关系保证链表的正确性。在添加元素时它会创建一个新的节点并将其插入到链表中并更新前后节点的引用在删除元素时它会修改前后节点的引用使得被删除节点脱离链表。由于LinkedList采用双向链表的结构因此在插入和删除元素时时间复杂度为O(1)。
五、如何创建LinkedList
{transient int size 0;/*** Pointer to first node.* Invariant: (first null last null) ||* (first.prev null first.item ! null)*/transient NodeE first; //指向第一个节点的指针首节点的元素类型为 E/*** Pointer to last node.* Invariant: (first null last null) ||* (last.next null last.item ! null)*/transient NodeE last; //指向第一个节点的指针首节点的元素类型为 E。/*** Constructs an empty list.*/public LinkedList() {}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collections* 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);}LinkedList类的构造函数。第一个构造函数是无参构造函数用于构造一个空的LinkedList实例。第二个构造函数接受一个集合参数c并将该集合中的元素按照迭代器返回的顺序添加到LinkedList中。首先调用了无参构造函数this()来初始化一个空的LinkedList然后调用addAll方法将集合c中的所有元素添加到LinkedList中。这样设计的意义在于提供了创建LinkedList的灵活性可以直接传入一个集合来初始化LinkedList。
六、addE e添加源码
public boolean add(E e) {linkLast(e);return true;}linkLast(e)方法将元素e链接到链表的末尾然后返回true表示添加元素成功。 linkLast(e) 方法会在链表末尾添加一个新节点并更新链表的相关指针。
void linkLast(E e) {final NodeE l last; // 将当前链表的最后一个节点赋值给变量l用final修饰表示l是一个不可变的引用final NodeE newNode new Node(l, e, null); // 创建一个新节点newNode其中// - 前驱节点指向l即当前链表的最后一个节点// - 元素为e即要添加到链表中的元素// - 后继节点暂时为null因为这是新节点添加到最后一个位置last newNode; // 更新last指针使其指向新节点newNode表示新节点成为了链表中的最后一个节点if (l null)first newNode; // 如果原链表为空即l为null将first指针指向新节点newNode表示此时链表只包含一个节点即newNodeelsel.next newNode; // 如果原链表不为空则将当前链表最后一个节点的next指针指向新节点newNode让新节点成为原链表中最后一个节点的后继节点size; // 增加链表的大小表示成功在链表尾部添加了一个新节点modCount; // 修改计数器用于记录对LinkedList结构进行修改的次数以便在迭代过程中检测并发修改操作
} final NodeE l last; 将当前链表的最后一个节点存储在变量l中使用final关键字表示l是一个不可变的引用。 final NodeE newNode new Node(l, e, null); 创建一个新的节点newNode包括 前驱节点指向l即指向当前链表的最后一个节点元素为e即要添加到链表中的元素后继节点暂时为null因为这是要将新节点添加到链表末尾 last newNode; 更新last指针使其指向新创建的节点newNode表示新节点成为了链表中的最后一个节点。 if (l null) 检查原链表是否为空即l为null。 first newNode; 如果原链表为空则将first指针指向新节点newNode表示此时链表只包含一个节点即newNode。 else 如果原链表不为空则执行以下操作 l.next newNode; 让当前链表最后一个节点的next指针指向新节点newNode让新节点成为原链表中最后一个节点的后继节点。 size; 增加链表的大小表示成功在链表尾部添加了一个新节点。 modCount; 修改计数器用于记录对LinkedList结构进行修改的次数以便在迭代过程中检测并发修改操作。 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;}}E item; 定义了一个泛型类型E的变量item用于存储节点中的元素值。 NodeE next; 定义了一个泛型类型为Node的变量next表示指向链表中下一个节点的引用。 NodeE prev; 定义了一个泛型类型为Node的变量prev表示指向链表中上一个节点的引用。 Node(NodeE prev, E element, NodeE next) { 定义了Node类的构造函数包括如下参数 prev: 前驱节点的引用element: 节点中的元素值next: 后继节点的引用 this.item element; 将传入的element赋值给节点的item属性表示该节点存储了对应的元素值。 this.next next; 将传入的next引用赋值给节点的next属性表示该节点指向链表中的下一个节点。 this.prev prev; 将传入的prev引用赋值给节点的prev属性表示该节点指向链表中的上一个节点。 从头部追加addFirst LinkedList arrayList new LinkedList ();arrayList.addFirst(头部);private void linkFirst(E e) {final NodeE f first;final NodeE newNode new Node(null, e, f);first newNode;if (f null)last newNode;elsef.prev newNode;size;modCount;} private void linkFirst(E e) { 定义了一个私有方法linkFirst用于在链表的开头添加一个新节点参数e表示要添加的元素。 final NodeE f first; 通过final关键字将当前链表的第一个节点头节点赋值给变量f。 final NodeE newNode new Node(null, e, f); 创建一个新的节点newNode其中 前驱节点为null因为新节点将成为头节点元素为e即要添加到链表中的元素后继节点为f即原来的头节点 first newNode; 更新first指针使其指向新创建的头节点newNode。 if (f null) 检查原链表是否为空即f为null。 last newNode; 如果原链表为空则将last指针也指向新的头节点newNode。 else 如果原链表不为空则执行以下操作 f.prev newNode; 将原来的头节点的prev指针指向新的头节点newNode建立双向连接。 size; 增加链表的大小表示成功在链表开头添加了一个新的节点。 modCount; 修改计数器用于记录对LinkedList结构进行修改的次数以便在迭代过程中检测并发修改操作。
七、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); // 调用unlink方法将该节点从链表中移除return true; // 返回true表示移除成功}}} else { // 如果传入的对象不为空for (NodeE x first; x ! null; x x.next) { // 遍历链表直到最后一个节点if (o.equals(x.item)) { // 如果传入的对象等于当前节点存储的对象unlink(x); // 调用unlink方法将该节点从链表中移除return true; // 返回true表示移除成功}}}return false; // 如果遍历完链表都没有找到匹配的对象则返回false表示移除失败
}总结如果传入的对象为空则遍历链表直到找到存储的对象也为空的节点然后将其从链表中移除。如果传入的对象不为空则遍历链表直到找到与传入对象相等的节点然后将其从链表中移除。如果未找到匹配的对象则返回false表示移除失败。 /*** Unlinks non-null node x.*/
E unlink(NodeE x) { // 定义了一个方法用于移除非空节点xfinal E element x.item; // 获取节点x存储的元素final NodeE next x.next; // 获取节点x的下一个节点final NodeE prev x.prev; // 获取节点x的前一个节点if (prev null) { // 如果节点x的前一个节点为空first next; // 将链表的头指针指向节点x的下一个节点} else {prev.next next; // 将节点x的前一个节点的next指针指向节点x的下一个节点x.prev null; // 将节点x的prev指针置为空}if (next null) { // 如果节点x的下一个节点为空last prev; // 将链表的尾指针指向节点x的前一个节点} else {next.prev prev; // 将节点x的下一个节点的prev指针指向节点x的前一个节点x.next null; // 将节点x的next指针置为空}x.item null; // 将节点x的元素置为空size--; // 链表大小减一modCount; // 修改次数加一return element; // 返回被移除节点x的元素
}八、 get查找
/*** Returns the (non-null) Node at the specified element 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; // 返回找到的节点}
}根据索引值快速定位链表中的节点通过前半部分和后半部分遍历的方式提高了效率。
LinkedList 总结用法和使用场景
用法LinkedList 是一个双向链表实现的 List支持在任意位置进行元素的插入和删除操作。可以作为队列Queue或双端队列Deque使用。使用场景适合对列表进行频繁的插入和删除操作因为插入和删除节点的开销较小。特别适合需要在中间插入元素的场景。由于每个节点在内存中不连续存储可能会增加内存占用。
LinkedList 性能总结
查询性能LinkedList 在查询时需要遍历链表时间复杂度为 O(n)效率较低。插入/删除性能在列表的开头或中间插入/删除元素时LinkedList 的性能优于 ArrayList因为只需要调整指针即可。迭代性能LinkedList 在迭代访问元素时效率较高不会涉及数组复制等操作。
与 ArrayList 方法对比
ArrayList底层基于数组实现随机访问快但插入和删除元素开销较大需要移动后续元素。适合读取操作多于修改操作的场景。对比 LinkedList 适合频繁插入和删除元素的场景而 ArrayList 更适合于随机访问元素。LinkedList 的插入和删除操作性能更好但查询性能较差ArrayList 的查询性能更好但在插入和删除方面效率相对较低。
