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

分类

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

1.单向链表

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

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

2.双向链表

```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;
}
}```

Java中的链表

```package java.util;

import java.util.function.Consumer;

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

// 链表头部
transient Node<E> first;

// 链表尾部
transient Node<E> last;

}

public LinkedList(Collection<? extends E> c) {
this();
}

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

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

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

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

// 添加头部元素
}

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

// 添加尾部元素
}

// 添加尾部元素的具体方法
final Node<E> l = last;
final Node<E> 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<E> x = first; x != null; ) {
Node<E> 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> {
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` 的设计还是很巧妙的，了解了它的实现代码之后，下面我们来看看它是如何使用的？或者说它的常用方法有哪些。

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());
}```

链表常见笔试题

实现方法 1：Stack

```public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> 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 验证结果如下图所示：

总结

0 条评论

• 一点思考|工作十几年了，竟从未用过do-while！

最近在看 Java 的基础知识，其中有部分是关于循环的，在 Java 中，循环的语法总共分为 3 种： for、 while、 do-while，如下图所示：

• 链表反转的两种实现方法，后一种击败了100%的用户！

链表反转是一道很基础但又非常热门的算法面试题，它也在《剑指Offer》的第 24 道题出现过，至于它有多热（门）看下面的榜单就知道了。

• 算法 - 数组和链表

关于多维数组在内存中的布局参考这篇文章：Memory Layout of Multi-Dimensional Arrays

• 5.链表导论-心法篇

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以...

• 2-5 线性表之循环链表

为了方便，我这里使用带头结点的单链表来构建循环链表，至于单链表带不带头结点的异同，我在前面的线性表之链表那篇文章中已经做过分析，就不再赘述。

• [Leetcode][python]Merge k Sorted Lists/合并K个排序链表

用一个大小为K的最小堆（用优先队列+自定义降序实现）(优先队列就是大顶堆，队头元素最大,自定义为降序后，就变成小顶堆，队头元素最小)，先把K个链表的头结点放入堆...

• 不仅游戏会坑人，来看看LeetCode出题人是怎么埋坑的

今天是LeetCode专题的第35篇文章，上一篇文章当中我们一口气肝了三题，不知道大家感觉怎么样？今天我们来放松一下，看一道相对比较简单也比较有趣的问题。

• LeetCode 82，考察你的基本功，在有序链表中删除重复元素II

今天是LeetCode专题的第51篇文章，我们来看LeetCode第82题，删除有序链表中的重复元素II(Remove Duplicates from Sort...

Java布道者