Java链表

链表(Linked List)是一种线性数据结构，它由一系列节点组成，每个节点包含两部分：一部分为用于储存数据元素，另部分是一种引用(指针),指向下一个节点。

这种结构允许动态地添加和删除元素，而不需要像数组那种大规模的数据移动。

 

java链表的定义

在java中，链表可以通过自定义来实现，也可以直接使用java.util.LinkedList 类。LinkedList实现了接口，并且提供了双向链接的功能，即每个节点不仅由指向下一个节点的引用，哈有指向前一个节点的引用。这意味着LinkedList不仅可以作为列表使用，还可以作为栈或队列使用，因为它是基于双向链表现实的。

每个节点通常包含两个字段：

• data：用于存储实际的数据。

• next：用于存储向下一个节点的引用；如果是双向链表，则还有一个prev字段用于存储指向前一个节点的引用。

实例：

在自定义单项链表是，可以这样定义节点类:

class Node<E> {private E elem; // 数据域private Node<E> next; // 指针域public Node(E element, Node<E> next) {this.elem = element;this.next = next;}// Getter 和 Setter 方法...
}

对于LinkedList类而言，内部由一个静态内部类Node，用来表示链表中的节点。此外，LinkedList还维护着几个重要的成员变量，例如size（记录链表大小）、first（指向第一个节点）和last（指向最后一个节点）。这些变量是的可以在O(1)时间内完成对链表头部或尾部的操作。

 

Java链表的应用

由于链表具有灵活的内存管理和高效的插入\删除操作特性,因此适用于多种引用场景：

1. 频繁插入和删除：当应用程序需要频繁地在集合中插入或删除元素是，使用LinkedList会比ArrayList更有效率。这是因为LinkedList不需要像ArrayList那样在插入或删除时调整其他元素的位置，从而避免了额外的时间开销。

2. 作为栈或队列使用:LinkedList实现了Deque接口，所以它可以很方便地用作栈（通过addFirst()、removeFirst()等方法）或者队列（通过addList()、removeFirst()等方法）。

3. 缓存系统：某些缓存算法（例如LRU,Least Recentiy Used）可能需要用到LinkedList来维护元素的顺序。如，可以结合HashMap和LinkedList实现一个简单的LRu缓存。

4. 多线程环境下的队列：尽管LinkedList本身不是线程安全的，但在多线程环境中，可以通过适当的同步机制将其用作线程安全的队列。

5. 文件系统的实现：链表的概念也被应用与文件系统的设计中，比如FAT32、NTFS等格式的选择实际上就是在选择不同类型的链表空间规模及格式。

6. 高级数据结构：除了上述应用外，java链表还可以用于构建更加复杂的结构，如双端队列（Deque）、循环链表（Circular Linked List）、跳表（Skip List）等。

7. 链表合并：在排序算法中，如归并排序、合并两个有序链表也是常见的操作之一。

8. 返回倒数第K个节点:利用前后指针法可以高效地找到链表中的倒数第K个节点。

常用方法

 

