链表的底层实现（Java版）（单向，双向，循环）

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。链表有多种类型，包括单向链表、双向链表和循环链表。本文将介绍这三种链表的底层实现，主要使用Java语言进行示例。

1. 单向链表

单向链表是最基本的链表结构，每个节点只包含一个指向下一个节点的引用。下面是单向链表的基本实现：

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

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

class SinglyLinkedList {
    private Node head; // 链表的头节点

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

    // 在链表尾部添加节点
    public void add(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;
        }
    }

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

2. 双向链表

双向链表的每个节点都包含两个引用：一个指向下一个节点，另一个指向前一个节点。这使得在链表中双向遍历变得更加方便。

下面是双向链表的实现：

class DNode {
    int data; // 存储数据
    DNode next; // 指向下一个节点
    DNode prev; // 指向前一个节点

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

class DoublyLinkedList {
    private DNode head; // 头节点

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

    // 在链表尾部添加节点
    public void add(int data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = newNode;
        } else {
            DNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }

    // 打印链表（从头到尾）
    public void printList() {
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 打印链表（从尾到头）
    public void printReverse() {
        DNode current = head;
        if (current == null) return;

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

        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
}

3. 循环链表

循环链表的最后一个节点指向头节点形成一个闭环，可以是单向或双向的。下面是单向循环链表的实现示例：

class CNode {
    int data; // 存储数据
    CNode next; // 指向下一个节点

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

class CircularLinkedList {
    private CNode head; // 头节点

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

    // 在链表尾部添加节点
    public void add(int data) {
        CNode newNode = new CNode(data);
        if (head == null) {
            head = newNode;
            newNode.next = head; // 形成循环
        } else {
            CNode current = head;
            while (current.next != head) {
                current = current.next;
            }
            current.next = newNode;
            newNode.next = head; // 形成循环
        }
    }

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

总结

以上是单向链表、双向链表和循环链表的基本实现。每种链表都有其独特的特点和应用场景。在实际开发中，根据需求选择合适的链表结构是十分重要的。在性能、内存和操作效率等方面，每种链表都有其优缺点，需要根据具体情况进行选择。