java如何实现链表

实现链表的基本结构

在Java中，链表可以通过定义一个节点类（Node）和链表类（LinkedList）来实现。每个节点包含数据（data）和指向下一个节点的引用（next）。

class Node {
    int data;
    Node next;

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

链表的初始化

链表类通常包含一个头节点（head）作为链表的起始点。初始化时，头节点可以为空。

class LinkedList {
    Node head;

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

插入节点

链表的插入操作分为头部插入、尾部插入和指定位置插入。

头部插入：

public void insertAtHead(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

尾部插入：

public void insertAtTail(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}

指定位置插入：

public void insertAtPosition(int data, int position) {
    if (position == 0) {
        insertAtHead(data);
        return;
    }
    Node newNode = new Node(data);
    Node current = head;
    for (int i = 0; i < position - 1 && current != null; i++) {
        current = current.next;
    }
    if (current == null) {
        return;
    }
    newNode.next = current.next;
    current.next = newNode;
}

删除节点

删除操作可以通过值或位置实现。

删除指定值的节点：

public void deleteByValue(int data) {
    if (head == null) {
        return;
    }
    if (head.data == data) {
        head = head.next;
        return;
    }
    Node current = head;
    while (current.next != null && current.next.data != data) {
        current = current.next;
    }
    if (current.next != null) {
        current.next = current.next.next;
    }
}

删除指定位置的节点：

public void deleteByPosition(int position) {
    if (head == null) {
        return;
    }
    if (position == 0) {
        head = head.next;
        return;
    }
    Node current = head;
    for (int i = 0; i < position - 1 && current != null; i++) {
        current = current.next;
    }
    if (current == null || current.next == null) {
        return;
    }
    current.next = current.next.next;
}

遍历链表

遍历链表可以通过循环从头节点开始，依次访问每个节点。

public void traverse() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

查找节点

查找操作可以通过值或索引实现。

查找指定值的节点：

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

查找指定位置的节点：

public int getByPosition(int position) {
    Node current = head;
    for (int i = 0; i < position && current != null; i++) {
        current = current.next;
    }
    if (current == null) {
        throw new IndexOutOfBoundsException();
    }
    return current.data;
}

反转链表

反转链表可以通过迭代或递归实现。以下是迭代方法：

public void reverse() {
    Node prev = null;
    Node current = head;
    Node next = null;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}

链表的长度

计算链表的长度可以通过遍历节点计数实现。

public int length() {
    int count = 0;
    Node current = head;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}