Singly Linked List

A singly linked list is a linear data structure where elements are stored in nodes, and each node contains data and a reference (or link) to the next node in the sequence. It provides dynamic memory allocation and efficient insertion/deletion at the beginning.

Features

Dynamic size - grows and shrinks during runtime
Memory efficient - allocates memory as needed
Fast insertion/deletion at the beginning (O(1))
Sequential access - elements accessed by traversing from head
Generic type support for type safety

Time Complexities

Operation	Time Complexity
Prepend	O(1)
Append	O(n)
Insert	O(n)
Remove First	O(1)
Remove Last	O(n)
Remove by Value	O(n)
Remove by Index	O(n)
Search	O(n)
Access by Index	O(n)

Basic Usage

Creating and Initializing

from algo.data_structs.lists.singly_linked_list import SinglyLinkedList

# Create empty list
ll = SinglyLinkedList()

# Check if empty
print(ll.is_empty())  # True
print(len(ll))        # 0
print(ll.size())      # 0

Adding Elements

# Prepend elements (add to beginning)
ll.prepend(3)
ll.prepend(2)
ll.prepend(1)
print(list(ll))  # [1, 2, 3]

# Append elements (add to end)
ll.append(4)
ll.append(5)
print(list(ll))  # [1, 2, 3, 4, 5]

# Extend with multiple elements
ll.extend([6, 7, 8])
print(list(ll))  # [1, 2, 3, 4, 5, 6, 7, 8]

# Insert at specific position
ll.insert(0, 0)     # Insert at beginning
ll.insert(4, 3.5)   # Insert in middle
ll.insert(len(ll), 9)  # Insert at end
print(list(ll))     # [0, 1, 2, 3, 3.5, 4, 5, 6, 7, 8, 9]

Accessing Elements

# Get head and tail
print(ll.get_head())  # 0 (first element)
print(ll.get_tail())  # 9 (last element)

# Access by index
print(ll.get(0))   # 0 (first element)
print(ll.get(5))   # 4 (sixth element)

# Modify elements
ll.set(1, 10)
print(ll.get(1))   # 10

# Get list length
print(len(ll))     # 11
print(ll.size())   # 11

Removing Elements

# Remove first element
first = ll.remove_first()
print(first)       # 0
print(list(ll))    # [10, 2, 3, 3.5, 4, 5, 6, 7, 8, 9]

# Remove last element
last = ll.remove_last()
print(last)        # 9
print(list(ll))    # [10, 2, 3, 3.5, 4, 5, 6, 7, 8]

# Remove by value (first occurrence)
result = ll.remove(3.5)
print(result)      # True
print(list(ll))    # [10, 2, 3, 4, 5, 6, 7, 8]

# Remove by index
removed = ll.remove_at(0)
print(removed)     # 10
print(list(ll))    # [2, 3, 4, 5, 6, 7, 8]

# Clear all elements
ll.clear()
print(len(ll))     # 0

Search Operations

ll = SinglyLinkedList()
ll.extend([1, 2, 3, 2, 4, 2])

# Find index of element (first occurrence)
print(ll.find(2))      # 1
print(ll.find(4))      # 4
print(ll.find(99))     # -1 (not found)

# Check if element exists
print(2 in ll)         # True
print(99 in ll)        # False

# Count occurrences
print(ll.count(2))     # 3
print(ll.count(1))     # 1
print(ll.count(99))    # 0 (non-existent)

List Manipulation

ll = SinglyLinkedList()
ll.extend([1, 2, 3, 4, 5])

# Reverse the list
ll.reverse()
print(list(ll))  # [5, 4, 3, 2, 1]

# Copy the list
ll_copy = ll.copy()
print(list(ll_copy))  # [5, 4, 3, 2, 1]

# Lists are independent
ll_copy.append(6)
print(len(ll))        # 5 (original unchanged)
print(len(ll_copy))   # 6 (copy modified)

# Convert to Python list
python_list = ll.to_list()
print(python_list)    # [5, 4, 3, 2, 1]
print(type(python_list))  # <class 'list'>

# Iteration
for item in ll:
    print(item)  # 5, 4, 3, 2, 1

Working with Different Types

Strings

str_ll = SinglyLinkedList()
str_ll.extend(['apple', 'banana', 'cherry'])

