如何用java实现链表

实现链表的基本结构

链表由节点（Node）组成，每个节点包含数据（data）和指向下一个节点的引用（next）。

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

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

定义链表类

链表类需要管理节点的增删改查操作，并维护头节点（head）。

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

    public LinkedList() {
        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;
}

删除指定值的节点

遍历链表找到目标节点，调整前驱节点的next指针以跳过目标节点。

public void delete(T data) {
    if (head == null) return;
    if (head.data.equals(data)) {
        head = head.next;
        return;
    }
    Node<T> current = head;
    while (current.next != null && !current.next.data.equals(data)) {
        current = current.next;
    }
    if (current.next != null) {
        current.next = current.next.next;
    }
}

查找节点是否存在

遍历链表，检查是否存在与目标值匹配的节点。

public boolean contains(T data) {
    Node<T> current = head;
    while (current != null) {
        if (current.data.equals(data)) {
            return true;
        }
        current = current.next;
    }
    return false;
}

打印链表内容

遍历链表并依次输出每个节点的值。

public void printList() {
    Node<T> current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}

示例用法

创建一个链表并测试插入、删除和查找功能。

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

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

        System.out.println("Contains 3: " + list.contains(3)); // 输出: true
    }
}