【Java】链表（LinkedList）（图文版）

本博客总结了Java当中链表的实现，以及相关方法的使用，在最后附带了一些常见链表相关处理技巧，希望对你有帮助！

ps：可拷贝到IDEA上自行测试，代码全部完成测试。

一.链表概述

1.什么是链表？

链表（LinkedList） 是一种线性数据结构，由一系列节点（Node） 通过指针（引用）连接而成，每个节点包含两部分：

数据域：存储实际的数据（可以是任意类型）

指针域：存储指向下一个节点（或前一个节点）的引用

顾名思义，就是像链子一样的数据结构，在物理内存上不要求连续，通过引用（Next）套接连接：

想要访问链表元素，只能从头结点进入，顺着链子找到下一个节点，依次访问，直到访问到为节点（Null）

2.链表的分类

链表大致可以分为以下三类：

单链表（Singly Linked List）

双链表（Doubly Linked List）

循环链表（Circular Linked List）

（1）单链表

• 定义：每个节点仅包含一个指向下一个节点的指针（next）。

• 特点：单向遍历，只能从头节点开始访问后续节点。

• 终止条件：最后一个节点的next指向null。

如上图就是一个经典的单链表。

（2）双链表

• 每个节点包含两个指针：next（指向后一个节点）和 prev（指向前一个节点）。

• 特点：支持双向遍历，但需要更多内存存储指针。

（3）循环链表

• 单链表的变种：最后一个节点的next指向头节点。

• 特点：形成一个环，适合需要循环访问的场景。

• 终止条件：遍历时需检查是否回到头节点。

（4）有头/无头指针结构

有头指针结构会有个空的指针作为专门的头指针作为入口，插入只能在头指针之后。

无头指针结构无专门的头指针，以第一个节点作为入口，可以在入口前插入。

有头/无头指针结构与上述3种链表可以任意组合，我们推荐使用有头，因为不需要考虑变更头结点，简化了操作。

为了演示一些错误和注意事项，我们使用无头结构。

3.在集合框架中的位置

属于线性表（List）的一种，能与ArrayList与Stack互转，前提是类型声明为List（之后会介绍）。

4.优缺点

（1）优点

• 高效的增删数据（变动链式关系即可，无需关心空间顺序）
• 动态内存（无需指定大小，因为以节点形式存在）

（2）缺点

• 访问效率低（只能从头访问）
• 内存开销稍大（要存储指针）

二.链表的实现

先简单看一眼Java源码：

不难发现Java使用了内部类的形式存储节点，并且LinkedList这一集合使用的是双向无头链表。

为了便于理解与复现，我们暂且不考虑泛型与io等高阶特性，而使用int存储value。

1.单链表的实现

（1）基本实现

