java代码实现双向链表

下面我为大家详细讲解如何使用Java代码实现双向链表。

什么是双向链表？

双向链表是一种数据结构，与单向链表类似，但其每个节点还会连接到其前驱节点。一个节点包括数据域和两个指针域，分别指向前后两个节点。可以看做是两个单向链表的结合体。

双向链表的实现

1. 定义节点类

Java代码中，需要先定义一个节点类来表示链表中的每个节点。Java代码实现如下：

public class ListNode {
    int val;
    ListNode prev;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

ListNode表示一个节点，包含val表示节点存储的值，prev表示前一个节点，next表示后一个节点。我们使用构造函数来初始化这些值。

2. 实现双向链表类

接下来，实现双向链表类，包含添加节点、删除节点、输出链表等基本操作。Java代码实现如下：

public class DoublyLinkedList {
    private ListNode head;
    private ListNode tail;
    private int size;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void addFirst(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
    }

    public void addLast(int val) {
        ListNode node = new ListNode(val);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Invalid index");
        } else if (index == 0) {
            addFirst(val);
        } else if (index == size) {
            addLast(val);
        } else {
            ListNode node = new ListNode(val);
            ListNode cur = getNodeAtIndex(index);
            ListNode prev = cur.prev;
            prev.next = node;
            node.prev = prev;
            node.next = cur;
            cur.prev = node;
            size++;
        }
    }

    public ListNode getNodeAtIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Invalid index");
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Invalid index");
        }
        ListNode cur = getNodeAtIndex(index);
        ListNode prev = cur.prev;
        ListNode next = cur.next;
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
        }
        size--;
    }

    public void printList() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

DoublyLinkedList表示双向链表类，包含头指针head、尾指针tail和链表节点个数size，下面介绍一下几个核心方法。

• addFirst方法：在链表头部添加节点。
• addLast方法：在链表尾部添加节点。
• addAtIndex方法：在链表的index位置添加节点，如果index位置越界，则抛出异常。
• deleteAtIndex方法：删除链表中index位置的节点，如果index位置越界，则抛出异常。
• getNodeAtIndex方法：获取链表中index位置的节点。
• printList方法：输出链表中所有节点的值。

这样，我们就实现了一个双向链表类。

3. 示例

下面通过两个示例说明如何使用我们刚刚实现的双向链表。

示例1：在双向链表中添加节点

public static void main(String[] args) {
    DoublyLinkedList list = new DoublyLinkedList();
    list.addFirst(1);
    list.addLast(3);
    list.addAtIndex(1, 2);
    list.printList();
    // 输出结果：1 2 3
}

在示例中，首先创建了一个双向链表对象list，然后在链表头部添加节点1，接着在链表尾部添加节点3，最后在链表的第二个位置插入节点2，然后输出完整的链表节点值。

示例2：在双向链表中删除节点

public static void main(String[] args) {
    DoublyLinkedList list = new DoublyLinkedList();
    list.addFirst(1);
    list.addLast(2);
    list.addLast(3);
    list.deleteAtIndex(1);
    list.printList();
    // 输出结果：1 3
}

在示例中，首先创建了一个双向链表对象list，然后在链表头部添加节点1，接着在链表尾部添加节点2和节点3，之后删除了第二个节点，并输出完整的链表节点值。

总结

以上就是Java代码实现双向链表的完整攻略了。双向链表和单向链表主要区别在于节点除了保存指向下一个节点的指针外，还保存指向上一个节点的指针。通过使用Java代码，我们可以轻松地创建和操作双向链表，实现常见的链表操作，如添加节点、删除节点等。