[Data Structure] Doubly-Linked Lists

Doubly-Linked List

 

A doubly-linked list is a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node. The doubly-linked list's first node is called the head, and the last node the tail. (same as singly–linked lists)

Same as the singly–linked list, doubly–linked list is also a positional list: A list where elements contain pointers to the next and/or previous elements in the list.

---

Operations

 

1. Append

Append operation for a doubly-linked list inserts the new node after the list's tail node.

• Append to empty list: If the list's head pointer is null (empty), the algorithm points the list's head and tail pointers to the new node.
• Append to non-empty list: If the list's head pointer is not null (not empty), the algorithm points the tail node's next pointer to the new node, points the new node's previous pointer to the list's tail node, and points the list's tail pointer to the new node.

 

2. Prepend

Prepend operation of a doubly-linked list inserts the new node before the list's head node and points the head pointer to the new node.

• Prepend to empty list: If the list's head pointer is null (empty), the algorithm points the list's head and tail pointers to the new node.
• Prepend to non-empty list: If the list's head pointer is not null (not empty), the algorithm points the new node's next pointer to the list's head node, points the list head node's previous pointer to the new node, and then points the list's head pointer to the new node.

 

3. Insert

InsertAfter operation for a doubly-linked list inserts the new node after a provided existing list node. curNode is a pointer to an existing list node. 

• Insert as first node: If the list's head pointer is null (list is empty), the algorithm points the list's head and tail pointers to the new node.
• Insert after list's tail node: If the list's head pointer is not null (list is not empty) and curNode points to the list's tail node, the new node is inserted after the tail node. The algorithm points the tail node's next pointer to the new node, points the new node's previous pointer to the list's tail node, and then points the list's tail pointer to the new node.
• Insert in middle of list: If the list's head pointer is not null (list is not empty) and curNode does not point to the list's tail node, the algorithm updates the current, new, and successor nodes' next and previous pointers to achieve the ordering {curNode newNode sucNode}, which requires four pointer updates: point the new node's next pointer to sucNode, point the new node's previous pointer to curNode, point curNode's next pointer to the new node, and point sucNode's previous pointer to the new node.

 

4. Remove

Remove operation for a doubly-linked list removes a provided existing list node. 

• Successor exists: If the successor node pointer is not null (successor exists), the algorithm points the successor's previous pointer to the predecessor node.
• Predecessor exists: If the predecessor node pointer is not null (predecessor exists), the algorithm points the predecessor's next pointer to the successor node.
• Removing list's head node: If curNode points to the list's head node, the algorithm points the list's head pointer to the successor node.
• Removing list's tail node: If curNode points to the list's tail node, the algorithm points the list's tail pointer to the predecessor node.

 

Searching is the same with singly-linked list. 

It returns the first node with the value matching the key, starting from the head node traversing until the tail node, and return null if not found. 

---

Python Implementation

 

In the singly–linked list Node class, we only had two class variables, data for its value and next pointing the next node. 

This time, we add another reference variable to the previous node, called prev. 

class Node:
    def __init__(self, initial_data):
        self.data = initial_data
        self.next = None
        self.prev = None

 

 

This single change results in a little bit of modification for each operation methods from that of singly-linked list. 

The differences are denoted with comments in each method code block.

 

1. append

def append(self, new_node):
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        new_node.prev = self.tail  # Added
        self.tail = new_node

 

2. prepend

def prepend(self, new_node):
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node  # Added
        self.head = new_node

 

3. insert_after

def insert_after(self, current_node, new_node):
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    elif current_node is self.tail:
        self.append(new_node)
    else:
        # Modified Algorithm
        successor_node = current_node.next
        new_node.next = successor_node
        new_node.prev = current_node
        current_node.next = new_node
        successor_node.prev = new_node

 

4. remove

# Changed from remove_after to remove
def remove(self, current_node):
    successor_node = current_node.next
    predecessor_node = current_node.prev

    if successor_node is not None:
        successor_node.prev = predecessor_node

    if predecessor_node is not None:
        predecessor_node.next = successor_node

    if current_node is self.head:
        self.head = successor_node

    if current_node is self.tail:
        self.tail = predecessor_node