Java数据结构与算法学习之双向链表

Java数据结构与算法学习之双向链表

什么是双向链表？

双向链表是链表的一种，与单向链表不同的是，双向链表的每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点，因此双向链表可以双向遍历。

双向链表的Java实现

Java中可以使用节点类来实现双向链表，节点类代码如下：

public class Node<T> {

    private T data;
    private Node<T> prev;
    private Node<T> next;

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

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

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

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

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

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

具体实现过程的代码请参见Github链接：https://github.com/luokangyuan/data-structure-algorithm/tree/master/src/main/java/com/kangyuan/core/linklist

双向链表的基本操作

双向链表的基本操作包括：插入节点、删除节点、查找节点、修改节点等。以下是双向链表的基本操作的代码实现。

插入节点操作

双向链表的插入节点操作可以在任意位置插入一个新节点，包括表头和表尾。具体代码实现如下：

public void add(int index, T data) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    Node<T> newNode = new Node<>(data, null, null);
    if (index == 0) { // 插入到链表头部
        newNode.setNext(head);
        head.setPrev(newNode);
        head = newNode;
    } else if (index == size) { // 插入到链表尾部
        newNode.setPrev(tail);
        tail.setNext(newNode);
        tail = newNode;
    } else { // 插入到链表中间
        Node<T> temp = getNode(index);
        newNode.setPrev(temp.getPrev());
        temp.getPrev().setNext(newNode);
        newNode.setNext(temp);
        temp.setPrev(newNode);
    }
    size++;
}

删除节点操作

双向链表的删除节点操作可以删除链表中任意位置的节点，包括表头和表尾。具体代码实现如下：

public T remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    Node<T> removedNode = null;
    if (size == 1) { // 链表只有一个节点
        removedNode = head;
        head = null;
        tail = null;
    } else if (index == 0) { // 删除链表头部节点
        removedNode = head;
        head = head.getNext();
        head.setPrev(null);
    } else if (index == size - 1) { // 删除链表尾部节点
        removedNode = tail;
        tail = tail.getPrev();
        tail.setNext(null);
    } else { // 删除链表中间节点
        Node<T> temp = getNode(index);
        removedNode = temp;
        temp.getPrev().setNext(temp.getNext());
        temp.getNext().setPrev(temp.getPrev());
    }
    size--;
    return removedNode.getData();
}

查找节点操作

双向链表的查找操作即根据索引查找节点，实现代码如下：

public Node<T> getNode(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    Node<T> temp = head;
    for (int i = 0; i < index; i++) {
        temp = temp.getNext();
    }
    return temp;
}

修改节点操作

双向链表要修改节点只需要先查找到该节点，然后修改该节点的数据即可，实现代码如下：

public void set(int index, T data) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    Node<T> node = getNode(index);
    node.setData(data);
}

双向链表示例

以下是双向链表的两个示例，一个是将学生成绩按从高到低的顺序插入到链表中，另一个是将链表中的重复节点删除。

将学生成绩按从高到低的顺序插入到链表中

public static void insertSort(LinkList<Integer> linkList, Integer[] scores) {
    for (Integer score : scores) {
        Node<Integer> node = linkList.tail;
        while (node != null && score > node.getData()) {
            node = node.getPrev();
        }
        if (node == null) {
            linkList.add(0, score);
        } else if (node == linkList.tail) {
            linkList.add(linkList.size(), score);
        } else {
            linkList.add(linkList.indexOf(node.getData()), score);
        }
    }
}

public static void main(String[] args) {
    LinkList<Integer> linkList = new LinkList<>();
    Integer[] scores = {85, 78, 92, 60, 76};
    insertSort(linkList, scores);
    System.out.println(linkList);
}

删除双向链表中的重复节点

public void removeRepeated() {
    Node<T> node = head;
    while (node != null) {
        Node<T> next = node.getNext();
        while (next != null) {
            if (node.getData().equals(next.getData())) {
                remove(indexOf(next.getData()));
            }
            next = next.getNext();
        }
        node = node.getNext();
    }
}

public static void main(String[] args) {
    LinkList<String> linkList = new LinkList<>();
    linkList.add("A");
    linkList.add("B");
    linkList.add("C");
    linkList.add("B");
    linkList.add("D");
    linkList.add("C");
    linkList.add("E");
    linkList.add("F");
    linkList.add("A");
    linkList.add("E");
    linkList.removeRepeated();
    System.out.println(linkList);
}