【Java数据结构】链表(Linked List)-双向链表

谁借莪１个温暖的怀抱￠ 2023-09-30 23:21 18阅读 0赞

**双向链表（Linked List）**是一种常用的数据结构，它允许在所有节点中快速添加或删除元素，并且可以有效地实现反向遍历。本篇文章将介绍双向链表的基础知识，并提供使用Java语言实现该数据结构的示例代码。

--------------------

#### 一、双向链表的基础知识 ####

一个双向链表由多个节点组成，每个节点包含两个指针，分别指向前驱节点和后继节点。首节点的前驱节点为null，尾节点的后继节点为null。

下面是一个示意图：

![48d42dd9a13a4555a98df290b5f91320.png][]

null <- A <-> B <-> C <-> D -> null

上述图中，`A`为首节点，`D`为尾节点。每个节点都有一个值域（value），这个值域可以存储任意类型的数据。在双向链表中，我们通常只需要保存首节点的引用，即可轻松访问整个链表。

#### 二、双向链表的操作 ####

*  **添加节点**

为了在链表中添加新节点，我们需要指定插入节点的位置。假设我们要在节点`B`之后插入一个新节点`E`，则需要进行以下操作：

1.  创建一个新节点`E`，并将其值域设置为目标元素。
2.  将新节点`E`的前驱指针指向节点`B`，将新节点`E`的后继指针指向节点`C`。
3.  将节点`B`的后继指针指向新节点`E`，将节点`C`的前驱指针指向新节点`E`。

下面是上述操作的示意图：

null <- A <-> B <-> E <-> C <-> D -> null

*  **删除节点**

要从双向链表中删除节点，我们需要知道目标节点的位置。假设我们要删除节点`C`，则需要进行以下操作：

1.  将节点`C`的前驱节点（即节点`B`）的后继指针指向节点`D`。
2.  将节点`D`的前驱指针指向节点`B`。

下面是上述操作的示意图：

null <- A <-> B <-> E <-> D -> null

*  **遍历节点**

由于双向链表中每个节点都有一个指向后继节点和前驱节点的引用，因此可以非常容易地实现正向和反向遍历。

下面是一个遍历链表并打印所有元素值的示例代码：

public class DoublyLinkedList<T> {
        private Node<T> head;
        private Node<T> tail;
    
        private static class Node<T> {
            private T data;
            private Node<T> prev;
            private Node<T> next;
    
            public Node(T data) {
                this.data = data;
                this.prev = null;
                this.next = null;
            }
        }
    
        public void addFirst(T data) {
            Node<T> newNode = new Node<>(data);
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                head.prev = newNode;
                newNode.next = head;
                head = newNode;
            }
        }
    
        public void addLast(T data) {
            Node<T> newNode = new Node<>(data);
            if (tail == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.prev = tail;
                tail = newNode;
            }
        }
    
        public void removeFirst() {
            if (head == null) {
                throw new NoSuchElementException();
            } else if (head == tail) {
                head = null;
                tail = null;
            } else {
                head.next.prev = null;
                head = head.next;
            }
        }
    
        public void removeLast() {
            if (tail == null) {
                throw new NoSuchElementException();
            } else if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail.prev.next = null;
                tail = tail.prev;
            }
        }
    
        /**
        *为了实现反向遍历，我们只需要替换current.next为current.prev，同时从尾节点开始遍历即可。
        */
        public void traverse() {
            Node<T> current = head;
            while (current != null) {
                System.out.print(current.data + " ");
                current = current.next;
            }
            System.out.println();
        }
    }

上述实现定义了一个 `DoublyLinkedList` 类，其中包含一个嵌套的 `Node` 类，用于表示双向链表中的节点。通过 `addFirst` 和 `addLast` 方法可以在链表的头部和尾部添加元素，通过 `removeFirst` 和 `removeLast` 方法可以删除链表中的第一个和最后一个元素。traverse方法用于遍历链表并打印所有元素值

[48d42dd9a13a4555a98df290b5f91320.png]: https://img-blog.csdnimg.cn/48d42dd9a13a4555a98df290b5f91320.png