怎么在Java中实现LinkedList数据结构

1. 引言

链表（LinkedList）是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。与数组不同，链表在内存中不需要连续的空间，因此可以更灵活地管理内存。链表的主要优点是插入和删除操作的效率较高，而缺点是访问元素的效率较低。

在Java中，LinkedList是java.util包中的一个类，它实现了List和Deque接口。本文将介绍如何在Java中手动实现一个简单的单向链表（Singly Linked List）和双向链表（Doubly Linked List）。

2. 单向链表的实现

2.1 节点类

首先，我们需要定义一个节点类Node，它包含两个部分：数据和指向下一个节点的引用。

class Node<T> {
    T data;
    Node<T> next;

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

2.2 链表类

接下来，我们定义一个链表类SinglyLinkedList，它包含一个指向链表头部的引用head，并提供一些基本的操作，如插入、删除和遍历。

class SinglyLinkedList<T> {
    private Node<T> head;

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

    // 在链表头部插入节点
    public void insertAtHead(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
    }

    // 在链表尾部插入节点
    public void insertAtTail(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node<T> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 删除链表头部节点
    public void deleteAtHead() {
        if (head == null) {
            return;
        }
        head = head.next;
    }

    // 删除链表尾部节点
    public void deleteAtTail() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node<T> current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
    }

    // 遍历链表并打印节点数据
    public void printList() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

2.3 测试单向链表

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
        list.insertAtHead(3);
        list.insertAtHead(2);
        list.insertAtHead(1);
        list.insertAtTail(4);
        list.printList(); // 输出: 1 -> 2 -> 3 -> 4 -> null

        list.deleteAtHead();
        list.printList(); // 输出: 2 -> 3 -> 4 -> null

        list.deleteAtTail();
        list.printList(); // 输出: 2 -> 3 -> null
    }
}

3. 双向链表的实现

3.1 节点类

双向链表的节点类Node需要包含两个引用：一个指向下一个节点，另一个指向前一个节点。

class Node<T> {
    T data;
    Node<T> next;
    Node<T> prev;

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

3.2 链表类

双向链表类DoublyLinkedList与单向链表类似，但需要处理前后两个方向的引用。

class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 在链表头部插入节点
    public void insertAtHead(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // 在链表尾部插入节点
    public void insertAtTail(T data) {
        Node<T> newNode = new Node<>(data);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 删除链表头部节点
    public void deleteAtHead() {
        if (head == null) {
            return;
        }
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    // 删除链表尾部节点
    public void deleteAtTail() {
        if (tail == null) {
            return;
        }
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
    }

    // 遍历链表并打印节点数据
    public void printList() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

3.3 测试双向链表

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        list.insertAtHead(3);
        list.insertAtHead(2);
        list.insertAtHead(1);
        list.insertAtTail(4);
        list.printList(); // 输出: 1 <-> 2 <-> 3 <-> 4 <-> null

        list.deleteAtHead();
        list.printList(); // 输出: 2 <-> 3 <-> 4 <-> null

        list.deleteAtTail();
        list.printList(); // 输出: 2 <-> 3 <-> null
    }
}

4. 总结

本文介绍了如何在Java中手动实现单向链表和双向链表。通过定义节点类和链表类，我们可以实现链表的基本操作，如插入、删除和遍历。链表是一种非常灵活的数据结构，适用于需要频繁插入和删除操作的场景。在实际开发中，Java标准库中的LinkedList类已经提供了丰富的功能，但在某些情况下，手动实现链表可以帮助我们更好地理解其工作原理。