print(str_ll.find('banana'))   # 1
print(str_ll.count('apple'))   # 1
print('cherry' in str_ll)      # True

Mixed Types

mixed_ll = SinglyLinkedList()
mixed_ll.extend([1, 'hello', 3.14, True])

print(len(mixed_ll))    # 4
print(mixed_ll.get(1))  # 'hello'
print(mixed_ll.get(3))  # True

Custom Objects

class Person:
    def __init__(self, name: str, age: int):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return isinstance(other, Person) and self.name == other.name

people = SinglyLinkedList()
alice = Person("Alice", 30)
bob = Person("Bob", 25)

people.extend([alice, bob])
print(people.count(alice))    # 1
print(people.find(bob))       # 1
print(alice in people)        # True

Performance Characteristics

Insertion Performance

Prepend: O(1) - Always fast as it only modifies the head
Append: O(n) - Must traverse to the end
Insert at arbitrary position: O(n) - Must traverse to position

ll = SinglyLinkedList()

# Fast prepend operations
for i in range(1000):
    ll.prepend(i)  # O(1) each

# Slower append operations  
for i in range(100):
    ll.append(i)   # O(n) each

Memory Efficiency

Singly linked lists use memory efficiently by allocating nodes only as needed:

# Memory grows with elements
ll = SinglyLinkedList()
for i in range(10):
    ll.append(i)  # Each append allocates one new node

# Memory freed when elements removed
ll.clear()  # All nodes can be garbage collected

Error Handling

ll = SinglyLinkedList()

# Index errors for empty list
try:
    ll.get(0)  # IndexError: list index out of range
except IndexError:
    print("Cannot access empty list")

try:
    ll.remove_first()  # IndexError: remove from empty list
except IndexError:
    print("Cannot remove from empty list")

# Index errors for invalid indices
ll.extend([1, 2, 3])
try:
    ll.get(5)  # IndexError: list index out of range
except IndexError:
    print("Index out of range")

try:
    ll.insert(-1, 5)  # IndexError: negative index not allowed
except IndexError:
    print("Invalid insert index")

# Value error for non-existent elements
try:
    ll.remove(99)  # Returns False (doesn't raise error)
    print("Element not found")
except:
    pass

String Representation

ll = SinglyLinkedList()
ll.extend([1, 2, 3])

print(str(ll))   # SinglyLinkedList([1 -> 2 -> 3 -> None])
print(repr(ll))  # SinglyLinkedList(size=3, head=ListNode(1))

# Empty list representation
empty_ll = SinglyLinkedList()
print(str(empty_ll))  # SinglyLinkedList([])

Common Patterns

Building from Iterables

# From list
ll = SinglyLinkedList()
ll.extend([1, 2, 3, 4, 5])

# From tuple
ll2 = SinglyLinkedList()
ll2.extend((1, 2, 3))

# From range
ll3 = SinglyLinkedList()
ll3.extend(range(10))

# From another linked list
ll4 = SinglyLinkedList()
ll4.extend(ll)  # Copy elements from ll

Stack-like Usage (LIFO)

stack = SinglyLinkedList()

# Push elements (prepend for O(1) performance)
stack.prepend(1)
stack.prepend(2)
stack.prepend(3)
print(list(stack))  # [3, 2, 1]

# Pop elements
while not stack.is_empty():
    item = stack.remove_first()
    print(item)  # 3, 2, 1

Queue-like Usage (FIFO) - Less Efficient

# Note: This is inefficient for queues due to O(n) remove_last
queue = SinglyLinkedList()

# Enqueue (append to end)
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue (remove from front)
while not queue.is_empty():
    item = queue.remove_first()
    print(item)  # 1, 2, 3

Filtering Elements

ll = SinglyLinkedList()
ll.extend(range(10))

# Remove all even numbers
i = 0
while i < len(ll):
    if ll.get(i) % 2 == 0:
        ll.remove_at(i)
    else:
        i += 1

print(list(ll))  # [1, 3, 5, 7, 9]

Merging Lists

ll1 = SinglyLinkedList()
ll1.extend([1, 3, 5])

ll2 = SinglyLinkedList()
ll2.extend([2, 4, 6])

# Merge ll2 into ll1
ll1.extend(ll2)
print(list(ll1))  # [1, 3, 5, 2, 4, 6]

