Why Linked List Exists and What Problem It Solves in DSA Go - See It Work

Why Linked List Exists and What Problem It Solves

📖 Scenario: Imagine you are organizing a photo album. You want to add photos one by one, but you don't know how many photos you will have in total. You also want to be able to add or remove photos easily without moving all the others.This is similar to how computers store lists of items. Arrays are like photo albums with fixed pages, but linked lists are like a chain of photos where each photo points to the next one.

🎯 Goal: Build a simple linked list in Go to understand why linked lists exist and how they solve the problem of flexible and efficient data storage when the number of items changes.

📋 What You'll Learn

Create a linked list node structure with a value and a pointer to the next node

Create a linked list with three nodes connected

Add a variable to count the number of nodes

Traverse the linked list to print all node values

Print the count of nodes

💡 Why This Matters

🌍 Real World

Linked lists are used in real-world applications where data size changes often, like music playlists, undo features in apps, or managing tasks.

💼 Career

Understanding linked lists helps in software development jobs that require efficient data management and memory usage, such as backend development and systems programming.

1

Create a linked list node structure and three connected nodes

Create a struct called Node with two fields: value int and next *Node. Then create three nodes named node1, node2, and node3 with values 10, 20, and 30 respectively. Connect node1.next to node2 and node2.next to node3. Set node3.next to nil.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

func main() {
    // Create three nodes and connect them
}

Hint

Define the Node struct first. Then create nodes using &Node{value: ...}. Connect nodes by setting the next field.

2

Add a variable to count the number of nodes

Inside main, create an integer variable called count and set it to 0. This will keep track of how many nodes are in the linked list.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

func main() {
    node1 := &Node{value: 10}
    node2 := &Node{value: 20}
    node3 := &Node{value: 30}

    node1.next = node2
    node2.next = node3
    node3.next = nil

    // Create a count variable and set it to 0
}

Hint

Just add count := 0 inside the main function.

3

Traverse the linked list and count the nodes

Use a for loop with a variable current starting at node1. Loop while current != nil. Inside the loop, increase count by 1 and move current to current.next.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

func main() {
    node1 := &Node{value: 10}
    node2 := &Node{value: 20}
    node3 := &Node{value: 30}

    node1.next = node2
    node2.next = node3
    node3.next = nil

    count := 0

    // Traverse the linked list and count nodes
}

Hint

Use a for loop to move through each node until current is nil. Increase count inside the loop.

4

Print all node values and the count

Use a for loop with current starting at node1. Loop while current != nil. Inside the loop, print current.value followed by an arrow " -> ". After the loop, print "nil" on the same line. Then print "Total nodes: " followed by the count variable.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

func main() {
    node1 := &Node{value: 10}
    node2 := &Node{value: 20}
    node3 := &Node{value: 30}

    node1.next = node2
    node2.next = node3
    node3.next = nil

    count := 0

    current := node1
    for current != nil {
        count++
        current = current.next
    }

    // Print all node values followed by " -> " and then print "nil"
    // Then print the total count of nodes
}

Hint

Use fmt.Print inside the loop to print values and arrows. After the loop, print "nil". Then print the total count with fmt.Println.

Practice

1. Why do we use a linked list instead of an array in some cases?

easy

A. Because linked lists allow easy insertion and deletion without shifting elements

B. Because linked lists use less memory than arrays always

C. Because linked lists provide faster access to elements by index

D. Because linked lists store elements in contiguous memory locations

Solution

1. Step 1: Understand array limitations

   Arrays store elements in contiguous memory, so inserting or deleting elements requires shifting others, which is slow.

2. Step 2: Understand linked list advantages

   Linked lists store elements in nodes linked by pointers, so insertion and deletion can be done by changing pointers without shifting.

3. Final Answer:

   Because linked lists allow easy insertion and deletion without shifting elements -> Option A

4. Quick Check:

   Insertion/deletion ease = C [OK]

Hint: Linked lists excel at insert/delete without shifting [OK]

Common Mistakes:

