Linked List – A Complete Guide (GoNimbus DSA Tutorial)

🔹 What is a Linked List?

A Linked List is a linear data structure where elements (called nodes) are connected using pointers.
Unlike arrays, the data elements in a linked list are not stored in contiguous memory locations. Each node contains:

• Data → the actual value
• Next pointer → reference (link) to the next node in the list

[10 | *] → [20 | *] → [30 | *] → NULL

Here, each box represents a node, and NULL indicates the end of the list.

---

💡 Meaning of Traverse in Simple Words

To traverse a linked list (or array, tree, graph, etc.) means:

“Go through each element in order, from start to end (or in a defined sequence), to perform some operation — like printing, searching, or modifying.”

---

🧱 Example: Traversing a Linked List

Suppose we have this linked list:
10 → 20 → 30 → NULL

Traversing it means:

1. Start at the head node (10)
2. Move to the next node (20)
3. Then to the next node (30)
4. Stop when you reach NULL (end of the list)

During traversal, you can:

• Print each value
• Count nodes
• Search for a specific value

---

🧮 Example in Code (Pseudo-code)

current = head
while current is not NULL:
    print(current.value)
    current = current.next

This code “traverses” the list by visiting each node once.

---

🚀 In the GoNimbus Visualizer

When you click Traverse,
the animation highlights each node one by one — showing how a program would visit all nodes sequentially.

---

---

🔹 Why Linked List?

In arrays, inserting or deleting an element at any position requires shifting elements, which is time-consuming.
Linked lists solve this problem by dynamically linking nodes.

Operation	Array	Linked List
Insertion (at beginning)	O(n)	O(1)
Deletion (at beginning)	O(n)	O(1)
Random Access	O(1)	O(n)
Memory Usage	Fixed	Dynamic

---

🔹 Types of Linked Lists

1. Singly Linked List
   ➤ Each node links to the next node only.
   Example: 10 → 20 → 30 → NULL
2. Doubly Linked List
   ➤ Each node links to both the previous and next nodes.
   Example: NULL ← 10 ⇄ 20 ⇄ 30 → NULL
3. Circular Linked List
   ➤ The last node points back to the first node, forming a circle.
   Example: 10 → 20 → 30 → (back to 10)

---

🔹 Basic Operations on Linked List

Let’s explore some common linked list operations:

1. Insertion

• At the beginning
• At the end
• After a given node

// GoNimbus Example – Insert at the beginning
type Node struct {
    data int
    next *Node
}

func insertAtBeginning(head **Node, data int) {
    newNode := &Node{data: data}
    newNode.next = *head
    *head = newNode
}

2. Traversal

func traverse(head *Node) {
    for head != nil {
        fmt.Printf("%d → ", head.data)
        head = head.next
    }
    fmt.Println("NULL")
}

3. Deletion

func deleteNode(head **Node, key int) {
    temp := *head
    if temp != nil && temp.data == key {
        *head = temp.next
        return
    }
    for temp != nil && temp.next.data != key {
        temp = temp.next
    }
    if temp != nil {
        temp.next = temp.next.next
    }
}

---

🔹 Advantages

✅ Dynamic memory allocation
✅ Efficient insertion/deletion
✅ Flexible size

🔹 Disadvantages

❌ No random access (must traverse nodes)
❌ Extra memory for storing pointers

---

🔹 Real-World Applications

• Undo/Redo operations in editors
• Browser history (previous/next pages)
• Music playlists
• Memory management systems

---

🧠 Key Takeaways

• A Linked List is a dynamic data structure made of nodes.
• Ideal for frequent insertions and deletions.
• Variants like doubly and circular linked lists improve traversal flexibility.
• Understanding linked lists is essential before learning Stacks, Queues, and Trees.

---

---