In a previous post, I introduced data structure including: What are data structures? Classification of data structure.

In this article, I will show you how to set up a singly linked list algorithm in Python.

Table of content

• What is a Linked List data structure?
• What is a Singly Linked List?
• How to implement in Python
• Setup
• Insertion
• Deletion
• Conclusion

What is a Linked List data structure?

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:

1. Create a new node, and the next pointer is the head node.
2. 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:

1. Create a new node, and the next pointer is None
2. 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:

1. Get an index of node B
2. Create a new node, and the pointer is now node C
3. 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:

1. Get the second node in the list
2. 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:

1. Get near the last node in the list
2. 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:

1. Get the previous node, the next node, and the node that should be deleted
2. 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

Conclusion

In this article, I introduced linked lists and the algorithm settings for a single-linked list in Python.

Hope this article will be useful to you.

My door is always open if you have any comments.

Continue, You want to be able to setup a doubly linked list in Python that I will show you in the next article Doubly linked list.

Document references:

• https://www.geeksforgeeks.org/data-structures/linked-list/
• https://viblo.asia/p/cau-truc-du-lieu-va-giai-thuat-danh-sach-lien-ket-don-singly-linked-list-naQZRk0Xlvx