public class MyLinkedListTest {private Node head;    //入口，并非哨兵节点private int size;     //节点数//节点内部类private static class Node {int val;Node next;public Node(int val) {this.val = val;}}//构造方法public MyLinkedListTest() {this.head = null;    //head指向空节点，表示初始化为空this.size = 0;}......

（2）添加元素

//在头部插入
public void addHead(int data) {Node newNode = new Node(data);  // 1newNode.next = this.head;       // 2 this.head = newNode;            // 3this.size++;                    
}

头插示意图：

step1：

step2：

step3：

//在尾部插入
public void addTail(int data) {Node newNode = new Node(data);Node current = this.head;if (head == null) {        //链表为空的情况this.head = newNode;}else{                     //链表不为空的情况while (current.next != null) {current = current.next;}//改链接current.next = newNode;}this.size++;
}

 尾插示意图：

step1：

step2：

step3：

//在指定位置插入
public void addIndex(int index, int data) {//下标合法性判断if (index < 0 || index > size) {        System.out.println("illegal index");return;}Node newNode = new Node(data);//是否头插？if (index == 0) {addHead(data);return;}//是否尾插if (index == size) {addTail(data);return;}Node prev = this.head;Node cur = prev.next;//找位置for (int i = 1; i < index; i++) {prev = cur;cur = cur.next;}//改链接prev.next = newNode;newNode.next = cur;
}

指定位置插入示意图：

（3）遍历输出

public void display() {Node current = head;System.out.print("Head -> ");while (current != null) {System.out.print(current.val + " -> ");current = current.next;}System.out.println("null");
}

（4）删除元素

//删除第一个遇见的元素
public void remove(int key) {if (this.head == null) {return;}if (this.head.val == key) {this.head = this.head.next;}Node prev = this.head;       //当前节点的前驱节点Node cur = prev.next;        //当前节点while (cur != null) {if (cur.val == key) {//改链接prev.next = cur.next;this.size--;return;}//指针遍历prev = cur;cur = cur.next;}System.out.println("not find");
}//删除所有value == key的元素
public void removeAllKey(int key) {if (this.head == null) {return;}//头结点 val == key的情况，循环删除直到头val不为keywhile (head.val == key && head.next != null) {this.head = this.head.next;}//指针遍历Node prev = this.head;Node cur = prev.next;while (cur != null) {if (cur.val == key) {//改链接prev.next = cur.next;cur = cur.next;this.size--;}else {//指针遍历prev = cur;cur = cur.next;}}
}//删除所有元素
public void clean(){this.head = null;this.size = 0;
}

删除元素示意图（cur：当前要删除的元素）：

（5）查找元素

public boolean contains(int key) {Node current = this.head;while (current != null) {if (current.val != key) {current = current.next;continue;}return true;}return false;
}

2.双链表的实现

（1）基本实现

public class MyLinkedList {//节点内部类private static class Node {int data;Node next;Node prev;public Node(int data) {this.data = data;this.next = null;this.prev = null;}}private Node head;private Node tail;private int size;//构造方法public MyLinkedList() {this.head = null;this.tail = null;this.size = 0;}......

（2）添加元素

//头插法
public void addFirst(int data) {Node newNode = new Node(data);//空链表情况下if (this.head == null) {this.head = newNode;this.tail = newNode;}else{//非空链表情况下this.head.prev = newNode;newNode.next = this.head;this.head = newNode;}size++;
}//尾插法，类似头插
public void addLast(int data) {Node newNode = new Node(data);if (this.head == null) {this.head = newNode;this.tail = this.head;}else{this.tail.next = newNode;newNode.prev = this.tail;this.tail = newNode;}size++;
}//辅助方法，寻找下标为index的节点
private Node getNode(int index) {Node temp = this.head;for (int i = 0; i < index; i++) {temp = temp.next;}return temp;
}//按下标插入
public void addAt(int index, int data) {Node newNode = new Node(data);//合法性判断if (index < 0 || index > size) {throw new IndexOutOfBoundsException("bad index");}if (index == 0) {this.addFirst(data);}else if(index == size){this.addLast(data);}else{Node place = getNode(index);//改链接newNode.next = place;newNode.prev = place.prev;place.prev.next = newNode;place.prev = newNode;size++;}
}

添加元素示意图：

（3）删除元素

//删除第一个元素
public void removeFirst(){if (this.head == null) return;if (this.head == tail) {this.head = null;this.tail = null;}else{this.head = this.head.next;this.head.prev = null;}size--;
}//删除最后一个元素
public void removeLast(){if (this.tail == null) return;if (head == tail) {head = null;tail = null;} else {tail = tail.prev;tail.next = null;}size--;
}//删除第一个 data == key 的元素
public void remove(int key){Node cur = this.head;//遍历while(cur != null){//判断是否找到if(cur.data == key){if(this.head == cur){removeFirst();}else if(this.tail == cur){removeLast();}else{//改链接cur.next.prev = cur.prev;cur.prev.next = cur.next;size--;}return;}//指针遍历cur = cur.next;}
}

删除元素示意图：

（4）遍历输出

// 正向遍历打印链表
public void printForward() {Node cur = head;System.out.print("Forward: null <-> ");while (cur != null) {System.out.print(cur.data + " <-> ");cur = cur.next;}System.out.println("null");
}// 反向遍历打印链表
public void printBackward() {Node cur = tail;System.out.print("Backward: null <-> ");while (cur != null) {System.out.print(cur.data + " <-> ");cur = cur.prev;}System.out.println("null");
}

（5）其他

public int getSize() {return size;
}public boolean isEmpty() {return size == 0;
}......

3.循环链表的实现

循环链表就是把尾节点指向头结点，循环链表在实际开发中的使用频率相对较低，这里不过多描述，仅做简单介绍。

class CircularLinkedList {private Node head;private Node tail;privat static class Node {int data;Node next;Node(int data) { this.data = data; }}// 添加节点到尾部public void add(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;tail = newNode;tail.next = head; // 循环指向自身} else {tail.next = newNode;tail = newNode;tail.next = head; // 新尾部指向头}}// 遍历打印public void print() {if (head == null) return;Node current = head;do {System.out.print(current.data + " -> ");current = current.next;} while (current != head); // 终止条件}......}

三.相关oj题

详情请见LeetCode

1.反转一个单链表。

206. 反转链表 - 力扣（LeetCode）

2. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

876. 链表的中间结点 - 力扣（LeetCode）

3. 输入两个链表，找出它们的第一个公共结点。

160. 相交链表 - 力扣（LeetCode）

4. 给定一个链表，判断链表中是否有环。

141. 环形链表 - 力扣（LeetCode）

四.LinkedList的使用

请参考如下代码：

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;public class LinkedListDemo {public static void main(String[] args) {// 1. 创建LinkedListLinkedList<String> linkedList = new LinkedList<>();// 2. 添加元素linkedList.add("Apple");      // 添加到末尾linkedList.addFirst("Banana");// 添加到头部linkedList.addLast("Cherry"); // 添加到末尾（同add）linkedList.add(1, "Durian");  // 插入到指定位置System.out.println("初始化链表: " + linkedList);// 输出: [Banana, Durian, Apple, Cherry]// 3. 访问元素System.out.println("\n访问元素演示:");System.out.println("getFirst(): " + linkedList.getFirst()); // BananaSystem.out.println("getLast(): " + linkedList.getLast());   // CherrySystem.out.println("get(2): " + linkedList.get(2));         // Apple// 4. 删除元素System.out.println("\n删除操作演示:");linkedList.removeFirst();     // 删除头部linkedList.removeLast();      // 删除尾部linkedList.remove("Apple");   // 删除指定元素System.out.println("删除后: " + linkedList); // [Durian]// 5. 其他常用方法System.out.println("\n其他方法演示:");System.out.println("contains('Durian'): " + linkedList.contains("Durian")); // trueSystem.out.println("size(): " + linkedList.size());                   // 1System.out.println("indexOf('Durian'): " + linkedList.indexOf("Durian"));       // 0// 6. 遍历方式System.out.println("\n遍历演示:");System.out.println("1. for-each循环:");for (String fruit : linkedList) {System.out.print(fruit + " ");}System.out.println("\n\n2. 迭代器遍历:");Iterator<String> it = linkedList.iterator();while (it.hasNext()) {System.out.print(it.next() + " ");}}
}

更多方法请参考官方api文档：LinkedList (Java Platform SE 8 )

结语

链表的理解难度算是数据结构当中比较难的了，oj题更是，对于初学者来说不建议死磕。可以等熟练了做专项练习，毕竟链表也是笔试的重难点了，难题基本都有它的影子（博主本人也被这么的不轻......）。

OK，那么本博客到此结束，下篇我们讲栈和队列，它们就友好多了。

觉得有帮助不妨点个赞，我们下期见！(*´∀ ˋ*)