关于 Java 的数据结构链表

关于 Java 的数据结构链表完整攻略

简介

链表是一种线性数据结构，是由多个节点构成的数据集合。每个节点包含两个部分，一个是数据，一个是指向下一个节点的引用。链表有很多种不同的类型，包括单向链表、双向链表、循环链表等等。在 Java 中，我们通常使用单向链表或双向链表。

实现单向链表

单向链表是链表中最简单的类型，每个节点只包含对下一个节点的引用。以下是一个简单的示例代码，实现单向链表：

public class Node {
    int data; //节点数据
    Node next; //指向下一个节点的引用

    public Node(int data) {
        this.data = data;
        next = null;
    }
}

public class LinkedList {
    Node head; //链表头节点

    public LinkedList() {
        head = null;
    }

    //在链表末尾添加节点
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    //打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

通过创建一个 Node 类表示节点，再通过 LinkedList 类维护链表，我们可以很容易地在链表末尾添加节点，并打印整个链表。

实现双向链表

双向链表是每个节点除了包含对下一个节点的引用外，还包含对上一个节点的引用。这个额外的步骤让我们可以在链表中双向遍历。同样，以下是一个示例代码，实现双向链表：

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

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

public class LinkedList {
    Node head;

    public LinkedList() {
        head = null;
    }

    //在链表末尾添加节点
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        Node newNode = new Node(data);
        current.next = newNode;
        newNode.prev = current;
    }

    //打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

通过添加 prev 对上一个节点的引用，我们可以双向遍历链表。

总结

Java 中的链表是一个非常重要的数据结构，通常用于解决需要快速增删元素的问题。虽然实现起来可能有些困难，但是通过理解节点引用和链表指针，我们可以很容易地实现一个高效的链表。如有需要，我们可以在代码中维护更多的数据，例如链表长度和当前节点位置等等。

阅读剩余 58%