Finding and Replacing

ll = SinglyLinkedList()
ll.extend([1, 2, 3, 2, 4])

# Replace all occurrences of 2 with 20
for i in range(len(ll)):
    if ll.get(i) == 2:
        ll.set(i, 20)

print(list(ll))  # [1, 20, 3, 20, 4]

Use Cases

When to Use Singly Linked Lists

Good for:

Frequent insertion/deletion at the beginning
Unknown or highly variable data size
Memory-constrained environments
Implementing other data structures (stacks, queues)
Sequential access patterns

Examples:

# Undo/Redo functionality (stack-like)
undo_stack = SinglyLinkedList()
undo_stack.prepend("action1")
undo_stack.prepend("action2")
last_action = undo_stack.remove_first()

# Browser history (recent first)
history = SinglyLinkedList()
history.prepend("google.com")
history.prepend("github.com")

# Dynamic playlist
playlist = SinglyLinkedList()
playlist.append("song1.mp3")
playlist.append("song2.mp3")
playlist.insert(1, "favorite_song.mp3")

When NOT to Use Singly Linked Lists

Avoid for:

Frequent random access by index
Frequent insertion/deletion at the end
Memory access patterns requiring cache efficiency
When you need bidirectional traversal

Better alternatives:

# For random access, use dynamic array instead
from algo.data_structs.arrays.dynamic_array import DynamicArray
arr = DynamicArray()  # Better for arr[index] operations

# For queue operations, use deque instead
from collections import deque
queue = deque()  # Better for queue operations

Node Structure

The underlying ListNode class provides the building blocks:

from algo.data_structs.lists.singly_linked_list import ListNode

# Create individual nodes
node1 = ListNode(1)
node2 = ListNode(2, node1)  # Points to node1

print(node1.data)    # 1
print(node1.next)    # None
print(node2.data)    # 2
print(node2.next)    # node1

# String representation
print(str(node1))    # "1"
print(repr(node1))   # "ListNode(1)"

Performance Comparison

Operation	Singly Linked List	Dynamic Array	Python List
Prepend	O(1)	O(n)	O(n)
Append	O(n)	O(1) amortized	O(1) amortized
Insert Middle	O(n)	O(n)	O(n)
Remove First	O(1)	O(n)	O(n)
Remove Last	O(n)	O(1)	O(1)
Access by Index	O(n)	O(1)	O(1)
Search	O(n)	O(n)	O(n)
Memory Overhead	Low	Medium	Low

API Reference

Singly Linked List Implementation

A singly linked list is a linear data structure where each element (node) contains data and a reference (link) to the next node in the sequence. Unlike arrays, linked lists don't store elements in contiguous memory locations.

Key Features:

