简介

明天咱们来学习一下简单一点的 LinkedList：doublyLinkedList。

和 LinkedList 相比，doublyLinkedList 中的节点除了 next 指向下一个节点之外，还有一个 prev 之前的一个节点。所以被称为 doublyLinkedList。doublyLinkedList 是一个双向链表，咱们能够向前或者向后遍历 list。

明天咱们来学习一下 doublyLinkedList 的基本操作和概念。

doublyLinkedList 的构建

和 linkedList 一样，doublyLinkedList 是由一个一个的节点形成的。而每个节点除了要存储要保留的数据之外，还须要存储下一个节点和上一个节点的援用。

doublyLinkedList 须要一个 head 节点，咱们看下怎么构建：

public class DoublyLinkedList {

    Node head; // head 节点

    //Node 示意的是 Linked list 中的节点，蕴含一个 data 数据，上一个节点和下一个节点的援用
    class Node {
        int data;
        Node next;
        Node prev;
        //Node 的构造函数
        Node(int d) {data = d;}
    }
}

doublyLinkedList 的操作

接下来，咱们看一下 doublyLinkedList 的一些基本操作。

头部插入

头部插入的逻辑是：将新插入的节点作为新的 head 节点，并且将 newNode.next 指向原来的 head 节点。

同时须要将 head.prev 指向新的插入节点。

看下 java 代码：

    // 插入到 linkedList 的头部
    public void push(int newData) {
        // 构建要插入的节点
        Node newNode = new Node(newData);
        // 新节点的 next 指向当初的 head 节点
        // 新节点的 prev 指向 null
        newNode.next = head;
        newNode.prev = null;

        if (head != null)
            head.prev = newNode;

        // 现有的 head 节点指向新的节点
        head = newNode;
    }

尾部插入

尾部插入的逻辑是：找到最初一个节点，将最初一个节点的 next 指向新插入的节点，并且将新插入的节点的 prev 指向最初一个节点。

   // 新节点插入到 list 最初面
    public void append(int newData) {
        // 创立新节点
        Node newNode = new Node(newData);
        // 如果 list 是空，则新节点作为 head 节点
        if (head == null) {
            newNode.prev = null;
            head = newNode;
            return;
        }

        newNode.next = null;
        // 找到最初一个节点
        Node last = head;
        while (last.next != null) {last = last.next;}
        // 插入
        last.next = newNode;
        newNode.prev = last;
        return;
    }

插入给定的地位

如果要在给定的地位插入节点，咱们须要先找到插入地位的前一个节点，而后将前一个节点的 next 指向新节点。新节点的 prev 指向前一个节点。

同时咱们须要将新节点的 next 指向下一个节点，下一个节点的 prev 指向新的节点。

    // 插入在第几个元素之后
    public void insertAfter(int index, int newData) {
        Node prevNode = head;
        for (int i = 1; i < index; i++) {if (prevNode == null) {System.out.println("输出的 index 有误，请从新输出");
                return;
            }
            prevNode = prevNode.next;
        }
        // 创立新的节点
        Node newNode = new Node(newData);
        // 新节点的 next 指向 prevNode 的下一个节点
        newNode.next = prevNode.next;
        // 将新节点插入在 prevNode 之后
        prevNode.next = newNode;
        // 将新节点的 prev 指向 prevNode
        newNode.prev = prevNode;

        //newNode 的下一个节点的 prev 指向 newNode
        if (newNode.next != null)
            newNode.next.prev = newNode;
    }

删除指定地位的节点

删除节点的逻辑是：找到要删除节点的前一个节点，和下一个节点。前一个节点的 next 指向下一个节点，下一个节点的 prev 指向前一个节点。

    // 删除特定地位的节点
    void deleteNode(int index)
    {
        // 如果是空的，间接返回
        if (head == null)
            return;

        // head 节点
        Node temp = head;

        // 如果是删除 head 节点
        if (index == 1)
        {
            head = temp.next;
            return;
        }

        // 找到要删除节点的前一个节点
        for (int i=1; temp!=null && i<index-1; i++)
            temp = temp.next;

        // 如果超出范围
        if (temp == null || temp.next == null)
            return;

        // temp->next 是要删除的节点，删除节点
        Node next = temp.next.next;
        temp.next = next;
        Node prev = temp.next.prev;
        prev.prev = prev;
    }

本文的代码地址：

learn-algorithm

本文收录于 http://www.flydean.com/algorithm-doubly-linked-list/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！