Doubly Linked List

Description

Structure

Node Structure: A node in a doubly linked list typically consists of three components: data, next pointer and previous pointer.

Data: It holds the actual value or data associated with the node.

Next Pointer: It stores the memory address (reference) of the next node in the list.

Previous Pointer: It stores the memory address (reference) of the previous node in the list.

Head and Tail: The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL, indicating the end of the list. This node is known as the tail node.

Push back

1. Create a new node.
2. Set the next pointer of tail node to the new node.
3. Set the previous pointer of new node to the tail node.
4. Set the tail pointer to the new node.

Push front

1. Create a new node.
2. Set the next pointer of the new node to the head node.
3. Set the previous pointer of the head node to the new node.
4. Set the head pointer to the new node.

Pop back

1. Save the previous pointer of the tail node to the temporary pointer.
2. Set the next pointer of tail's previous node to NULL.
3. Free the tail node.
4. Set the tail pointer to the temporary pointer.

Pop front

1. Save the next pointer of the head node to the temporary pointer.
2. Set the previous pointer of head's next node to NULL.
3. Free the head node.
4. Set the head pointer to the temporary pointer.

Find item

1. Set current pointer to the head pointer.
2. Compare current node data with finding item data in cycle:
   • If they are equal, we found the right node.
   • If they are not equal, set current pointer to the current node next pointer.
3. If current node is NULL, then there is no right node in the list.

Example

Let's look at several examples of working with a doubly linked list. We start with empty list.

1. Set current pointer to the head pointer.
2. Current node data = 1 is not equal to data = 4.
3. Set current pointer to the current node next pointer.

Code

                        class DoublyLinkedList:
                            class Node:
                                def __init__(self, data: Any):
                                    self.data = data
                                    self.prev: Optional[DoublyLinkedList.Node] = None
                                    self.next: Optional[DoublyLinkedList.Node] = None
                        
                            def __init__(self):
                                self.head: Optional[DoublyLinkedList.Node] = None
                                self.tail: Optional[DoublyLinkedList.Node] = None
                        
                            def push_back(self, data: Any):
                                if self.tail is None:
                                    self.tail = DoublyLinkedList.Node(data)
                                    self.head = self.tail
                                else:
                                    self.tail.next = DoublyLinkedList.Node(data)
                                    self.tail.next.prev = self.tail
                                    self.tail = self.tail.next
                        
                            def push_front(self, data: Any):
                                if self.head is None:
                                    self.head = DoublyLinkedList.Node(data)
                                    self.tail = self.head
                                else:
                                    self.head.prev = DoublyLinkedList.Node(data)
                                    self.head.prev.next = self.head
                                    self.head = self.head.prev
                        
                            def pop_back(self):
                                if self.tail is not None:
                                    if self.head.next is None:
                                        self.head = None
                                        self.tail = None
                                    else:
                                        self.tail = self.tail.prev
                                        self.tail.next = None
                        
                            def pop_front(self):
                                if self.head is not None:
                                    if self.head.next is None:
                                        self.head = None
                                        self.tail = None
                                    else:
                                        self.head = self.head.next
                                        self.head.prev = None
                        
                            def find_item(self, data: Any) -> bool:
                                current = self.head
                                while current is not None:
                                    if current.data == data:
                                        return True
                                    else:
                                        current = current.next
                                return False