Java 与数据结构（2）：链表网站首页 其他

Java 与数据结构（2）：链表

暗星涌动 2024-06-17 10:26:03

简介Java 与数据结构（2）：链表

一、链表

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。链表中的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针指向 NULL。

相比于数组，链表的优点是可以动态地分配内存，不需要预先知道存储元素的个数，而且插入和删除操作的时间复杂度为 O(1)。

链表常见的类型有单向链表、双向链表和循环链表。单向链表每个节点只包含一个指向下一个节点的指针，而双向链表每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。循环链表的尾节点的指针指向头节点，形成一个环。

链表的缺点是访问元素的时间复杂度为 O(n)，因为需要从头节点开始遍历整个链表。另外，链表的存储空间比数组更大，因为每个节点需要额外的指针空间。

以下是一些链表的常见操作：

遍历链表：从头节点开始，依次访问每个节点，直到尾节点。
插入节点：将新节点插入到链表中的指定位置，需要修改相应节点的指针。
删除节点：将指定节点从链表中删除，需要修改相应节点的指针。
反转链表：将链表中的节点顺序翻转，需要修改相应节点的指针。
合并链表：将两个有序链表合并成一个有序链表，需要比较节点的值来确定插入顺序。

二、Java 示例

在 Java 中，可以使用自定义类来实现链表数据结构。一般情况下，链表由节点组成，每个节点包含元素值和指向下一个节点的指针。以下是一个简单的单向链表的 Java 代码示例：

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {
    private ListNode head;

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

    public void addNode(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }

    public void deleteNode(int val) {
        if (head == null) {
            return;
        }
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode curr = head;
        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
                return;
            }
            curr = curr.next;
        }
    }

    public void printList() {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.printList(); // 输出：1 2 3
        list.deleteNode(2);
        list.printList(); // 输出：1 3
    }
}

这个示例中，ListNode 表示链表中的节点，包含一个整数值和一个指向下一个节点的指针；LinkedList 表示单向链表，包含一个头节点和一些操作方法，如添加节点、删除节点和遍历链表；Main 类是程序的入口，创建了一个链表对象，添加了三个节点，然后删除了一个节点，最后输出链表中剩余节点的值。