Singly Linked Lists Data Structures

What You’ll Learn 📚

• Basic concepts and terminology of singly linked lists
• How to implement a singly linked list in Python
• Progressively complex examples and variations
• Common questions and troubleshooting tips
• Practice exercises to solidify your understanding

Introduction to Singly Linked Lists

A singly linked list is a type of data structure that consists of a sequence of elements, each containing a reference (or link) to the next element in the sequence. This structure is useful for dynamic data storage where the size can change over time.

Think of a singly linked list like a chain of paperclips where each clip is connected to the next one.

Key Terminology

• Node: An element of the linked list containing data and a reference to the next node.
• Head: The first node in the list.
• Tail: The last node, which points to null (or None in Python).

Simple Example: Creating a Node

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

# Creating a single node
a_node = Node(5)
print(a_node.data)  # Output: 5
print(a_node.next)  # Output: None

Building a Simple Singly Linked List

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

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

# Creating a linked list and adding elements
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

Progressively Complex Examples

Example 1: Traversing the List

def traverse(linked_list):
    current = linked_list.head
    while current:
        print(current.data)
        current = current.next

traverse(linked_list)

Example 2: Inserting a Node

def insert_after(node, data):
    if not node:
        return
    new_node = Node(data)
    new_node.next = node.next
    node.next = new_node

# Inserting a node after the first node
insert_after(linked_list.head, 1.5)

Example 3: Deleting a Node

def delete_node(linked_list, key):
    current = linked_list.head
    if current and current.data == key:
        linked_list.head = current.next
        current = None
        return
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next
    if current is None:
        return
    prev.next = current.next
    current = None

# Deleting a node with data '2'
delete_node(linked_list, 2)

Common Questions and Answers

1. What is the difference between a singly linked list and a doubly linked list?

   A singly linked list allows traversal in one direction (forward), while a doubly linked list allows traversal in both directions (forward and backward).

2. How do I know if my linked list is empty?

   Check if the head of the linked list is None. If it is, the list is empty.

3. Why use linked lists over arrays?

   Linked lists provide dynamic memory allocation, making them ideal for situations where the size of the data structure changes frequently.

Troubleshooting Common Issues

Be careful with None references! Accessing next on a None object will cause an error.

If you encounter an error, double-check your node connections and ensure you’re not trying to access properties on a None object.

Practice Exercises

• Implement a function to reverse a singly linked list.
• Create a function to find the middle element of the list.
• Write a function to detect a cycle in the linked list.

Remember, practice makes perfect. Keep experimenting with these exercises and you’ll become a linked list pro in no time! 💪

Additional Resources

• Python Data Structures Documentation
• GeeksforGeeks Linked List Tutorial