Java手写链表和案例拓展

Java手写链表和案例拓展

思维导图

以下是思维导图，用于解释链表的实现思路和原理。

摘要

链表是一种常用的数据结构，它由一系列的节点组成，每个节点包含一个数据域和一个指向下一个节点的指针。链表相比于数组具有动态插入和删除节点的优势，但访问节点的时间复杂度较高。

在创建链表时，我们需要定义一个节点类，包含数据域和指针域。然后，创建一个链表类，包含一个头节点，用于管理链表的各种操作。

链表的基本操作包括在链表末尾添加节点、在链表头部插入节点、删除指定值的节点和打印链表。在添加节点时，需要判断链表是否为空，如果为空，则将新节点设置为头节点；如果链表不为空，则遍历到链表末尾，将新节点添加到末尾节点的next指针上。在插入节点时，只需将新节点的next指针指向当前的头节点，并将新节点设置为头节点。在删除节点时，需要判断链表是否为空，如果为空，则直接返回；如果头节点为要删除的节点，则将头节点的next指针指向下一个节点；否则，遍历链表找到要删除节点的前一个节点，将前一个节点的next指针指向要删除节点的下一个节点。打印链表只需遍历链表，依次输出每个节点的数据。

除了基本操作外，链表还可以进行拓展，例如链表的反转。链表的反转可以通过遍历链表，将每个节点的next指针指向前一个节点，最终将头节点设置为链表的末尾节点，实现链表的反转。

链表是一种常见的数据结构，可以根据需要自定义链表的功能，例如实现栈、队列等数据结构。掌握链表的基本操作和拓展应用，对于理解和应用其他数据结构和算法都具有重要意义。

实现的详细介绍和详细步骤

1. 创建节点类

首先，我们需要创建一个节点类，表示链表中的每个节点。节点类包含一个数据域和一个指向下一个节点的指针。

public class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
1
2
3
4
5
6
7
8
9

2. 创建链表类

接下来，我们创建一个链表类，用于管理链表的各种操作。链表类包含一个头节点，表示链表的起始位置。

public class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }
}
1
2
3
4
5
6
7

3. 在链表末尾添加节点

现在，我们来实现在链表末尾添加节点的操作。首先，判断链表是否为空，如果为空，则将新节点设置为头节点。如果链表不为空，我们需要遍历到链表的末尾，然后将新节点添加到末尾节点的next指针上。

public void append(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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 在链表头部插入节点

接下来，我们实现在链表头部插入节点的操作。我们只需要将新节点的next指针指向当前的头节点，并将新节点设置为头节点。

public void prepend(int data) {
    Node newNode = new Node(data);

    newNode.next = head;
    head = newNode;
}
1
2
3
4
5
6

5. 删除指定值的节点

现在，我们来实现删除链表中指定值的节点的操作。首先，判断链表是否为空，如果为空，则直接返回。然后，判断头节点是否为要删除的节点，如果是，则将头节点的next指针指向下一个节点。如果头节点不是要删除的节点，我们需要遍历链表，找到要删除的节点的前一个节点，然后将前一个节点的next指针指向要删除节点的下一个节点。

public void delete(int data) {
    if (head == null) {
        return;
    }

    if (head.data == data) {
        head = head.next;
        return;
    }

    Node current = head;
    while (current.next != null) {
        if (current.next.data == data) {
            current.next = current.next.next;
            return;
        }
        current = current.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6. 打印链表

最后，我们实现打印链表的操作。我们只需要遍历链表，依次输出每个节点的数据。

public void print() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}
1
2
3
4
5
6
7
8

总结

通过以上步骤，我们成功实现了手写链表的基本操作。链表是一种常用的数据结构，具有动态插入和删除节点的优势。在实际开发中，我们可以根据需要自定义链表的功能，例如实现栈、队列等数据结构。

拓展案例：链表反转

下面是一个链表反转的拓展案例，展示了如何使用链表的基本操作来实现链表反转。

public void reverse() {
    Node previous = null;
    Node current = head;
    Node next = null;

    while (current != null) {
        next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    head = previous;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

以上是链表反转的代码，通过遍历链表，将每个节点的next指针指向前一个节点，最终将头节点设置为链表的末尾节点，实现了链表的反转。