Java数据结构之链表实现（单向、双向链表及链表反转）

Java数据结构之链表实现

链表基础概念

链表是一种数据结构，它由一系列节点（Node）组成，每个节点包含两个部分，一个是数据域（data），一个是指针域（next）。数据域存储数据信息，指针域指向下一个节点。

链表的种类很多，比如单向链表、双向链表、循环链表等等。

单向链表：链表的每个节点只有一个指针域，指向下一个节点。

双向链表：链表的每个节点有两个指针域，一个指向前一个节点，一个指向后一个节点。

循环链表：链表的最后一个节点指向链表的头节点。

单向链表的实现

定义单向链表节点类

定义单向链表的节点类Node，由data和next两部分组成，即数据和下一个节点的指针。

class Node {
    int data;
    Node next;

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

单向链表的基本操作

单向链表的基本操作，包括增加节点、删除节点、遍历节点和获取链表长度等。

增加节点

在链表末尾添加一个节点，并使新节点成为新的末尾节点。

public void addNode(int data) {
    Node newNode = new Node(data);
    if (head == null) {    // 添加的节点为头节点
        head = newNode;
        return;
    }
    Node temp = head;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
}

删除节点

删除链表中指定节点，需要找到该节点的前一个节点，使得前一个节点的指针指向后一个节点。

public void deleteNode(int data) {
    if (head == null) {    // 空链表
        return;
    }
    if (head.data == data) {   // 删除头节点
        head = head.next;
        return;
    }
    Node temp = head;
    while (temp.next != null && temp.next.data != data) {
        temp = temp.next;
    }
    if (temp.next == null) {  // 节点不存在
        return;
    }
    temp.next = temp.next.next; // 删除节点
}

遍历节点

遍历链表中的所有节点。

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

获取链表长度

获取链表的长度，需要从头节点开始遍历，同时计数器加1，直到遍历完成。

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

双向链表的实现

定义双向链表节点类

定义双向链表的节点类Node，由data和两个指针pre和next三部分组成，即数据、前一个节点和后一个节点的指针。

class DNode {
    int data;
    DNode pre;
    DNode next;

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

双向链表的基本操作

双向链表的基本操作，类似于单向链表，包括增加节点、删除节点和遍历节点等。

增加节点

在链表末尾添加一个节点，并使新节点成为新的末尾节点。

public void addNode(int data) {
    DNode newNode = new DNode(data);
    if (head == null) {    // 添加的节点为头节点
        head = newNode;
        return;
    }
    DNode temp = head;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
    newNode.pre = temp;
}

删除节点

删除链表中指定节点，需要找到该节点的前一个节点和后一个节点，使得它们的指针相互指向。

public void deleteNode(int data) {
    if (head == null) {    // 空链表
        return;
    }
    if (head.data == data) {   // 删除头节点
        head = head.next;
        head.pre = null;
        return;
    }
    DNode temp = head;
    while (temp.next != null && temp.next.data != data) {
        temp = temp.next;
    }
    if (temp.next == null) {  // 节点不存在
        return;
    }
    temp.next = temp.next.next;
    if (temp.next != null) {
        temp.next.pre = temp;
    }
}

遍历节点

遍历链表中的所有节点。

public void traverse() {
    DNode temp = head;
    while (temp != null) {
        System.out.print(temp.data + "<->");
        temp = temp.next;
    }
    System.out.println("null");
}

链表的反转

对于链表反转，常见的方法有递归和迭代两种方法。

递归反转单向链表

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

迭代反转单向链表

public Node reverse(Node head) {
    Node prev = null;
    Node curr = head;
    while (curr != null) {
        Node nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

非递归反转双向链表

public void reverse() {
    DNode pre = null;
    DNode curr = head;
    while (curr != null) {
        DNode nextTemp = curr.next;
        curr.next = pre;
        curr.pre = nextTemp;
        pre = curr;
        curr = nextTemp;
    }
    head = pre;
}

示例

示例1：单向链表的基本操作

public class Main {
    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.addNode(10);
        linkList.addNode(20);
        linkList.addNode(30);
        linkList.addNode(40);

        linkList.traverse();        // 10->20->30->40->null

        linkList.deleteNode(20);
        linkList.deleteNode(40);

        linkList.traverse();        // 10->30->null

        int length = linkList.length();
        System.out.println("length=" + length);    // length=2
    }
}

示例2：双向链表的基本操作和反转操作

public class Main {
    public static void main(String[] args) {
        DLinkList dLinkList = new DLinkList();
        dLinkList.addNode(10);
        dLinkList.addNode(20);
        dLinkList.addNode(30);
        dLinkList.addNode(40);

        dLinkList.traverse();       // 10<->20<->30<->40<->null

        dLinkList.deleteNode(20);
        dLinkList.deleteNode(40);

        dLinkList.traverse();       // 10<->30<->null

        dLinkList.reverse();
        dLinkList.traverse();       // 30<->10<->null
    }
}