引言
在计算机科学中，数据结构是存储、组织数据的方式。而链表，作为一种基础而强大的数据结构，因其独特的特性，在多种算法和应用场景中拥有不可替代的地位。
什么是链表，为什么要使用链表
链表（Linked List）是一种线性表，但与数组不同的是，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的数据域和一个指向下一个元素的指针（或链接）组成。正因为这种独特的存储结构，链表显示出了在插入和删除操作上的天然优势。
那么，为什么我们需要链表呢？首先，链表提供了一种灵活的内存管理方式。不同于数组需要一块连续的内存空间，链表通过指针将零散的内存块串联起来使用，这在处理动态数据时显示出极大的优势。其次，链表在添加或删除元素时，不需要移动其他元素，相比数组在这些操作上更高效。
链表与数组的对比：优缺点分析，适用场景
尽管链表在某些方面比数组高效，但这并不意味着它们总是更好的选择。下面是链表和数组的一些核心对比：
- 内存分配：数组需要一块连续的内存空间，而链表的元素可以分散在内存的任何地方，通过指针连接。
- 性能：数组在随机访问数据时更高效，因为可以直接计算出元素的存储位置。而链表在添加和删除元素时，特别是在列表的开头和中间，通常表现得更好，因为不需要移动其他元素。
- 内存利用：链表可以更好地利用内存，因为它不需要在创建时就确定大小，并且可以扩展到所有可用的内存，而数组在初始化时需要确定大小，可能会浪费内存或需要调整大小。
- 适用场景：
- 数组适用于需要频繁访问元素，元素数量固定或变化不大的场景。
- 链表适合元素数量频繁变动，特别是需要频繁进行添加和删除操作的场景。
2、链表的基本概念
链表的定义
链表是一种在物理上非连续、非顺序的数据结构，由一系列节点（Node）组成。每个节点包括两个部分：一部分是存储数据的数据域，另一部分是指向下一个节点的指针域。这种结构允许数据在内存中分散存放，通过指针连接成一个链式的结构。
链表与数组的最大区别在于，数组在内存中是顺序存储的，而链表则是随机存取。这种存储方式让链表在插入和删除数据时能更高效，因为这些操作不需要像数组那样移动其余元素。
链表的类型
-
单向链表：最基本的链表结构，每个节点只有一个指针指向下一个节点，最后一个节点指向一个空值，表示链表的结束。
![ ][nbsp] -
双向链表：每个节点有两个指针，一个指向下一个节点，一个指向前一个节点。这种结构使得从两个方向遍历链表成为可能，提高了某些情况下的效率。
![ ][nbsp 1] -
循环链表：与单向链表类似，但是最后一个节点不是指向空值，而是指回链表的第一个节点，形成一个环。循环链表的变种包括循环双向链表，即双向链表的最后一个节点指向第一个节点，第一个节点也指向最后一个节点。
![ ][nbsp 2]
节点的结构
节点是构成链表的基本单位，每个节点由数据域和指针域组成。
- 数据域：存储数据的地方，可以是任意类型的数据。
- 指针域：存储指向下一个节点的指针（在双向链表中还会有指向上一个节点的指针）。
通过这种方式，链表中的每个节点都连接到下一个节点，形成一条链。这种结构使得链表能在不重新分配整个数据结构的情况下，动态地插入和删除节点。
3.链表的操作
链表是一种常见的数据结构，用于存储元素的集合，但与数组不同，链表中的元素在内存中不必连续存放。链表的每个元素都包含了指向下一个元素的指针，这使得链表在插入和删除操作上比数组有优势。
创建链表
-
如何初始化一个链表
在Java中，可以通过创建一个链表类，并在该类中定义一个内部节点类
Node来初始化链表。每个Node包含数据和指向下一个节点的指针。 -
代码示例
class LinkedList { Node head; // 链表头 class Node { int data; Node next; // 节点构造函数 Node(int d) { data = d; next = null; } } }
插入操作
-
在链表头部插入
在链表的头部插入元素意味着将新元素作为链表的第一个元素。
-
在链表中间插入
在链表的中间插入元素意味着在指定的位置或者在给定的节点之后插入新元素。
-
在链表尾部插入
在链表的尾部插入元素即将新元素添加到链表的末尾。
-
代码示例
public void insertAtStart(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } public void insertAfter(Node prevNode, int data) { if (prevNode == null) { System.out.println("Previous node cannot be null"); return; } Node newNode = new Node(data); newNode.next = prevNode.next; prevNode.next = newNode; } public void insertAtEnd(int data) { Node newNode = new Node(data); if (head == null) { head = new Node(data); return; } newNode.next = null; Node last = head; while (last.next != null) { last = last.next; } last.next = newNode; }
删除操作
-
删除指定元素
删除链表中值为特定值的节点。
-
删除头部元素
删除链表的第一个元素。
-
删除尾部元素
删除链表的最后一个元素。
-
代码示例
public void deleteByKey(int key) { Node temp = head, prev = null; if (temp != null && temp.data == key) { head = temp.next; return; } while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } if (temp == null) return; prev.next = temp.next; } public void deleteAtStart() { if (head != null) { head = head.next; } } public void deleteAtEnd() { if (head == null || head.next == null) { head = null; return; } Node temp = head; while (temp.next.next != null) temp = temp.next; temp.next = null; }
查找操作
-
查找元素是否存在
检查链表中是否存在某个元素。
-
查找元素的位置
查找特定元素在链表中的位置。
-
代码示例
public boolean search(int key) { Node current = head; while (current != null) { if (current.data == key) return true; current = current.next; } return false; }
链表的遍历
-
顺序遍历
从头到尾遍历链表中的每个元素。
-
代码示例
public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data + " "); tnode = tnode.next; } } -
逆序遍历（如果是双向链表）
如果链表是双向链表，则可以从尾部到头部逆向遍历元素。
链表是基础数据结构之一，掌握其操作对于理解更复杂的数据结构非常重要。
4. 链表的高级操作
链表反转
思路解析
链表反转涉及到改变链表节点的指向。遍历链表，将每个节点的next指针指向它的前一个节点。为此，你需要维护两个指针：当前节点和它的前一个节点。
代码示例
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
链表中环的检测
快慢指针法
快慢指针法能够检测链表中是否存在环。快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，快慢指针最终会相遇。
代码示例
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
合并两个有序链表
思路解析
创建一个新的链表头节点，然后逐个比较两个链表中的节点值，将较小的节点连接到新链表上，并移动相应的指针，直到某一个链表为空，然后将非空链表的剩余部分连接到新链表的末尾。
代码示例
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
找出链表的中间节点
快慢指针法
快慢指针法同样适用于找出链表的中间节点。快指针一次移动两步，慢指针一次移动一步。当快指针到达链表末尾时，慢指针正好在链表的中间。
代码示例
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
5. 链表的应用场景
![ ][nbsp 3]
栈的实现
栈是一种后进先出（LIFO）的数据结构，可以使用链表来实现。链表的头部作为栈顶，因为这样可以在O(1)时间复杂度内完成push和pop操作。
代码示例
class Node {
int value;
Node next;
Node(int value) { this.value = value; }
}
class Stack {
private Node top;
public boolean isEmpty() {
return top == null;
}
public void push(int value) {
Node newNode = new Node(value);
newNode.next = top;
top = newNode;
}
public int pop() {
if (isEmpty()) throw new EmptyStackException();
int value = top.value;
top = top.next;
return value;
}
public int peek() {
if (isEmpty()) throw new EmptyStackException();
return top.value;
}
}
队列的实现
队列是一种先进先出（FIFO）的数据结构，可以通过带有头尾指针的链表来实现。链表的尾部作为队列的尾部用于插入，头部作为队列的头部用于删除。
代码示例
class Node {
int value;
Node next;
Node(int value) { this.value = value; }
}
class Queue {
private Node head, tail;
public boolean isEmpty() {
return head == null;
}
public void enqueue(int value) {
Node newNode = new Node(value);
if (isEmpty()) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}
public int dequeue() {
if (isEmpty()) throw new NoSuchElementException();
int value = head.value;
head = head.next;
if (head == null) {
tail = null;
}
return value;
}
public int peek() {
if (isEmpty()) throw new NoSuchElementException();
return head.value;
}
}
图的表示
链表也可以用来表示图。对于图中的每个顶点，可以使用链表来存储与它相邻的顶点。这种表示方法特别适合于表示稀疏图。
代码示例
这里以邻接表的形式表示无向图为例：
import java.util.LinkedList;
import java.util.List;
class Graph {
private int V; // 顶点数目
private List<Integer>[] adj; // 邻接表
Graph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<>();
}
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v); // 无向图是双向的
}
// 与v相邻的所有顶点
Iterable<Integer> adj(int v) {
return adj[v];
}
}
这些例子展示了链表在实现数据结构和表示结构化数据时的灵活性和功用。
6. 链表的问题与练习
链表作为一种基础且重要的数据结构，在软件开发和算法面试中经常遇到。
下面是一些常见的链表面试题及其解析。
常见面试题解析
-
反转链表
反转链表是最基础也是最常见的链表问题之一，要求改变链表的方向。
Java解法示例：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode nextTemp = current.next; current.next = prev; prev = current; current = nextTemp; } return prev; } -
链表中环的检测
检测一个链表是否有环是另一个经典问题。
Java解法示例：
public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } -
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。
Java解法示例：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }
练习题目推荐
以下是一些推荐的链表练习题，你可以在各大在线平台如LeetCode、HackerRank等找到这些题目并进行练习：
- 移除链表元素：移除链表中等于给定值
val的所有节点。 - 奇偶链表：给定一个单链表，把所有的奇数位置的节点组成一个链表和偶数位置的节点组成另一个链表，然后将它们连接起来。
- 两数相加：给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
- 环形链表 II：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回
null。 - 相交链表：编写一个程序，找到两个单链表相交的起始节点。
如果没有思路，不知道该如何去写，可以参考一下别人是如何实现的：最新：Java 离线版 LeetCode 累计 3000+ 刷题笔记
最后说一句(求关注，求赞，别白嫖我)
最近无意间获得一份阿里大佬写的刷题笔记和面经，一下子打通了我的任督二脉，进大厂原来没那么难。
这是大佬写的，7701页的阿里大佬写的刷题笔记，让我offer拿到手软
求一键三连：点赞、分享、收藏
点赞对我真的非常重要！在线求赞，加个关注我会非常感激！@小郑说编程
[nbsp]: https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2F%2Fwww.feiz.vip%2Fimages%2Fother_images%2Ficon%2Fdanxiang_LinkedList.png&pos_id=img-Fj8JFqP6-1710246015766)
[nbsp 1]: https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2F%2Fwww.feiz.vip%2Fimages%2Fother_images%2Ficon%2Fshuangxiang_LinkedList.png&pos_id=img-oMTNH7OX-1710246016117)
[nbsp 2]: https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2F%2Fwww.feiz.vip%2Fimages%2Fother_images%2Ficon%2Fshuangxiang_xunhuan_LinkedList.png&pos_id=img-JjhSqNlc-1710246016298)
[nbsp 3]: https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2F%2Fwww.feiz.vip%2Fimages%2Fother_images%2Ficon%2Fstack_queue.png&pos_id=img-X8laD9GU-1710246016469)