Singly Linked List

Singly linked list in Python

A singly linked list in Python is a linear data structure where each element (node) points to the next element in the sequence. Each node consists of two parts:

  • data: stores the actual value.
  • next: points to the next node in the list (or None if it is the last node).

Here’s an example of using a singly linked list in Python.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)

    def delete(self, data):
        if not self.head:
            return
        
        if self.head.data == data:  # If head needs to be deleted
            self.head = self.head.next
            return

        current = self.head
        while current.next and current.next.data != data:
            current = current.next
        
        if current.next:  # If found, delete the node
            current.next = current.next.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()

ll.delete(2)
ll.display()

Output

1 -> 2 -> 3 -> None
1 -> 3 -> None

Explanation

This code defines a singly linked list with three basic operations:

  • Appending a Node (append) – Adds a new node at the end.
  • Deleting a Node (delete) – Removes a node by its value.
  • Displaying the List (display) – Prints the list in order.

1. Node Class (Node)

Each node in the linked list contains:

  • data → The value stored in the node.
  • next → A pointer to the next node in the list.
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  • When a Node object is created, its data is set, and next is None (meaning no next node yet).

2. LinkedList Class (LinkedList)

This class manages the linked list operations.

(a) Initializing the Linked List:

class LinkedList:
    def __init__(self):
        self.head = None  # Initially, the list is empty.
  • self.head stores the first node of the linked list.
  • If head is None, the list is empty.

(b) Append a Node (append)

Adds a new node to the end of the list.

def append(self, data):
    if not self.head:  # If the list is empty, set head to new node
        self.head = Node(data)
        return

    current = self.head
    while current.next:  # Traverse to the last node
        current = current.next
    current.next = Node(data)  # Attach the new node at the end
  • If head is None, the list is empty, so we set head = Node(data).
  • Otherwise, we traverse (while current.next) until we reach the last node.
  • Then, we create a new node and attach it to the last node.

(c) Delete a Node (delete)

Removes a node containing a specific value.

def delete(self, data):
    if not self.head:  # If list is empty, do nothing
        return
    
    if self.head.data == data:  # If head is to be deleted
        self.head = self.head.next
        return

    current = self.head
    while current.next and current.next.data != data:  # Find the node before the one to delete
        current = current.next
    
    if current.next:  # If the node is found, remove it
        current.next = current.next.next
  • If the list is empty, nothing happens.
  • If the node to delete is the head, move head to the next node.
  • Otherwise, we traverse to find the node before the one to be deleted.
  • If found, we adjust the next pointer to skip the unwanted node.

(d) Display the List (display)

Prints all nodes in order.

def display(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")
  • Starts at head and prints each node’s data.
  • Stops when current becomes None.

Usage Example

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # Output: 1 -> 2 -> 3 -> None

ll.delete(2)
ll.display()  # Output: 1 -> 3 -> None
Edit this page
Linked List Introduction
Overview of Linked Lists
Stack
Stack data structure and its operations