# 23张图！万字详解「链表」，从小白到大佬！

## 分类

• 单向链表
• 双向链表
• 循环链表

• 单循链表
• 双循环链表

### 1.单向链表

``````private static class Node {
E item;
Node next;

Node(E element, Node next) {
this.item = element;
this.next = next;
}
}``````

### 2.双向链表

``````private static class Node {
E item;
Node next;
Node prev;

Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}``````

## Java中的链表

``````package java.util;

import java.util.function.Consumer;

extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
// 链表大小
transient int size = 0;

// 链表头部
transient Node first;

// 链表尾部
transient Node last;

}

this();
}

// 获取头部元素
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

// 获取尾部元素
public E getLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

// 删除头部元素
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
}

// 删除尾部元素
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
}

// 添加头部元素
}

// 添加头部元素的具体执行方法
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

// 添加尾部元素
}

// 添加尾部元素的具体方法
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

// 查询链表个数
public int size() {
return size;
}

// 清空链表
public void clear() {
for (Node x = first; x != null; ) {
Node next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}

// 根据下标获取元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

private static class Node {
E item;
Node next;
Node prev;

Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 忽略其他方法......
}``````

## 链表常用方法

`LinkedList` 的设计还是很巧妙的，了解了它的实现代码之后，下面我们来看看它是如何使用的？或者说它的常用方法有哪些。

### 1.增加

``````public class LinkedListTest {
public static void main(String[] a) {
System.out.println(list);
}
}``````

[头部添加, Java, 中文, 社群, 尾部添加]

• offer(E e)：向链表末尾添加元素，返回是否成功；
• offerFirst(E e)：头部插入元素，返回是否成功；
• offerLast(E e)：尾部插入元素，返回是否成功。

• offer 方法属于 Deque 接口，add 方法属于 Collection 的接口；
• 当队列添加失败时，如果使用 add 方法会报错，而 offer 方法会返回 false。

### 2.删除

``````import java.util.LinkedList;

public static void main(String[] a) {
list.offer("头部");
list.offer("中间");
list.offer("尾部");

list.removeFirst(); // 删除头部元素
list.removeLast();  // 删除尾部元素

System.out.println(list);
}
}``````

[中间]

• clear()：清空链表；
• removeFirst()：删除并返回第一个元素；
• removeLast()：删除并返回最后一个元素；
• remove(Object o)：删除某一元素，返回是否成功；
• remove(int index)：删除指定位置的元素；
• poll()：删除并返回第一个元素；
• remove()：删除并返回第一个元素。

### 3.修改

``````import java.util.LinkedList;

public static void main(String[] a) {
list.offer("Java");
list.offer("MySQL");
list.offer("DB");

// 修改
list.set(2, "Oracle");

System.out.println(list);
}
}``````

[Java, MySQL, Oracle]

### 4.查询

``````import java.util.LinkedList;

public static void main(String[] a) {
list.offer("Java");
list.offer("MySQL");
list.offer("DB");

// --- getXXX() 获取 ---
// 获取最后一个
System.out.println(list.getLast());
// 获取首个
System.out.println(list.getFirst());
// 根据下标获取
System.out.println(list.get(1));

// peekXXX() 获取
System.out.println("--- peek() ---");
// 获取最后一个
System.out.println(list.peekLast());
// 获取首个
System.out.println(list.peekFirst());
// 根据首个
System.out.println(list.peek());
}
}``````

DB

Java

MySQL

--- peek() ---

DB

Java

Java

### 5.遍历

`LinkedList` 的遍历方法包含以下三种。

``````for (int size = linkedList.size(), i = 0; i < size; i++) {
}``````

``````for (String str: linkedList) {
System.out.println(str);
}``````

``````Iterator iter = linkedList.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}``````

## 链表应用：队列 & 栈

### 1.用链表实现栈

``````LinkedList list = new LinkedList();
// 元素入列

while (!list.isEmpty()) {
// 打印并移除队头元素
System.out.println(list.poll());
}``````

Java

### 2.用链表实现队列

``````LinkedList list = new LinkedList();
// 元素入栈

while (!list.isEmpty()) {
// 打印并移除栈顶元素
System.out.println(list.pollLast());
}``````

Java

## 链表常见笔试题

### 实现方法 1：Stack

``````public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack stack = new Stack<>();
}
// 反转链表
ListNode listNode = stack.pop(); // 反转第一个元素
ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 当前节点
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
return listNode;
}``````

LeetCode 验证结果如下图所示：

### 实现方法 2：递归

``````public static ListNode reverseList(ListNode head) {
// 从下一个节点开始递归
head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
return reverse;
}``````

LeetCode 验证结果如下图所示：

### 实现方法 3：循环

``````class Solution {
if (head == null) return null;
// 最终排序的倒序链表
ListNode prev = null;
// 循环的下个节点
// 反转节点操作
// 存储下个节点的上个节点
// 移动指针到下一个循环
}
return prev;
}
}``````

LeetCode 验证结果如下图所示：