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

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 在插入和删除时需要移动元素来保持连续性。

内存消耗：

• LinkedList 需要额外的空间存储前后节点的引用，因此内存消耗稍高于 ArrayList。

• ArrayList 需要预分配数组空间，当元素个数增加时可能需要进行扩容，扩容时需要重新分配数组并复制元素，可能会导致内存重新分配的开销。

迭代性能：

• 在使用迭代器遍历集合时，ArrayList 的性能通常优于 LinkedList，因为 ArrayList 在数组中连续存储元素，迭代时可以更高效地访问。

适用场景：

• 如果需要频繁进行随机访问操作，使用 ArrayList 更合适，例如需要根据索引获取元素或进行快速遍历。

• 如果需要频繁进行插入和删除操作，特别是在中间位置进行插入和删除，使用 LinkedList 更合适，因为链表插入和删除操作性能更好。

综合考虑：

• 如果对集合的操作类型不确定，或者需要在不同操作间取得平衡，可以根据实际场景进行选择。

• 如果对性能要求不高，且操作类型多样，可以优先选择 ArrayList，因为它在大多数情况下都表现得很好。

• 如果需要根据不同操作类型进行优化，也可以根据操作的频率和性质来选择使用 ArrayList 或 LinkedList。

综合来说，选择使用 ArrayList 还是 LinkedList 取决于具体的使用场景和操作类型。如果可能，可以根据实际需求进行性能测试和评估，以便选择最适合的集合类。