方法	描述
public boolean add(E e)	链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
public void add(int index, E element)	向指定位置插入元素。
public boolean addAll(Collection c)	将一个集合的所有元素添加到链表后面，返回是否成功，成功为 true，失败为 false。
public boolean addAll(int index, Collection c)	将一个集合的所有元素添加到链表的指定位置后面，返回是否成功，成功为 true，失败为 false。
public void addFirst(E e)	元素添加到头部。
public void addLast(E e)	元素添加到尾部。
方法	描述
public boolean add(E e)	链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
public void add(int index, E element)	向指定位置插入元素。
public boolean addAll(Collection c)	将一个集合的所有元素添加到链表后面，返回是否成功，成功为 true，失败为 false。
public boolean addAll(int index, Collection c)	将一个集合的所有元素添加到链表的指定位置后面，返回是否成功，成功为 true，失败为 false。
public void addFirst(E e)	元素添加到头部。
public void addLast(E e)	元素添加到尾部。
public boolean offer(E e)	向链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
public boolean offerFirst(E e)	头部插入元素，返回是否成功，成功为 true，失败为 false。
public boolean offerLast(E e)	尾部插入元素，返回是否成功，成功为 true，失败为 false。
public void clear()	清空链表。
public E removeFirst()	删除并返回第一个元素。
public E removeLast()	删除并返回最后一个元素。
public boolean remove(Object o)	删除某一元素，返回是否成功，成功为 true，失败为 false。
public E remove(int index)	删除指定位置的元素。
public E poll()	删除并返回第一个元素。
public E remove()	删除并返回第一个元素。
public boolean contains(Object o)	判断是否含有某一元素
public E get(int index)	返回指定位置的元素。
public E getFirst()	返回第一个元素。
public E getLast()	返回最后一个元素。
public int indexOf(Object o)	查找指定元素从前往后第一次出现的索引。
public int lastIndexOf(Object o)	查找指定元素最后一次出现的索引。
public E peek()	返回第一个元素。
public E element()	返回第一个元素。
public E peekFirst()	返回头部元素。
public E peekLast()	返回尾部元素。
public E set(int index, E element)	设置指定位置的元素。
public Object clone()	克隆该列表。
public Iterator descendingIterator()	返回倒序迭代器。
public int size()	返回链表元素个数。
public ListIterator listIterator(int index)	返回从指定位置开始到末尾的迭代器。
public Object[] toArray()	返回一个由链表元素组成的数组。
public T[] toArray(T[] a)	返回一个由链表元素转换类型而成的数组。

上述列来自于菜鸟教程，下方为更多API方法

LinkedList (Java SE 11 & JDK 11 )

链表应用定义总结：

Java中的链表不仅是一个基础的数据结构，而且因其灵活性和效率，在许多不同的编程场景中都有着广泛的应用。无论是作为简单的容器还是构建更为复杂的数据结构的基础组件，链表都扮演着不可或缺的角色。

链表应用实例

创建链表

首先，我们可以创建一个空的LinkedList实例：

 

import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {// 创建一个新的空LinkedListLinkedList<String> list = new LinkedList<>();}
}

这段代码展示了如何导入java.util.LinkedList包，并创建了一个存储字符串类型的LinkedList对象。

添加元素

接下来，我们可以在链表中添加元素。可以使用add()方法向链表末尾添加元素，或者使用addFirst()、addLast()分别向链表头部或尾部插入元素。

// 向链表末尾添加元素
list.add("Apple");
list.add("Banana");// 向链表头部添加元素
list.addFirst("Orange");// 向链表尾部添加元素
list.addLast("Grape");

这里展示了如何使用不同的方法向链表中添加元素。值得注意的是，addFirst()和addLast()提供了更明确的操作意图，而不仅仅是默认地添加到链表末尾。

访问元素

访问链表中的元素可以通过索引进行，也可以遍历整个链表。对于前者，可以使用get()方法；对于后者，则可以使用增强型for循环或迭代器。

// 通过索引访问元素
String element = list.get(1); // 获取第二个元素// 使用增强型for循环遍历链表
for (String fruit : list) {System.out.println(fruit);
}// 使用迭代器遍历链表
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {System.out.println(iterator.next());
}

 

这里介绍了两种常见的遍历方式：一种是直接通过索引获取特定位置的元素，另一种则是利用迭代器逐一访问每个元素。

删除元素

删除链表中的元素同样支持多种方式，包括根据索引删除、根据值删除以及移除链表头尾的元素。

// 根据索引删除元素
list.remove(0); // 移除第一个元素// 根据值删除元素
list.remove("Banana"); // 移除值为"Banana"的第一个匹配项// 移除链表头部元素
list.removeFirst();// 移除链表尾部元素
list.removeLast();

 

插入元素

除了简单的添加和删除外，还可以在链表的任意位置插入新元素。这通常涉及到先找到目标位置，然后将新元素插入到该位置之前或之后。

// 在指定位置插入元素
list.add(1, "Peach"); // 在索引1处插入"Peach"

查找元素

如果想要检查某个元素是否存在於链表中，可以使用contains()方法。

boolean exists = list.contains("Apple");
if (exists) {System.out.println("The list contains Apple.");
} else {System.out.println("The list does not contain Apple.");
}

这段代码用来验证链表中是否包含特定元素，并输出相应的消息。

这些例子涵盖了Java中LinkedList的基本用法，包括创建、添加、访问、删除、插入以及查找元素。