🔗 Singly Linked List Basics

Welcome to your first advanced data structure! So far we’ve learned about arrays and slices, which are like boxes in a row. Now let’s learn about Linked Lists - where items are connected like links in a chain.

What is a Linked List? (Real Life Analogy)

Arrays = Bookshelf

• Fixed number of shelves
• Books are side by side
• Easy to jump to any book

Linked List = Treasure Hunt

• Each clue leads to the next clue
• Can add new clues anywhere
• No fixed size limit

Think of it like:

• Each item = A person in a line
• Connection = Each person holds the hand of the next person
• The chain = The whole line of people

How Linked Lists Work

The Basic Building Block: A Node

Each item in a linked list is stored in a Node. A node has two parts:

1. Data - The actual information (like a number, name, etc.)
2. Next - A pointer to the next node (like an arrow)

type Node struct {
    data int      // The actual data (number, name, etc.)
    next *Node    // Pointer to next node (like an arrow)
}

The Linked List Structure

type LinkedList struct {
    head *Node    // The first person in line
    size int      // How many people in line
}

Creating Your First Linked List

Step 1: Create Individual Nodes

// Create three people in line
person1 := &Node{data: 10, next: nil}  // First person, no one after them
person2 := &Node{data: 20, next: nil}  // Second person, no one after them yet
person3 := &Node{data: 30, next: nil}  // Third person, no one after them

// Connect them: person1 -> person2 -> person3
person1.next = person2  // person1 now points to person2
person2.next = person3  // person2 now points to person3

// Now we have a chain: 10 -> 20 -> 30

Step 2: Create the Linked List

// Create empty linked list
myList := &LinkedList{
    head: nil,  // No one in line yet
    size: 0,    // Empty
}

// Add first person
myList.head = person1
myList.size = 3

Adding Items to the Chain

Method 1: Add to the Beginning (New person at front of line)

func (ll *LinkedList) addToFront(data int) {
    // Create new person
    newPerson := &Node{data: data, next: nil}

    // New person holds hand of current first person
    newPerson.next = ll.head

    // New person becomes the first in line
    ll.head = newPerson

    ll.size++
}

// Example
list := &LinkedList{}
// Add 10, then 20, then 30 to front
list.addToFront(10)  // Line: 10
list.addToFront(20)  // Line: 20 -> 10
list.addToFront(30)  // Line: 30 -> 20 -> 10

Method 2: Add to the End (New person at back of line)

func (ll *LinkedList) addToEnd(data int) {
    // Create new person
    newPerson := &Node{data: data, next: nil}

    // If line is empty, new person is first
    if ll.head == nil {
        ll.head = newPerson
        ll.size++
        return
    }

    // Walk to the end of the line
    current := ll.head
    for current.next != nil {
        current = current.next  // Move to next person
    }

    // Last person now holds new person's hand
    current.next = newPerson
    ll.size++
}

// Example
list := &LinkedList{}
// Add 10, then 20, then 30 to end
list.addToEnd(10)  // Line: 10
list.addToEnd(20)  // Line: 10 -> 20
list.addToEnd(30)  // Line: 10 -> 20 -> 30

Reading the Chain

Print All Items

func (ll *LinkedList) printList() {
    // Start from first person
    current := ll.head

    // Walk through the line
    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next  // Move to next person
    }

    fmt.Println("END")
}

// Example
list := &LinkedList{}
list.addToEnd(10)
list.addToEnd(20)
list.addToEnd(30)
list.printList()  // Output: 10 -> 20 -> 30 -> END

Find an Item

func (ll *LinkedList) findItem(target int) int {
    current := ll.head
    position := 0

    // Walk through line looking for target
    for current != nil {
        if current.data == target {
            return position  // Found it!
        }
        current = current.next
        position++
    }

    return -1  // Not found
}

// Example
list := &LinkedList{}
list.addToEnd(10)
list.addToEnd(20)
list.addToEnd(30)

