Understanding Linked Lists: How to Build Custom Linked Lists in Pseudocode

· 6 min read

Hey everyone, it’s alanturrr1703 back again! 😄 Today, we’re diving into a core data structure that forms the foundation for many algorithms: Linked Lists. Linked lists are a simple yet powerful way to store and manipulate data, and they’re essential for understanding more advanced data structures like queues, stacks, and graphs.

In this blog, we’ll cover what linked lists are, the different types (including singly, doubly, and circular linked lists), and how to implement operations like insertion, deletion, and traversal using pseudocode. Let’s get started! 🚀

What is a Linked List?

A linked list is a linear data structure consisting of nodes, where each node contains:

  1. Data: The actual data the node is storing.
  2. Next: A reference (or pointer) to the next node in the sequence.

Unlike arrays, linked lists don’t store elements in contiguous memory locations. This makes them more flexible for dynamic memory allocation but slower for direct access since elements must be accessed sequentially.

Basic Terminology:

  • Node: A single element in the linked list that stores the data and a reference to the next node.
  • Head: The first node in the list.
  • Tail: The last node in the list, which points to null (or None).

Advantages of Linked Lists:

  • Dynamic Size: Unlike arrays, linked lists can grow and shrink in size dynamically.
  • Efficient Insertions/Deletions: Inserting and deleting elements in a linked list is efficient (no shifting of elements, unlike arrays).

Disadvantages:

  • Sequential Access: You must traverse the list from the head to access any element, which can be slow (O(n) time complexity).
  • Extra Memory: Each node stores an additional pointer, which requires extra memory.

Types of Linked Lists

1. Singly Linked List

A singly linked list is a basic linked list where each node contains:

  • Data: The value stored in the node.
  • Next: A pointer/reference to the next node in the list.

Each node only points forward to the next node.

2. Doubly Linked List

A doubly linked list is an extension of the singly linked list, where each node has:

  • Data: The value stored in the node.
  • Next: A pointer to the next node.
  • Prev: A pointer to the previous node.

This allows traversal in both directions, forward and backward.

3. Circular Linked List

In a circular linked list, the last node points back to the first node, creating a circular loop. This can be implemented with both singly and doubly linked lists.

Operations on Linked Lists

Let’s break down the key operations you can perform on linked lists, including pseudocode for insertion, deletion, and traversal for each type.

1. Singly Linked List Operations

(a) Insertion at the Beginning

Function InsertAtBeginning(head, data):
    Create newNode with data
    newNode.next = head
    head = newNode
    Return head

(b) Insertion at the End

Function InsertAtEnd(head, data):
    Create newNode with data
    If head is NULL:
        head = newNode
        Return head
    Set current = head
    While current.next is not NULL:
        current = current.next
    current.next = newNode
    Return head

(c) Deletion from the Beginning

Function DeleteAtBeginning(head):
    If head is NULL:
        Print "List is empty"
        Return NULL
    head = head.next
    Return head

(d) Deletion from the End

Function DeleteAtEnd(head):
    If head is NULL:
        Print "List is empty"
        Return NULL
    If head.next is NULL:
        head = NULL
        Return head
    Set current = head
    While current.next.next is not NULL:
        current = current.next
    current.next = NULL
    Return head

(e) Traversal

Function Traverse(head):
    If head is NULL:
        Print "List is empty"
        Return
    Set current = head
    While current is not NULL:
        Print current.data
        current = current.next

2. Doubly Linked List Operations

(a) Insertion at the Beginning

Function InsertAtBeginning(head, data):
    Create newNode with data
    newNode.next = head
    If head is not NULL:
        head.prev = newNode
    head = newNode
    Return head

(b) Insertion at the End

Function InsertAtEnd(head, data):
    Create newNode with data
    If head is NULL:
        head = newNode
        Return head
    Set current = head
    While current.next is not NULL:
        current = current.next
    current.next = newNode
    newNode.prev = current
    Return head

(c) Deletion from the Beginning

Function DeleteAtBeginning(head):
    If head is NULL:
        Print "List is empty"
        Return NULL
    If head.next is not NULL:
        head.next.prev = NULL
    head = head.next
    Return head

(d) Deletion from the End

Function DeleteAtEnd(head):
    If head is NULL:
        Print "List is empty"
        Return NULL
    If head.next is NULL:
        head = NULL
        Return head
    Set current = head
    While current.next is not NULL:
        current = current.next
    current.prev.next = NULL
    Return head

(e) Traversal (Forward and Backward)

Function TraverseForward(head):
    Set current = head
    While current is not NULL:
        Print current.data
        current = current.next

Function TraverseBackward(tail):
    Set current = tail
    While current is not NULL:
        Print current.data
        current = current.prev

3. Circular Linked List Operations

(a) Insertion at the Beginning

Function InsertAtBeginningCircular(head, data):
    Create newNode with data
    If head is NULL:
        newNode.next = newNode  # Single node points to itself
        head = newNode
        Return head
    Set current = head
    While current.next is not head:
        current = current.next
    newNode.next = head
    current.next = newNode
    head = newNode
    Return head

(b) Insertion at the End

Function InsertAtEndCircular(head, data):
    Create newNode with data
    If head is NULL:
        newNode.next = newNode
        head = newNode
        Return head
    Set current = head
    While current.next is not head:
        current = current.next
    current.next = newNode
    newNode.next = head
    Return head

(c) Deletion from the Beginning

Function DeleteAtBeginningCircular(head):
    If head is NULL:
        Print "List is empty"
        Return NULL
    If head.next is head:
        head = NULL  # Single node case
        Return NULL
    Set current = head
    While current.next is not head:
        current = current.next
    head = head.next
    current.next = head
    Return head

(d) Deletion from the End

Function DeleteAtEndCircular(head):
    If head is NULL:
        Print "List is empty"
        Return NULL
    If head.next is head:
        head = NULL
        Return NULL
    Set current = head
    While current.next.next is not head:
        current = current.next
    current.next = head
    Return head

(e) Traversal

Function TraverseCircular(head):
    If head is NULL:
        Print "List is empty"
        Return
    Set current = head
    Do:
        Print current.data
        current = current.next
    While current is not head

Wrapping It Up

Linked lists are an incredibly versatile and foundational data structure used in a variety of applications, from low-level system programming to implementing complex data structures like queues, stacks, and hash maps. Understanding the basic operations and how to manipulate linked lists will make you a stronger programmer and help you tackle more complex problems in computer science.

Whether you’re working with singly, doubly, or circular linked lists, the pseudocode examples provided here will give you a solid foundation for implementing them in any programming language.

That’s all for today! I hope this blog helped clarify the concepts of linked lists and their operations. Until next time, happy coding! 🚀