本博客总结了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); // 1
newNode.next = this.head; // 2
this.head = newNode; // 3
this.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不为key
while (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. 创建LinkedList
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()); // Banana
System.out.println("getLast(): " + linkedList.getLast()); // Cherry
System.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")); // true
System.out.println("size(): " + linkedList.size()); // 1
System.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
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
}
}
更多方法请参考官方api文档：LinkedList (Java Platform SE 8 )
结语
链表的理解难度算是数据结构当中比较难的了，oj题更是，对于初学者来说不建议死磕。可以等熟练了做专项练习，毕竟链表也是笔试的重难点了，难题基本都有它的影子（博主本人也被这么的不轻......）。
OK，那么本博客到此结束，下篇我们讲栈和队列，它们就友好多了。
觉得有帮助不妨点个赞，我们下期见！(*´∀ ˋ*)