pos20 := list.findItem(20)  // Returns 1
pos50 := list.findItem(50)  // Returns -1 (not found)

Real Life Example: Grocery Shopping List

package main

import "fmt"

type ShoppingItem struct {
    item string
    next *ShoppingItem
}

type ShoppingList struct {
    first *ShoppingItem
    count int
}

func (sl *ShoppingList) addItem(item string) {
    newItem := &ShoppingItem{item: item, next: nil}

    if sl.first == nil {
        sl.first = newItem
    } else {
        // Find last item
        current := sl.first
        for current.next != nil {
            current = current.next
        }
        current.next = newItem
    }

    sl.count++
}

func (sl *ShoppingList) printList() {
    current := sl.first
    fmt.Println("Shopping List:")

    for current != nil {
        fmt.Printf("- %s\n", current.item)
        current = current.next
    }

    fmt.Printf("Total items: %d\n", sl.count)
}

func main() {
    list := &ShoppingList{}

    list.addItem("Milk")
    list.addItem("Bread")
    list.addItem("Eggs")
    list.addItem("Apples")

    list.printList()
}

Output:

Shopping List:
- Milk
- Bread
- Eggs
- Apples
Total items: 4

Removing Items from the Chain

Remove from Beginning

func (ll *LinkedList) removeFromFront() {
    if ll.head == nil {
        fmt.Println("List is empty!")
        return
    }

    // Second person becomes first
    ll.head = ll.head.next
    ll.size--
}

// Example
list := &LinkedList{}
list.addToEnd(10)
list.addToEnd(20)
list.addToEnd(30)
// List: 10 -> 20 -> 30

list.removeFromFront()
// List: 20 -> 30

Remove from End

func (ll *LinkedList) removeFromEnd() {
    if ll.head == nil {
        fmt.Println("List is empty!")
        return
    }

    // If only one person
    if ll.head.next == nil {
        ll.head = nil
        ll.size--
        return
    }

    // Find second-to-last person
    current := ll.head
    for current.next.next != nil {
        current = current.next
    }

    // Last person lets go
    current.next = nil
    ll.size--
}

// Example
list := &LinkedList{}
list.addToEnd(10)
list.addToEnd(20)
list.addToEnd(30)
// List: 10 -> 20 -> 30

list.removeFromEnd()
// List: 10 -> 20

Linked Lists vs Arrays

Practice Problems - Build Your Skills!

Exercise 1: To-Do List

Create a linked list where each node contains a task (string). Add functions to:

• Add a new task
• Mark task as complete (remove it)
• Show all tasks
• Count total tasks

Exercise 2: Music Playlist

Create a linked list for songs. Each node has song title and artist. Add functions to:

• Add song to playlist
• Play next song (remove from front)
• Show current playlist
• Find songs by artist

Exercise 3: Number Chain

Create a linked list of numbers. Add functions to:

• Add numbers to the list
• Calculate sum of all numbers
• Find the largest number
• Remove all even numbers

Common Problems and Solutions

Problem: Infinite Loop

// WRONG: This creates a cycle!
node1 := &Node{data: 1}
node2 := &Node{data: 2}
node1.next = node2
node2.next = node1  // Points back to node1 - INFINITE LOOP!

Problem: Losing the Chain

// WRONG: This breaks the chain!
head = head.next  // Lost the first node forever!

Solution: Always keep track of nodes

// RIGHT: Keep reference to removed node
removed := head
head = head.next
// Now you can still access 'removed' if needed

Key Takeaways - What You Learned

• Nodes are the building blocks with data and next pointers
• Head points to the first node in the chain
• Adding to front is fast, adding to end requires walking the list
• Traversal means walking through the chain using next pointers
• Linked lists can grow dynamically unlike arrays

Next: Discover advanced singly linked list operations like reversing, finding cycles, and merging lists! 🔄

Ready for more advanced linked list techniques? Let’s explore reversing, cycles, and complex operations! 🚀