Linked List

Intro

A linked list is a data structure that implements the List ADT by storing elements in individual nodes connected via pointers, rather than in contiguous memory like arrays. Each node contains data and a reference to the next node, the previous node, or both.

Linked List Data Structure

Components

• Node: A structure containing data and a link (pointer) to the next node.
• Head: A pointer to the first node in the list, or null if the list is empty
• Null/Terminator: The final node points to null

Types of Linked Lists

• Singly Linked List: Each node points only to the next node.
• Doubly Linked List: Nodes have two pointers, one pointing to the next node and one to the previous node, allowing traversal in both directions.
• Circular Linked List: The last node points back to the first node instead of null

Implementations

Python Implementation

class LinkedList:
  def __init__(self) -> None:
    self.head = None
 
  def append(self, data):
    node = Node(data)
    if not self.head:
      self.head = node
      return
 
    last = self.head
    while last.next:
      last = last.next
    last.next = node
 
  def print_list(self):
    curr = self.head
    while curr:
      print(f"{curr.data} -> ", end="")
      curr = curr.next
    print("None")

# Example usage
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.print_list()  # 10 -> 20 -> 30 -> None