Đinh Thành Công Blog | Danh mục | Data structure: Singly Linked List

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 Singly Linked List?

A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element is connected only to its next element using a pointer.

How to implement in Python

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

Setup

Create a new file.

mkdir singly_linked_list
cd singly_linked_list
vi singly_linked_list.py

Create a new class with the name Node

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

Create a new class SinglyLinkedList

class SinglyLinkedList:
  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, and the next pointer is the head node.
Update head node and new node created.

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

Insert a node at the end

Step to insert:

Create a new node, and the next pointer is None
Update last node pointer is a new node created

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

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

  new_node = Node(data)
  current = self.head

  while current.next:
    current = current.next
  current.next = new_node

Insert a node at a given position

Step to insert:

Get an index of node B
Create a new node, and the pointer is now node C
Update node B pointer is a new node created

def insert_at_index(self, data: int, index: int):
  if (index < 0):
    return None
  
  if (index == 0):
    return self.insert_at_head(data)

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

Deletion

There are three types:

At the begginning
At the end
At a given position

Delete a node at the beginning

Step to delete:

Get the second node in the list
Update head node is the second node

def delete_first_node(self):
  if (self.head is None):
    return None

  new_first_node = self.head.next
  self.head = new_first_node

Delete a node at the end

Step to delete:

Get near the last node in the list
Update next pointer this node is None

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

Delete a node at a given position

Step to delete:

Get the previous node, the next node, and the node that should be deleted
Update the previous node pointer is the next node

def delete_node_at_index(self, index: int):
  if (self.head is None or index < 0):
    return None
  
  if (index == 0):
    return self.delete_first_node()
  
  if (index >= self.get_len() - 1):
    return self.delete_last_node()
  
  prev_node = self.get_node_at_index(index - 1)
  del_node = self.get_node_at_index(index)
  next_node = del_node.next

  prev_node.next = next_node