Java数据结构之实现双向链表的示例

1. 什么是双向链表？

双向链表，英文名为doubly linked list，是一种链表结构。与单向链表不同，双向链表中的每一个节点除了保存了指向下一个节点的指针外，还保存了指向前一个节点的指针。因此，双向链表可双向遍历，可以从前向后或从后向前遍历。

2. 双向链表的实现

2.1 节点类的实现

创建节点类Node，并定义节点的属性和方法。

public class Node<E> {
    private E data; // 数据
    private Node<E> prev; // 前一个节点
    private Node<E> next; // 后一个节点

    // 构造方法
    public Node(E data, Node<E> prev, Node<E> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }

    // setter和getter方法
    public void setData(E data) {
        this.data = data;
    }

    public E getData() {
        return data;
    }

    public void setPrev(Node<E> prev) {
        this.prev = prev;
    }

    public Node<E> getPrev() {
        return prev;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }

    public Node<E> getNext() {
        return next;
    }
}

在构造方法中初始化节点的属性，setData()和getData()方法用于设置和获取节点的数据，setPrev()和getPrev()方法用于设置和获取前一个节点，setNext()和getNext()方法用于设置和获取后一个节点。

2.2 双向链表类的实现

创建双向链表类DoublyLinkedList，并定义双向链表的属性和方法。

public class DoublyLinkedList<E> {
    private Node<E> head; // 头节点
    private Node<E> tail; // 尾节点
    private int size = 0; // 链表长度

    // 构造方法
    public DoublyLinkedList() {
        head = null;
        tail = null;
    }

    // 获取链表长度
    public int size() {
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 向链表尾部添加节点
    public void add(E data) {
        addLast(data);
    }

    // 向链表尾部添加节点
    public void addLast(E data) {
        Node<E> newNode = new Node<E>(data, tail, null);
        if (tail == null) { // 链表为空时，新节点既是头节点又是尾节点
            head = newNode;
            tail = newNode;
        } else {
            tail.setNext(newNode);
            tail = newNode;
        }
        size++;
    }

    // 向链表头部添加节点
    public void addFirst(E data) {
        Node<E> newNode = new Node<E>(data, null, head);
        if (head == null) { // 链表为空时，新节点既是头节点又是尾节点
            head = newNode;
            tail = newNode;
        } else {
            head.setPrev(newNode);
            head = newNode;
        }
        size++;
    }

    // 获取链表中指定位置的节点
    public Node<E> getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> node = head;
        for (int i = 0; i < index; i++) {
            node = node.getNext();
        }
        return node;
    }

    // 获取链表中指定位置节点的数据
    public E get(int index) {
        return getNode(index).getData();
    }

    // 修改链表中指定位置节点的数据
    public void set(int index, E data) {
        Node<E> node = getNode(index);
        node.setData(data);
    }

    // 在链表中指定位置插入节点
    public void add(int index, E data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            addFirst(data);
        } else if (index == size) {
            addLast(data);
        } else {
            Node<E> oldNode = getNode(index);
            Node<E> newNode = new Node<E>(data, oldNode.getPrev(), oldNode);
            oldNode.getPrev().setNext(newNode);
            oldNode.setPrev(newNode);
            size++;
        }
    }

    // 删除链表中指定位置节点
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            head = head.getNext();
            if (head != null) {
                head.setPrev(null);
            } else {
                tail = null;
            }
        } else if (index == size - 1) {
            tail = tail.getPrev();
            if (tail != null) {
                tail.setNext(null);
            } else {
                head = null;
            }
        } else {
            Node<E> oldNode = getNode(index);
            oldNode.getPrev().setNext(oldNode.getNext());
            oldNode.getNext().setPrev(oldNode.getPrev());
            oldNode.setData(null);
        }
        size--;
    }
}

在构造方法中初始化链表的头节点和尾节点，size()方法用于获取链表长度，isEmpty()方法用于判断链表是否为空。add()、addLast()、addFirst()方法用于向链表中添加节点，getNode()方法用于获取链表中指定位置的节点，get()方法用于获取链表中指定位置节点的数据，set()方法用于修改链表中指定位置节点的数据，add()方法用于在链表中指定位置插入节点，remove()方法用于删除链表中指定位置节点。

3. 示例说明

3.1 示例一：创建双向链表并向其中添加数据

public static void main(String[] args) {
    DoublyLinkedList<String> list = new DoublyLinkedList<String>();
    list.addLast("A");
    list.addLast("B");
    list.addFirst("C");
    list.add(1, "D");
    System.out.println(list.get(0)); // output: C
    System.out.println(list.get(1)); // output: D
    System.out.println(list.get(2)); // output: A
    System.out.println(list.get(3)); // output: B
}

首先创建一个DoublyLinkedList对象list，并向其中添加数据。addLast()方法将"A"和"B"分别添加到链表尾部，addFirst()方法将"C"添加到链表头部，add()方法将"D"插入到链表中间位置。最后输出链表中各个位置的数据。

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

public static void main(String[] args) {
    DoublyLinkedList<String> list = new DoublyLinkedList<String>();
    list.addLast("A");
    list.addLast("B");
    list.addFirst("C");
    list.add(1, "D");
    System.out.println(list.get(2)); // output: A
    System.out.println(list.size()); // output: 4
    list.remove(2);
    System.out.println(list.get(2)); // output: D
    System.out.println(list.get(3)); // output: B
    System.out.println(list.size()); // output: 3
}

首先创建一个DoublyLinkedList对象list，并向其中添加数据。addLast()方法将"A"和"B"分别添加到链表尾部，addFirst()方法将"C"添加到链表头部，add()方法将"D"插入到链表中间位置。然后删除链表中第2个位置的数据，最后输出链表中各个位置的数据和链表长度。