Dynamic size allocation
Efficient insertion/deletion at the beginning
Sequential access to elements
No memory waste (allocates exactly what's needed)

Time Complexities:

Access: O(n) - must traverse from head
Search: O(n) - linear search required
Insertion: O(1) at head, O(n) at arbitrary position
Deletion: O(1) at head, O(n) at arbitrary position
Append: O(n) - must traverse to end

Space Complexity: O(n)

`ListNode(data, next_node=None)`

Bases: Generic[T]

A node in a singly linked list.

Each node contains data and a reference to the next node.

Initialize a new list node.

Parameters:

Name	Type	Description	Default
`data`	`T`	The data to store in this node	required
`next_node`	`Optional[ListNode[T]]`	Reference to the next node (default: None)	`None`

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the node.

`SinglyLinkedList()`

Bases: Generic[T]

A singly linked list implementation with comprehensive operations.

This implementation maintains a reference to the head node and tracks the size for efficient length operations.

Initialize an empty singly linked list.

`contains(value)`

Check if a value exists in the list.

`iter()`

Return an iterator over the list elements.

`len()`

Return the number of elements in the list.

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the list.

`append(data)`

Add an element to the end of the list.

Time Complexity: O(n) - must traverse to the end

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to add	required

`clear()`

Remove all elements from the list.

Time Complexity: O(1)

`copy()`

Create a shallow copy of the list.

Time Complexity: O(n)

Returns:

Type	Description
`SinglyLinkedList[T]`	A new SinglyLinkedList with the same elements

`count(data)`

Count the number of occurrences of the specified value.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`data`	`T`	Value to count	required

Returns:

Type	Description
`int`	Number of occurrences

`extend(iterable)`

Extend the list by appending all elements from the iterable.

Time Complexity: O(k * n) where k is the number of elements to add and n is the current size (due to append being O(n))

Parameters:

Name	Type	Description	Default
`iterable`		Iterable containing elements to add	required

`find(data)`

Find the index of the first occurrence of the specified value.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`data`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of the first occurrence, or -1 if not found

`get(index)`

Get element at the specified index.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`index`	`int`	Index of element to retrieve	required

Returns:

Type	Description
`T`	Element at the specified index

Raises:

Type	Description
`IndexError`	If index is out of bounds

`get_head()`

Get the first element without removing it.

Time Complexity: O(1)

Returns:

Type	Description
`Optional[T]`	The first element, or None if list is empty

`get_tail()`

Get the last element without removing it.

Time Complexity: O(n)

Returns:

Type	Description
`Optional[T]`	The last element, or None if list is empty

`insert(index, data)`

Insert an element at the specified index.

Time Complexity: O(n) - may need to traverse to the position

Parameters:

Name	Type	Description	Default
`index`	`int`	Index where to insert (0-based)	required
`data`	`T`	Element to insert	required

Raises:

Type	Description
`IndexError`	If index is out of valid range

`is_empty()`

Check if the list is empty.

Returns:

Type	Description
`bool`	True if the list is empty, False otherwise

`prepend(data)`

Add an element to the beginning of the list.

Time Complexity: O(1)

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to add	required

`remove(data)`

Remove the first occurrence of the specified value.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`data`	`T`	Value to remove	required

Returns:

Type	Description
`bool`	True if element was found and removed, False otherwise

`remove_at(index)`

Remove and return element at the specified index.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`index`	`int`	Index of element to remove	required

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If index is out of bounds

`remove_first()`

Remove and return the first element.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If the list is empty

`remove_last()`

Remove and return the last element.

Time Complexity: O(n) - must traverse to find the second-to-last node

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If the list is empty

`reverse()`

Reverse the list in place.

Time Complexity: O(n) Space Complexity: O(1)

`set(index, data)`

Set element at the specified index.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`index`	`int`	Index where to set the value	required
`data`	`T`	New value to set	required

Raises:

Type	Description
`IndexError`	If index is out of bounds

`size()`

Get the number of elements in the list.

Returns:

Type	Description
`int`	The number of elements

`to_list()`

Convert the linked list to a Python list.

Time Complexity: O(n)

Returns:

Type	Description
`list[T]`	A Python list containing all elements

Singly Linked List

Features

Time Complexities

Basic Usage

Creating and Initializing

Adding Elements

Accessing Elements

Removing Elements

Search Operations

List Manipulation

Working with Different Types

Strings

Mixed Types

Custom Objects

Performance Characteristics

Insertion Performance

Memory Efficiency

Error Handling

String Representation

Common Patterns

Building from Iterables

Stack-like Usage (LIFO)

Queue-like Usage (FIFO) - Less Efficient

Filtering Elements

Merging Lists

Finding and Replacing

Use Cases

When to Use Singly Linked Lists

When NOT to Use Singly Linked Lists

Node Structure

Performance Comparison

API Reference

ListNode(data, next_node=None)

__repr__()

__str__()

SinglyLinkedList()

__contains__(value)

__iter__()

__len__()

__repr__()

__str__()

append(data)

clear()

copy()

count(data)

extend(iterable)

find(data)

get(index)

get_head()

get_tail()

insert(index, data)

is_empty()

prepend(data)

remove(data)

remove_at(index)

remove_first()

remove_last()

reverse()

set(index, data)

size()

to_list()

`ListNode(data, next_node=None)`

`repr()`

`str()`

`SinglyLinkedList()`

`contains(value)`

`iter()`

`len()`

`repr()`

`str()`

`append(data)`

`clear()`

`copy()`

`count(data)`

`extend(iterable)`

`find(data)`

`get(index)`

`get_head()`

`get_tail()`

`insert(index, data)`

`is_empty()`

`prepend(data)`

`remove(data)`

`remove_at(index)`

`remove_first()`

`remove_last()`

`reverse()`

`set(index, data)`

`size()`

`to_list()`