java链表怎么表示法

Java中，链表是一种常用的数据结构，用于存储一系列元素，其中每个元素（称为节点）包含数据部分和指向下一个节点的引用，链表有多种表示方法,以下是几种常见的链表表示法及其实现方式：

单向链表

基本结构

单向链表是最简单的链表形式，每个节点包含数据和指向下一个节点的引用，最后一个节点的引用为null,表示链表的结束。

代码示例

// 定义节点类
class Node<E> {
    E data;
    Node<E> next;
    public Node(E data) {
        this.data = data;
        this.next = null;
    }
}
// 定义单向链表类
class SingleLinkedList<E> {
    private Node<E> head;
    public SingleLinkedList() {
        this.head = null;
    }
    // 插入新节点到链表头部
    public void insertAtHead(E data) {
        Node<E> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
    }
    // 遍历链表并打印所有节点的数据
    public void printList() {
        Node<E> current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

双向链表

基本结构

双向链表中的每个节点不仅包含指向下一个节点的引用，还包含指向前一个节点的引用,这使得双向链表可以从两端进行遍历。

代码示例

// 定义双向链表的节点类
class DoubleNode<E> {
    E data;
    DoubleNode<E> next;
    DoubleNode<E> prev;
    public DoubleNode(E data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
// 定义双向链表类
class DoubleLinkedList<E> {
    private DoubleNode<E> head;
    private DoubleNode<E> tail;
    public DoubleLinkedList() {
        this.head = null;
        this.tail = null;
    }
    // 在链表尾部插入新节点
    public void insertAtTail(E data) {
        DoubleNode<E> newNode = new DoubleNode<>(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }
    // 遍历链表并打印所有节点的数据
    public void printList() {
        DoubleNode<E> current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

循环链表

基本结构

循环链表中的最后一个节点指向头节点，形成一个闭环,循环链表可以是单向或双向的。

代码示例（单向循环链表）

// 定义循环链表的节点类
class CircularNode<E> {
    E data;
    CircularNode<E> next;
    public CircularNode(E data) {
        this.data = data;
        this.next = null;
    }
}
// 定义单向循环链表类
class CircularLinkedList<E> {
    private CircularNode<E> head;
    public CircularLinkedList() {
        this.head = null;
    }
    // 在链表头部插入新节点
    public void insertAtHead(E data) {
        CircularNode<E> newNode = new CircularNode<>(data);
        if (head == null) {
            head = newNode;
            head.next = head; // 指向自身，形成循环
        } else {
            CircularNode<E> temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
            head = newNode;
        }
    }
    // 遍历链表并打印所有节点的数据
    public void printList() {
        if (head == null) return;
        CircularNode<E> current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head);
        System.out.println(head.data); // 打印头节点数据，完成循环
    }
}

FAQs

什么是链表中的“头节点”？

• 头节点是链表中的第一个节点，它通常不存储实际数据，而是作为链表的起始点，在某些实现中，头节点也用于简化链表的操作，如插入和删除，在单向链表中，头节点的next指针指向链表中的第一个实际数据节点；在双向链表中，头节点的next和prev指针分别指向第一个和最后一个节点，在许多简单的链表实现中，并不使用专门的头节点,而是直接将第一个存储数据的节点作为链表的起始点。

如何判断一个链表是否为空？

• 要判断一个链表是否为空，可以检查链表的头节点是否为null（对于单向链表）或头节点和尾节点是否都为null（对于双向链表），如果头节点为null，则说明链表中没有节点，即链表为空，这是最常用且高效的方法，因为只需要访问链表的头节点即可进行判断，时间复杂度为