• Thinking linked lists always use less memory
• Believing linked lists have faster index access
• Assuming linked lists store data contiguously

2. Which of the following is the correct way to declare a node struct for a singly linked list in Go?

easy

A. type Node struct { data int; next **Node }

B. type Node struct { data int; next Node }

C. type Node struct { data *int; next *Node }

D. type Node struct { data int; next *Node }

Solution

1. Step 1: Understand pointer usage in Go structs

   For linked lists, the next field must be a pointer to the next node to avoid copying the whole struct.

2. Step 2: Check each option

   type Node struct { data int; next *Node } uses *Node pointer correctly; B uses Node (value) which causes copying; C uses *int for data which is unnecessary; D uses **Node which is double pointer and unnecessary.

3. Final Answer:

   type Node struct { data int; next *Node } -> Option D

4. Quick Check:

   Next pointer = *Node [OK]

Hint: Next node must be a pointer to avoid copying [OK]

Common Mistakes:

• Using value type instead of pointer for next
• Using pointer for data unnecessarily
• Using double pointer for next

3. What will be the output of the following Go code snippet that creates a linked list and prints its elements?

type Node struct {
    data int
    next *Node
}

func main() {
    head := &Node{data: 1}
    second := &Node{data: 2}
    third := &Node{data: 3}
    head.next = second
    second.next = third

    current := head
    for current != nil {
        fmt.Print(current.data, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 1 -> 2 -> null

D. Compilation error

Solution

1. Step 1: Trace linked list creation

   Nodes created with data 1, 2, 3 linked in order: head -> second -> third.

2. Step 2: Trace printing loop

   Loop prints data of current node then moves to next until nil, so prints 1, 2, 3 in order, then prints "null".

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Print order matches linked list order [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Confusing order of nodes
• Forgetting to print null at end
• Assuming reverse order

4. The following Go code tries to insert a new node with value 4 after the head node in a linked list. What is the bug?

type Node struct {
    data int
    next *Node
}

func main() {
    head := &Node{data: 1}
    second := &Node{data: 2}
    head.next = second

    newNode := &Node{data: 4}
    newNode.next = head.next
    head = newNode
}

medium

A. No bug; code works correctly

B. The newNode.next should be nil

C. The new node is not linked correctly; head pointer is overwritten

D. The second node is lost because head.next is nil

Solution

1. Step 1: Understand intended insertion

   The goal is to insert newNode after head, so newNode.next should point to head.next, then head.next should point to newNode.

2. Step 2: Identify bug in code

   The code sets newNode.next = head.next correctly but then overwrites head pointer itself with newNode, losing original head node and breaking list.

3. Final Answer:

   The new node is not linked correctly; head pointer is overwritten -> Option C

4. Quick Check:

   Head pointer changed incorrectly = D [OK]

Hint: Insert by changing next pointers, not head itself [OK]

Common Mistakes:

• Overwriting head instead of head.next
• Not linking newNode.next properly
• Assuming newNode.next should be nil

5. You want to implement a playlist where songs can be added or removed anywhere efficiently. Why is a linked list a better choice than an array for this use case?

hard

A. Because linked lists allow dynamic memory allocation and efficient insertions/removals anywhere

B. Because linked lists provide faster random access to songs by index

C. Because arrays automatically resize without overhead

D. Because linked lists store all songs contiguously in memory

Solution

1. Step 1: Understand playlist operations

   Adding/removing songs anywhere means frequent insertions and deletions at arbitrary positions.

2. Step 2: Compare array and linked list

   Arrays require shifting elements on insert/delete, which is slow. Linked lists use pointers to insert/delete nodes efficiently without shifting.

3. Final Answer:

   Because linked lists allow dynamic memory allocation and efficient insertions/removals anywhere -> Option A

4. Quick Check:

   Efficient insert/delete = A [OK]

Hint: Linked lists excel at dynamic insertions/removals [OK]

Common Mistakes:

• Thinking linked lists have faster random access
• Assuming arrays resize without cost
• Believing linked lists store data contiguously