数据结构：链表

---

链表

一，概述

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的每个元素不需要在内存中连续存放，它通过指针将元素串联起来。

链表可以分为单向链表、双向链表和循环链表三种类型。

1. 单向链表：每个节点包含一个数据元素和一个指向下一个节点的指针。单向链表只能从头节点开始遍历，逐个访问链表中的节点。
2. 双向链表：每个节点包含一个数据元素、一个指向前一个节点的指针和一个指向下一个节点的指针。双向链表可以从任意节点开始遍历，向前或向后访问链表中的节点。
3. 循环链表：每个节点包含一个数据元素和一个指向下一个节点的指针，尾节点的指针指向头节点，形成一个环。循环链表可以从任意节点开始遍历，逐个访问链表中的节点。

链表的优点包括：

1. 动态分配内存：链表的大小不需要预先确定，可以根据需要动态分配内存空间。
2. 插入和删除效率高：在已知某一节点位置的情况下，链表的插入和删除操作仅需修改相邻节点的指针，时间复杂度为O(1)。
3. 空间利用率高：链表中的元素可以分散在内存中，不需要连续存放，空间利用率高。

然而，链表也存在一些缺点：

1. 顺序访问效率低：链表的访问只能从头节点开始逐个遍历，时间复杂度为O(n)。
2. 需要额外空间存储指针：每个节点需要额外存储一个指向下一个节点的指针，相对于数组来说，空间开销较大。
3. 不支持随机访问：链表不支持像数组那样的随机访问，只能从头节点开始逐个遍历。

在实际应用中，链表常用于需要频繁插入和删除操作的场景，如操作系统的任务调度、内存管理等。

简介：

• 链表是一种线性数据结构，用于存储有序的元素集合。
• 链表由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的引用（指针）。
• 链表中的元素可以通过遍历链表来访问，每个节点都有一个指向下一个节点的引用，直到达到链表的末尾。
• 链表可以分为单向链表、双向链表和循环链表三种类型。单向链表中的节点只有一个指向下一个节点的引用，双向链表中的节点有一个指向前一个节点和一个指向下一个节点的引用，循环链表中的最后一个节点指向头节点，形成一个环。

图示：

单向链表：

+-----+   +-----+   +-----+
| 1   |-->| 2   |-->| 3   |-->null
+-----+   +-----+   +-----+
1
2
3

双向链表：

+-----+   +-----+   +-----+
| 1   |<--| 2   |<--| 3   |
+-----+   +-----+   +-----+
1
2
3

循环链表：

+-----+   +-----+   +-----+
| 1   |-->| 2   |-->| 3   |-->| 1   |-->...
+-----+   +-----+   +-----+   +-----+
1
2
3

示例：
下面是一个简单的Java代码示例，展示如何创建和使用单向链表：

public class LinkedListExample {
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            next = null;
        }
    }
    static class LinkedList {
        Node head;
        void add(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                head = newNode;
            } else {
                Node current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
            }
        }
        void print() {
            Node current = head;
            while (current != null) {
                System.out.print(current.data + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.print(); // 输出：1 2 3
    }
}
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

二，添加数据

在Java中，链表是一种常见的数据结构，它可以有效地在任何位置插入和删除元素。Java的java.util包中提供了LinkedList类来实现链表。

下面是一个示例，展示如何使用LinkedList类来添加数据：

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个空的链表
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加数据到链表
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");
        linkedList.add("E");

        // 输出链表中的数据
        System.out.println("链表中的数据: " + linkedList);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上面的代码创建了一个空的链表，并使用add方法向链表中添加了几个字符串元素。最后，它打印出链表中的所有元素。

此外，还可以使用add(int index, E element)方法在链表的特定位置插入元素：

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个空的链表
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加数据到链表
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");
        linkedList.add("E");

        // 在链表的第三个位置插入元素"F"
        linkedList.add(2, "F");

        // 输出链表中的数据
        System.out.println("链表中的数据: " + linkedList);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

上面的代码在链表的第三个位置插入了字符串"F"，然后打印出链表中的所有元素。

三，删除数据

在Java中，链表是一种常见的数据结构，可以有效地在任何位置插入和删除元素。Java的java.util包中提供了LinkedList类来实现链表。

下面是一个示例，展示如何使用LinkedList类来删除数据：

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个链表
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加数据到链表
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");
        linkedList.add("E");

        // 输出链表中的数据
        System.out.println("链表中的数据: " + linkedList);

        // 删除链表中的元素"C"
        linkedList.remove("C");

        // 输出删除元素后的链表
        System.out.println("删除元素后的链表: " + linkedList);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面的代码创建了一个链表，并使用add方法向链表中添加了几个字符串元素。然后，它使用remove方法删除了链表中的一个特定元素。最后，它打印出删除元素后的链表。

此外，还可以使用remove(int index)方法根据索引删除链表中的元素：

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个链表
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加数据到链表
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");
        linkedList.add("E");

        // 输出链表中的数据
        System.out.println("链表中的数据: " + linkedList);

        // 删除链表中的第三个元素
        linkedList.remove(2);

        // 输出删除元素后的链表
        System.out.println("删除元素后的链表: " + linkedList);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面的代码根据索引删除了链表中的一个元素，然后打印出删除元素后的链表。