Linked Lists: Comprehensive Guide

1. Blog Overview

Goal: Teach beginners everything about Linked Lists to confidently solve common data structure and algorithm interview problems.

---

2. Linked List Fundamentals

Concept	Description	Importance
Node	A container for data (strings, numbers, booleans, objects). Conceptually visualized as a circle.	Core Concept
Link	A pointer from one node to the next node in the sequence (e.g., A's next is B).	Core Concept
Linked List	A collection of many nodes linked together in a sequence.	Core Concept
Last Node	The final node in the list. Its next pointer is set to null or None, signifying the end.	High
Head	The very first node of the linked list.	High
Tail	The very last node of the linked list.	High
Ordered Data Structure	A key characteristic allowing sequential traversal by following next pointers from head to tail.	High
Node Position	Positions are typically zero-indexed (Head is at index 0).	Medium

---

3. Comparison: Linked List vs. Array

Feature	Array	Linked List	Importance
Memory Storage	Must be stored contiguously (blocks right next to each other in memory).	Non-contiguous (nodes can exist anywhere in memory, linked by pointers).	Critical Distinction
Insertion at Index	Requires shifting all subsequent elements to make space.	Requires only adjusting pointers (specifically two pointers).	Critical Distinction
Insertion Time Complexity	$O(N)$ (Worst case: inserting at index 0 requires shifting all $N$ elements).	$O(1)$ (Constant time, assuming you already have the reference to the insertion point).	Critical Distinction

---

4. Core Linked List Algorithms

A. Traversal (Visiting Every Node)

• Core Idea: You only need a reference to the head node to access the entire list.
• Mechanism: Use a current variable (pointer), starting at the head. In a loop, set current = current.next until current is null/None.

1. Iterative Solution

   • Uses a while current is not None: loop.
   • Inside the loop, print current.val and update current to current.next.

2. Recursive Solution

   • Base Case (Stopping): If head is None, return (handles end of list or empty list).
   • Recursive Step: Print head.val, then recursively call the function on head.next.

---

B. Linked List Values (Return all values in an Array)

Problem: Given the head, return a list (array) containing all node values in the correct order.

Complexity Analysis

• Time Complexity: $O(N)$ (Must visit every node once).
• Space Complexity: $O(N)$ (Required to store the output list of values).

1. Iterative Solution

   • Initialize an empty list/array.
   • Use a while loop to traverse.
   • Append current.val to the values list.
   • Move current = current.next.
   • Return the list after the loop finishes.

2. Recursive Solution (Using Helper Function)

   • Why a helper? To maintain the state of the values list without creating new list copies in every stack frame.
   • Structure:
     • The main function initializes an empty values list.
     • Calls a recursive helper function: fill_values(head, values).
   • Helper Logic:
     • Base Case: If head is None, return.
     • Recursive Step: Append head.val to values, then call fill_values(head.next, values).