Linked Lists - potatoscript/dsa GitHub Wiki

🧩 What is a Linked List?

Imagine a chain of paper notes 📝.
Each note has:

• 📦 A piece of data (like a name)
• ➡️ A pointer to the next note

Together, they form a chain — that’s a Linked List!

---

🖼️ Visual Example:

[🧸 Tom ] ➡️ [🐶 Max ] ➡️ [🐱 Leo ] ➡️ null

Each box is called a Node:

• It stores something (like “Tom”)
• And knows where the next one is!

---

🧠 Why Use a Linked List?

Compared to an array:

• ✅ Easier to grow and shrink
• ✅ Insert/delete from the middle? No problem!
• ❌ But slower to access by index

---

🧃 Real-World Analogy

Situation	Linked List Comparison
🏃‍♂️ People holding hands	Each person knows who's next
🚂 Train cars connected	Each car links to the next
📬 Letters with directions	“Go to box 2” written on each

---

💻 C# Code: Simple Linked List

Define a Node:

public class Node
{
    public string data;
    public Node next;

    public Node(string value)
    {
        data = value;
        next = null;
    }
}

Create and Connect Nodes:

Node first = new Node("Tom");
Node second = new Node("Max");
Node third = new Node("Leo");

first.next = second;
second.next = third;

---

🧭 How Does It Work?

You only need the first node (called the head), then you can follow the links.

first → second → third

To get all names:

Node current = first;
while (current != null)
{
    Console.WriteLine(current.data);
    current = current.next;
}

---

🧪 Array vs Linked List

Feature	Array	Linked List
🔢 Access by index	Fast (O(1))	Slow (O(n))
➕ Insert/delete	Slow (O(n))	Fast (O(1) if at head)
📏 Size	Fixed	Dynamic
🧠 Memory use	Compact	More memory (extra pointers)

---

🧩 Parts of a Linked List

A basic singly linked list node has:

• data: the value (e.g., "Dog")
• next: the link to the next node

There are other types too!

---

🔄 Types of Linked Lists

Type	Description
Singly Linked List	One-way chain →
Doubly Linked List	Two-way chain ↔
Circular Linked List	Loops around 🔄

---

🧵 Singly Linked List

[ A ] → [ B ] → [ C ] → null

🧷 Doubly Linked List

null ← [ A ] ⇄ [ B ] ⇄ [ C ] → null

🔁 Circular Linked List

[ A ] → [ B ] → [ C ]
   ↑               ↓
   ←←←←←←←←←←←←←←←←←

---

🎓 Big O Notation

Operation	Time Complexity
Insert at head	O(1)
Insert at end	O(n)
Delete at head	O(1)
Delete at end	O(n)
Access by index	O(n)
Search	O(n)

---

📜 Fun With Code: Traverse a List

Node current = head;
while (current != null)
{
    Console.WriteLine("🧡 " + current.data);
    current = current.next;
}

---

🔨 Insert at the Beginning

Node newHead = new Node("Newbie");
newHead.next = head;
head = newHead;

---

🔧 Insert at the End

Node current = head;
while (current.next != null)
{
    current = current.next;
}
current.next = new Node("LastOne");

---

🗑️ Delete a Node

Delete head:

head = head.next;

Delete specific:

Node current = head;
while (current.next != null)
{
    if (current.next.data == "Max")
    {
        current.next = current.next.next;
        break;
    }
    current = current.next;
}

---

🚨 Pitfalls to Avoid

Mistake	What Happens
❌ Breaking the chain	You lose the rest of the list
❌ Loop with null check	NullReferenceException!
❌ Infinite loop	You forgot to move to next!

---

👩‍🏫 Summary Time!

✅ Linked Lists are made of nodes
✅ Each node has a value and a pointer
✅ Good for adding/removing items
✅ Slower to search/access by position
✅ Many types: singly, doubly, circular