Java链表操作示例

一、什么是链表

链表是一种数据结构，它由多个节点（node）组成，每个节点包含两个属性，一个是存储的数据，另一个是指向下一个节点的指针。链表的优势在于可以动态的增加和删除元素。相对于数组而言，链表的内存分配更加灵活，但是在访问某个节点时需要遍历整个链表，时间复杂度为O(n)。

二、创建链表

下面是一个简单的链表实现，它包括链表的节点类和链表类：

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

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

    public void add(int data) {
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
        } else {
            Node temp = this.head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }
}

三、链表的遍历

遍历链表指的是依次访问链表中每个节点。下面是遍历链表的一个示例方法：

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

四、在链表中插入一个新节点

下面给出了在链表中插入新节点的方法，如需在链表的第 i 个位置插入新节点，需要先定位到该位置的前一个节点，然后将新节点插入该节点之后。

public void insert(int data, int index) {
    Node node = new Node(data);

    if (index == 0) {
        node.next = this.head;
        this.head = node;
        return;
    }

    Node temp = this.head;
    for (int i = 0; i < index - 1; i++) {
        temp = temp.next;
    }

    node.next = temp.next;
    temp.next = node;
}

五、在链表中删除一个节点

从链表中删除节点的方法需要先定位到待删节点的前一个节点，然后将前一个节点的指针指向待删节点的下一个节点。

public void remove(int data) {
    if (this.head == null) {
        return;
    }

    if (this.head.data == data) {
        this.head = this.head.next;
        return;
    }

    Node temp = this.head;
    while (temp.next != null && temp.next.data != data) {
        temp = temp.next;
    }

    if (temp.next != null) {
        temp.next = temp.next.next;
    } else {
        System.out.println("节点不存在");
    }
}

六、链表的反转

反转链表指的是反转链表中节点的顺序。下面是一个递归实现的反转链表方法：

public Node reverse(Node node) {
    if (node == null || node.next == null) {
        return node;
    }

    Node head = reverse(node.next);
    node.next.next = node;
    node.next = null;
    return head;
}

七、链表的排序

链表的排序指的是对链表中节点的数据进行排序。下面是一个使用快速排序的链表排序方法：

public Node sort(Node node) {
    if (node == null || node.next == null) {
        return node;
    }

    int pivot = node.data;
    Node left = null;
    Node right = null;
    node = node.next;

    while (node != null) {
        Node next = node.next;
        if (node.data < pivot) {
            node.next = left;
            left = node;
        } else {
            node.next = right;
            right = node;
        }
        node = next;
    }

    left = sort(left);
    right = sort(right);
    Node result = left;
    while (left != null && left.next != null) {
        left = left.next;
    }
    if (left != null) {
        left.next = new Node(pivot);
    } else {
        result = new Node(pivot);
        left = result;
    }
    left.next = right;
    return result;
}