In the previous post, I introduced Data structure: Singly Linked List and how to implement it in Python.

Move on, I would like to show you about Data structure: Doubly Linked List

Table of content

What is a Linked List data structure?
What is a Doubly Linked List?
How to implement in Python
Setup
Insertion
Deletion
Difference between Singly Linked List and Doubly Linked List
Conclusion

What is a Linked List data structure?

This part is mentioned in the previous post. Don't worry about it. I will repeat it below.

A linked list is a fundamental data structure in computer science. It consists of nodes where each node contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays.

What is a Doubly Linked List?

A doubly linked list (DLL) is a special type of linked list in which each node contains a pointer to the previous node as well as the next node of the linked list.

How to implement in Python

You can clone the source code here to follow it easier.

Setup

Create a new file.

mkdir doubly_linked_list
cd doubly_linked_list
vi doubly_linked_list.py

Create a new class with the name Node

class Node:
  def __init__(self, data: int) -> None:
    self.data = data
    self.prev = None
    self.next = None

Create a new class DoublyLinkedList

class DoublyLinkedList:
  def __init__(self) -> None:
    self.head = None

Insertion

There are three types:

At the beginning
At the end
At a given position

Insert a node at the beginning

Step to insert:

Create a new node, the previous pointer is none, and the next pointer is a head node that is the current node.
The previous pointer of the head node is the created node, and then update the head node is the created node.

def insert_at_head(self, data: int):
  new_node = Node(data)
  new_node.prev = None
  new_node.next = self.head

  if (self.head):
    self.head.prev = new_node

  self.head = new_node

Insert a node at the end

Step to insert:

Getting tail node
Creating a new node and the previous pointer is the tail node, and the next pointer is none
The next pointer of the tail node is the created node, and then the updated head node is the created node.

def insert_at_tail(self, data: int):
  if (self.head is None):
    return self.insert_at_head(data)
  
  node_len = self.get_len()
  prev_node = self.get_node_at_index(node_len - 1)

  new_node = Node(data)
  new_node.prev = prev_node
  new_node.next = None

  prev_node.next = new_node

Insert a node at a given position

Step to insert:

Getting the previous node.
Create a new node, the previous pointer is the previous node, and the next pointer is the next node.
Update the previous pointer of the next node and the next pointer of the previous node is a created node

def insert_at_index(self, data: int, index: int):
  node_len = self.get_len()

  if (index < 0 or index > node_len):
    return None

  if (index == 0):
    return self.insert_at_head(data)

  if (index == node_len - 1):
    return self.insert_at_tail(data)
  
  prev_node = self.get_node_at_index(index - 1)
  
  new_node = Node(data)
  new_node.prev = prev_node
  new_node.next = prev_node.next

  prev_node.next = new_node

Deletion

There are three types:

At the beginning
At the end
At the given position

Delete a node at the beginning

Step to delete:

Get the next node of the head node
Update the previous pointer of the next node is none, and then update the head node is the next node

def delete_first_node(self):
  node_len = self.get_len()
  if (node_len == 0):
    return None

  if (node_len == 1):
    self.head = None
    return self.head

  next_node = self.head.next
  next_node.prev = None
  self.head = next_node

Delete a node at the end

Step to delete:

Get the previous node that is next to the last node.
Update the next pointer of the previous node is none

def delete_last_node(self):
  node_len = self.get_len()
  if (node_len == 0 or node_len == 1):
    return self.delete_first_node()
  
  prev_node = self.get_node_at_index(node_len - 2)
  prev_node.next = None

Delete a node at a given position

Step to delete:

Getting the node that is to be deleted
Update the next pointer of the previous node is the next node
Update the previous pointer of the next node is the previous node

def delete_node_at_index(self, index: int):
  node_len = self.get_len()
  if (index < 0 or index >= node_len):
    return None

  if (index == 0):
    return self.delete_first_node()

  if (index == node_len - 1):
    return self.delete_last_node()
  
  node_delete = self.get_node_at_index(index)

  node_delete.prev.next = node_delete.next
  node_delete.next.prev = node_delete.prev

Difference between Singly Linked List and Doubly Linked List

Both the singly linked list and the doubly linked list are the data structures to store a sequence of pointers.

But they still have differences like below:

Singly-linked list:

Having two segments: data and link
Only the last node points to the null
The direction is allowed one way from head to tail
Want to save memory, and do not need to perform searching
Require less memory

Doubly-linked list:

Having three segments: data and two links
Both the previous pointer of the first node and the next pointer of the last node are null
The direction is allowed both forward and backward
When we want to search
Require more memory

Conclusion

In this article, I showed you how to set up doubly linked lists in Python, and the difference between a singly linked list and a doubly linked list.

Hope this article will be useful to you.

My door is always open if you have any comments.

Document references:

https://www.geeksforgeeks.org/data-structures/linked-list/doubly-linked-list/
https://viblo.asia/p/cau-truc-du-lieu-va-giai-thuat-danh-sach-lien-ket-doi-doubly-linked-list-924lJ82WKPM

Bài viết

Thẻ