当前位置：首页 > news >正文

Java中LinkList的基本介绍和细节讨论。双向链表的代码和LinkList的源码。LinkList和ArrayList的比较与选择。

news 2025/7/19 9:02:47

LinkedList 是 Java 中的一个双向链表实现的类，它实现了 List 接口，同时也实现了 Deque 接口，因此可以用作列表、队列或双端队列。下面是关于 LinkedList 的基本介绍和细节讨论：

基本介绍：

LinkedList 是一个双向链表实现，每个节点包含了当前元素的值、指向前一个节点的引用和指向下一个节点的引用。
它实现了 List 接口，因此具备了列表的功能，支持随机访问、添加、删除等操作。
由于是链表实现，它在插入和删除元素时的性能通常比数组实现的 ArrayList 更好。
它同时也实现了 Deque 接口，因此支持队列和双端队列的操作。

细节讨论：

LinkedList 允许元素为 null。
由于是链表结构，它在随机访问时的性能较差，需要遍历链表来找到对应索引的元素。
插入和删除元素的性能较好，因为只需要改变节点的引用即可，而不需要像数组那样进行元素的移动。
LinkedList 内部使用双向链表结构，因此在插入和删除元素时不需要像 ArrayList 那样进行数组元素的移动。
LinkedList 不适合大量随机访问的场景，适合在插入和删除元素频繁的情况下使用。
LinkedList 在使用迭代器遍历时，性能可能会比 ArrayList 稍差，因为它需要在链表中移动节点。
LinkedList 的内存消耗会稍微大于 ArrayList，因为每个节点需要保存额外的前后节点的引用。

适用场景：

当需要频繁地在列表的任意位置插入或删除元素时，可以考虑使用 LinkedList。
当需要实现队列或双端队列时，LinkedList 是一个不错的选择，因为它实现了 Deque 接口。
不适合需要频繁随机访问元素的场景，因为它的随机访问性能较差。

总之，LinkedList 是一种适合特定场景的数据结构，特别适用于需要频繁插入和删除元素的情况。在选择使用时，应根据具体的应用场景和性能需求进行权衡。

双向列表的代码：

public class LinkListExpandCode {public static void main(String[] args) {Node ret1 = new Node("ret1");Node ret2 = new Node("ret2");Node ret3 = new Node("ret3");ret1.next = ret2;ret2.next = ret3;ret3.pre = ret2;ret2.pre = ret1;Node first = ret1;Node last = ret3;//从头遍历while (true){if(first == null){break;}System.out.println(first);first = first.next;}//从尾遍历while (true){if(last == null){break;}System.out.println(last);last = last.pre;}//插入对象Node ret = new Node("ret");ret.next = ret3;ret.pre = ret2;ret2.next = ret;ret3.pre = ret;//遍历//遍历之前先将first恢复原位,因为之前从头开始遍历的时候first到尾部了first = ret1;//first恢复原位//从头遍历while (true){if(first == null){break;}System.out.println(first);first = first.next;}//删除对象ret2.next = ret3;ret3.pre = ret2;//从头遍历first = ret1;//first恢复原位while (true){if(first == null){break;}System.out.println(first);first = first.next;}}
}class Node{//模拟双向列表private Object name;public Node pre;//注意这里的类型是Node类型,因为在main方法中pre和next要作为引用指向别的结点public Node next;public Node(Object name) {this.name = name;}@Overridepublic String toString() {return "Node{" +"name=" + name +'}';}
}

LinkList的源码：

public class LinkListCRUD {public static void main(String[] args) {/*** 源码(以增为例)：第一步public LinkedList() {}第二步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;elsel.next = newNode;size++;modCount++;}//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;}}** */LinkedList linkedList = new LinkedList();//增linkedList.add("ret1");linkedList.add("ret2");linkedList.add("ret3");System.out.println(linkedList);//删linkedList.remove("ret2");System.out.println(linkedList);//改linkedList.set(1,"ret2");System.out.println(linkedList);//查System.out.println(linkedList.contains("ret2"));System.out.println(linkedList.get(1));}
}

Java中LinkList和ArrayList的比较与选择：

LinkedList 和 ArrayList 都是 Java 中常用的集合类，它们分别基于链表和动态数组的数据结构实现，各有优劣。下面是它们的比较与选择的一些方面：

性能比较：

随机访问：ArrayList 在随机访问时性能优于 LinkedList，因为 ArrayList 底层使用数组，可以通过索引直接访问元素，而 LinkedList 需要遍历链表才能访问指定索引的元素。
插入和删除：LinkedList 在插入和删除元素时性能优于 ArrayList，因为链表插入和删除只需要改变节点的引用，而不需要移动元素。而 ArrayList 在插入和删除时需要移动元素来保持连续性。

内存消耗：