数据结构中第05节：链表

数据结构中的链表是一种重要的数据组织方式，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的灵活性和动态性使其在很多实际应用中非常有用，包括生活中的一些场景和游戏中。

Demo1

1. 排队系统：比如在银行、超市或电影院，顾客可以被视为链表的节点，每个顾客后面跟着下一个顾客，形成一条队列。当有人离开队伍时，下一个顾客就会自动向前移动。

2. 任务调度：在操作系统中，任务调度可以用链表来实现，每个任务是一个节点，系统通过指针来管理任务的执行顺序。

3. 社交媒体：在社交媒体中，用户的好友列表可以看作是一个链表，每个用户节点指向其下一个好友。

Demo2

1. 游戏角色队列：在角色扮演游戏中，玩家的队伍可以是一个链表，每个角色是一个节点，可以随时添加或删除队伍成员。

2. 任务列表：在某些游戏中，玩家的任务列表可以是一个链表，每个任务是一个节点，玩家可以按顺序完成或跳过某些任务。

3. 战斗队列：在回合制战斗中，战斗队列可以是链表，每个单位是一个节点，根据行动顺序排列。

Java_Code

下面是一个简单的Java单向链表实现，包括节点类和链表类，以及一些基础操作的示例：

// 节点类
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

// 链表类
public class LinkedList {
    private ListNode head; // 链表的头节点

    public LinkedList() {
        head = null;
    }

    // 在链表末尾添加节点
    public void add(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 打印链表
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 从链表中删除特定值的节点
    public void remove(int val) {
        ListNode current = head;
        ListNode prev = null;

        while (current != null) {
            if (current.val == val) {
                if (prev == null) {
                    head = current.next; // 删除头节点
                } else {
                    prev.next = current.next; // 删除中间或尾部节点
                }
                return;
            }
            prev = current;
            current = current.next;
        }
    }
}

// 测试类
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.printList(); // 输出：1 -> 2 -> 3 -> null

        list.remove(2);
        list.printList(); // 输出：1 -> 3 -> null
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

这段代码展示了链表的基本操作：添加节点、打印链表和删除特定值的节点。在实际应用中，链表可以根据需要进行扩展，比如实现双向链表、循环链表等更复杂的数据结构。

单向链表、双向链表和环形链表是链表数据结构的几种变体，每种链表都有其特定的应用场景和特点。

单向链表（Singly Linked List）

单向链表是最基础的链表形式，每个节点包含数据部分和一个指向下一个节点的指针。它只能从头部开始，沿着指针方向遍历到尾部。

特点：

• 插入和删除操作相对简单，只需要改变指针的指向。
• 不能从尾部开始反向遍历，需要从头节点开始。

双向链表（Doubly Linked List）

双向链表的每个节点除了包含数据和一个指向下一个节点的指针外，还包含一个指向前一个节点的指针。这使得我们可以从任一节点开始，向前或向后遍历整个链表。

特点：

• 可以进行双向遍历，增加了灵活性。
• 插入和删除操作稍微复杂，需要同时更新两个指针。
• 每个节点需要额外的空间来存储指向前一个节点的指针。

环形链表（Circular Linked List）

环形链表是链表的另一种形式，其中尾节点的指针指向头节点，形成一个闭环。环形链表可以是单向的，也可以是双向的。

特点：

• 可以方便地实现循环队列等数据结构。
• 插入和删除操作可能需要特殊处理，以保持环的连续性。
• 遍历时需要注意循环条件，避免无限循环。

应用场景

• 单向链表：适用于实现栈、队列等线性数据结构，以及在不需要反向遍历的场景下使用。
• 双向链表：适用于需要双向遍历的场景，如某些类型的队列和某些复杂的数据操作。
• 环形链表：适用于需要循环遍历或实现循环缓冲区的场景。

Java源代码示例

双向链表的Java实现

class DoublyListNode {
    int data;
    DoublyListNode prev;
    DoublyListNode next;

    DoublyListNode(int data) {
        this.data = data;
        prev = null;
        next = null;
    }
}

public class DoublyLinkedList {
    DoublyListNode head, tail;

    public void add(int data) {
        DoublyListNode newNode = new DoublyListNode(data);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public void printList() {
        DoublyListNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

环形链表的Java实现

public class CircularLinkedList {
    ListNode head = null;

    public void insert(int data) {
        ListNode newNode = new ListNode(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            ListNode temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            newNode.next = head;
            temp.next = newNode;
        }
    }

    public void printList() {
        if (head != null) {
            ListNode current = head;
            do {
                System.out.print(current.val + " ");
                current = current.next;
            } while (current != head);
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

在这些示例中，我们可以看到双向链表和环形链表的实现方式。双向链表通过维护前驱指针增加了操作的灵活性，而环形链表通过将尾节点的指针指向头节点形成了一个循环结构。每种链表都有其特定的使用场景和优势。