Java数据结构之双端链表原理与实现方法

一、什么是双端链表？

双端链表是一种链式数据结构，它每个节点都有两个指针：一个指向前一个节点，一个指向后一个节点。它具有链表的所有特点，而且还有一些独特的优点：对于一个双向链表，我们可以从头到尾遍历，也可以从尾到头遍历。在某些情况下，它比单向链表更有用，因为它可以执行逆序遍历。

二、双端链表的原理

双端链表由节点构成，每个节点包含两个引用/指针，一个指向前一个节点，指针称为"prev"，一个指向后一个节点，指针称为"next"。如下图所示：

+------+    +------+    +------+
| data |    | data |    | data |
+------+    +------+    +------+
| prev |<-->| prev |<-->| prev |
+------+    +------+    +------+
| next |--> | next |--> | next |
+------+    +------+    +------+

双端链表有两个特殊节点：头节点和尾节点。头节点是链表的第一个节点，尾节点是链表的最后一个节点。头节点的"prev"指针指向"null"，尾节点的"next"指针指向"null"。

三、双端链表的实现

3.1 双端链表节点的类定义

为了实现双端链表，我们需要定义一个节点类:

class Node<E> {
    E data;
    Node<E> prev;
    Node<E> next;

    public Node(E data, Node<E> prev, Node<E> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

在这个节点类中，我们定义了一个泛型类型的数据成员"data"和两个引用类型的"prev"和"next"，分别指向前一个节点和后一个节点。并实现了一个构造函数，用于创建一个新节点。

3.2 双端链表的类定义

双端链表的类定义如下：

public class DoubleLinkedList<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size;

    public DoubleLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    //添加新节点到链表尾部
    public void add(E element) {
        Node<E> newNode = new Node<E>(element, tail, null);
        if (tail != null) {
            tail.next = newNode;
        }
        tail = newNode;
        if (head == null) {
            head = newNode;
        }
        size++;
    }

    //获取指定下标的节点
    public Node<E> getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> ptr = head;
        for (int i = 0; i < index; i++) {
            ptr = ptr.next;
        }
        return ptr;
    }

    //获取指定下标的节点的值
    public E get(int index) {
        return getNode(index).data;
    }

    //在指定节点后插入节点
    public void addAfter(Node<E> node, E element) {
        Node<E> newNode = new Node<E>(element, node, node.next);
        node.next = newNode;
        if (node == tail) {
            tail = newNode;
        } else {
            newNode.next.prev = newNode;
        }
        size++;
    }

    //在指定节点前插入节点
    public void addBefore(Node<E> node, E element) {
        Node<E> newNode = new Node<E>(element, node.prev, node);
        node.prev = newNode;
        if (node == head) {
            head = newNode;
        } else {
            newNode.prev.next = newNode;
        }
        size++;
    }

    //移除指定节点
    public void remove(Node<E> node) {
        if (node == head) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        }
        if (node == tail) {
            tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
        size--;
    }
}

在这个双端链表类中，我们定义了三个数据成员：

• "head" – 链表的第一个节点的引用。如果链表为空，则为"null"。
• "tail" – 链表的最后一个节点的引用。如果链表为空，则为"null"。
• "size" – 链表中节点的数量。

我们实现了五个公共方法：

• "add" – 在链表的末尾添加一个新节点。
• "getNode" – 获取给定索引处的节点。该方法用于支持其他方法的实现。
• "get" – 获取给定索引处节点的值。
• "addAfter" – 在给定节点的后面添加新节点。
• "addBefore" – 在给定节点的前面添加新节点。
• "remove" – 从链表中移除给定的节点。

以上这些方法以及节点类的定义可以满足双端链表的基本操作。

3.3 双端链表的使用示例

public class DoubleLinkedListTest {
    public static void main(String[] args) {
        DoubleLinkedList<String> list = new DoubleLinkedList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");

        Node<String> secondNode = list.getNode(1);
        list.addAfter(secondNode, "PHP");
        list.addBefore(secondNode, "JavaScript");

        Node<String> thirdNode = list.getNode(2);
        list.remove(thirdNode);

        System.out.println("Size of List : " + list.size);
        System.out.println("Head of List : " + list.head.data);
        System.out.println("Tail of List : " + list.tail.data);
        for (int i = 0; i < list.size; i++) {
            System.out.println("Data at Index " + i + " : " + list.get(i));
        }
    }
}

在这个示例中，我们向双端链表中插入三个元素("Java", "Python", "C++")。然后，在第二个元素后面添加"PHP"，在第二个元素前面添加"JavaScript"。最后，从链表中删除第三个元素("C++")。最后打印链表的大小、头元素，尾元素和所有元素。

输出结果如下：

Size of List : 3
Head of List : JavaScript
Tail of List : Python
Data at Index 0 : JavaScript
Data at Index 1 : Java
Data at Index 2 : PHP

四、总结

双端链表是一种链式数据结构，具有许多链表的优点，它之所以称为"双向"，是因为每个节点都有两个指针指向前一个节点和后一个节点。这使得它能够执行双向遍历。实现双端链表需要定义一个节点类以及一个双端链表类，同时实现一些基本操作如"添加"、"获取"、"插入"和"删除"等。以上内容是双端链表的基本原理和实现方法的完整攻略。