Data Structure | Doubly LinkedList

Doubly LinkedList 即双向链表,在 Singly LinkedList 的基础上又增加了一个指向前一个 node 的指针。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

Doubly LinkedList（DLL）与 Singly LinkedList（SLL）的对比：

DLL 在删除节点方面比 SLL 更方便。SLL 要找到要删除节点的前一个节点，往往是用遍历整个链表的方法。在 DLL 中，我们可以使用 previousPointer 获取前一个节点。
DLL 由于多了一个指针，更需要空间，在某些特定的操作操作上比 SLL 更麻烦（比如插入）。

对于双向链表来说，我们主要考虑如下几个操作：

如何在Java中构造一个双向链表

class DoublyLinkedList{
    static Node head = null;
    class Node{
	int data;
	Node next, prev;
	Node(int data){
	    this.data = data;
	    next = null;
	    prev = null;
	}
    }
    public static void main(String[] args) {}
}

如何打印出 DLL 中的元素

// Print the elements in DLL
public void printList(Node node){
    Node last = node;
    System.out.println("Traversal in forward direction \n");
    while (node != null){
	System.out.println(node.data + " ");
	last = node;
	node = node.next;
    }
    System.out.println("Traversal in backword direction \n");
    while (last != null){
	System.out.println(last.data + " ");
	last = last.prev;
    }
}

如何在 DLL 中插入一个节点

插入一个节点分为四种不同的情况，我们依次来讨论：

如何在 DLL 头部插入节点

// Given a reference (pointer to pointer) to the head of a list
// and an int, inserts a new node on the front of the list. 
public void push(Node node, int newData){
    // Allocate node and initialise data
    Node newNode = new Node(newData);  
    // Make next of new node as head and previous as NULL
    newNode.next = node;
    newNode.prev = null;
    // Change prev of head node to new node
    if (node != null) node.prev = newNode;
    // Move the head to point to the new node
    head = newNode;
}

如何在指定节点之后插入

// Given a node as prev_node, insert a new node after the given node
public void insertAfter(Node node, int newData){
    if (node == null){      // Check if the given node is null
        System.out.println("The given node cannot be null.");
        return; 
    }
    Node newNode = new Node(newData);  // Allocate node and initialise data
    newNode.next = node.next;  // Make next of new node as next of prevNode
    newNode.prev = node;    // Make prevNode as previous of newNode
    node.next = newNode;    // Make the next of prevNode as newNode
    // Change previous of newNode's next node
    if (newNode.next != null) newNode.next.prev = newNode;
}

如何在 DLL 尾部插入节点

/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end  */
public void append(Node node, int newData){
    Node newNode = new Node(newData); // Allocate node and initialise data
    //This new node is going to be the last node, so make next of it as null
    newNode.next = null; 
    //If the Linked List is empty, then make the new node as head
    if (node == null){
    	newNode.prev = null;
    	head = newNode;
    	return;
    }  
    // Else traverse till the last node
    Node temp = node;
    while (temp.next != null){
    	temp = temp.next;
    }
    temp.next = newNode;  // Change the next of last node
    newNode.prev = temp;  // Make last node as previous of new node
}

如何在给定节点之前插入节点

// Given a node as prev_node, insert a new node before the given node
public void insertBefore(Node node, int newData){
    if (node == null){      // Check if the given node is null
	System.out.println("The given node cannot be null.");
	return; 
    }
    Node newNode = new Node(newData);  // Allocate node and initialise data
    newNode.next = node;
    newNode.prev = node.prev;
    node.prev = newNode;
    if (newNode.prev != null) newNode.prev.next = newNode;    
}

如何删除指定的节点

// Function to delete a node in a Doubly Linked List
// node --> head node
// del --> the node need to be deleted
public void delete(Node node, Node del){
    if (head == null || del == null) return;
    // If node to be deleted is head node
    if (head == del) head = del.next;
    // Change next only if node to be deleted is NOT the last node
    if (del.next != null) del.next.prev = del.prev;
    // Change prev only if node to be deleted is NOT the first node
    if (del.prev != null) del.prev.next = del.next;
    return;
}

如何 reverse DLL

// Function to reverse a Doubly Linked List
public void reverse(){
    Node temp = null;
    Node curr = head;
    // swap next and prev for all nodes of doubly linked list
    while(curr != null){
	temp = curr.prev;
	curr.prev = curr.next;
	curr.next = temp;
	curr = curr.prev;
    }
    // Before changing head, check for the cases like empty list
    // and list with only one node
    if (temp != null) head = temp.prev;
}

关于 DLL 的讨论就到这里，以上内容如有纰漏或不足之处，欢迎与我讨论：
邮箱：entropy714@gmail.com
微信：cobain0714

Reference：