Java实现详解——如何实现链表数据结构|极客教程

Java实现详解——如何实现链表数据结构

引言

链表是一种常用的数据结构，它的特点是每个元素都存储了下一个元素的地址，从而使得元素之间可以通过地址进行快速的查找和插入操作。在Java中，链表的实现可以基于节点的类进行构建，节点类包含了一个数据域和一个指向下一个节点的引用。

节点类的设计与实现

首先我们来设计节点类Node，节点类具有两个成员变量，一个存储数据的值data，一个存储下一个节点的引用next。

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

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

链表类的设计与实现

接下来我们创建链表类LinkedList，链表类具有一个头节点head，每次插入或删除操作都需要从头节点开始进行。

public class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }

    // 在链表末尾插入一个节点
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 删除指定数值的节点
    public void delete(int data) {
        if (head == null) {
            return;
        }
        if (head.data == data) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data != data) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
    }

    // 打印链表中的所有元素
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

链表操作示例

下面我们以一个示例来演示如何使用LinkedList类进行链表操作：

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // 在链表末尾插入节点
        list.insert(1);
        list.insert(2);
        list.insert(3);

        // 打印链表
        list.display();  // Output: 1 2 3

        // 删除节点
        list.delete(2);

        // 打印删除节点后的链表
        list.display();  // Output: 1 3
    }
}