Why Linked List Exists and What Problem It Solves in DSA Javascript - Why It Works

Concept Flow - Why Linked List Exists and What Problem It Solves

Start: Need to store items

↓

Use Array?

↓

Fixed size

↓

Problem: resizing costly

↓

Linked List: flexible size

↓

Add/remove nodes easily

↓

Problem solved: dynamic data storage

Shows decision from using arrays to linked lists due to resizing and flexibility needs.

Execution Sample

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Defines a node structure for linked list with value and pointer to next node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create first node with value 10	Node(10)	head -> Node(10)	head -> [10 | null]
2	Create second node with value 20	Node(10) -> Node(20)	Node(10).next -> Node(20)	head -> [10 | *] -> [20 | null]
3	Create third node with value 30	Node(10) -> Node(20) -> Node(30)	Node(20).next -> Node(30)	head -> [10 | *] -> [20 | *] -> [30 | null]
4	Add node dynamically without resizing	3 nodes linked	Pointers updated as above	head -> [10 | *] -> [20 | *] -> [30 | null]
5	End	List ready with 3 nodes	No pointer change	head -> [10 | *] -> [20 | *] -> [30 | null]

💡 Linked list built dynamically solving fixed size array problem

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
head	null	Node(10)	Node(10)	Node(10)	Node(10)
Node(10).next	null	null	Node(20)	Node(20)	Node(20)
Node(20).next	null	null	null	Node(30)	Node(30)
Node(30).next	null	null	null	null	null

Key Moments - 3 Insights

Why can't we just use arrays for all data storage?

Arrays have fixed size or costly resizing; linked lists allow dynamic size without resizing, as shown in steps 1-4 of execution_table.

How does linked list solve the resizing problem?

Linked list adds nodes by changing pointers without moving existing data, unlike arrays that need copying; see pointer changes in steps 2 and 3.

What does 'next' pointer do in a node?

'next' points to the next node in the list, linking nodes together; this is shown in variable_tracker where Node(10).next points to Node(20).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what does Node(10).next point to?

A null

B Node(30)

C Node(20)

D head

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 2 in execution_table.

At which step does the linked list first have more than one node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'Nodes in List' column in execution_table to see when second node is added.

If arrays did not have resizing issues, what would change in the concept_flow?

A We would always choose arrays, skipping linked lists

B We would still use linked lists for flexibility

C Linked lists would be used for sorting only

D No change, linked lists solve other problems

💡 Hint

Refer to the decision point in concept_flow where array resizing problem leads to linked list choice.

Concept Snapshot

Linked List stores items as nodes linked by pointers.
Unlike arrays, linked lists grow dynamically without resizing.
Each node has a value and a pointer to next node.
Linked lists solve fixed size and costly resizing problems of arrays.
Useful for dynamic data where size changes often.

Full Transcript

Linked lists exist because arrays have fixed size or resizing costs. Linked lists store data in nodes linked by pointers, allowing dynamic size. Each node holds a value and a pointer to the next node. This solves the problem of resizing arrays when data grows. The execution shows creating nodes and linking them step-by-step, updating pointers to build the list dynamically.

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 store data in contiguous memory locations

D. Because linked lists are faster for accessing elements by index

Solution

1. Step 1: Understand array limitations

   Arrays store elements in contiguous memory, so inserting or deleting in the middle requires shifting elements, 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 = B [OK]

Hint: Linked lists excel at insert/delete without moving all elements [OK]

Common Mistakes:

• Thinking linked lists always use less memory
• Believing linked lists store data contiguously
• Assuming linked lists have fast random access

2. Which of the following is the correct way to define a node in a singly linked list in JavaScript?

easy

A. function Node(value) { this.next = value; this.value = null; }

B. function Node(value) { this.value = value; this.prev = null; }

C. function Node(value) { this.value = null; this.next = value; }

D. function Node(value) { this.value = value; this.next = null; }

Solution

1. Step 1: Identify node properties for singly linked list

   A node should store its value and a pointer to the next node, usually called 'next'.

2. Step 2: Check each option's correctness

   function Node(value) { this.value = value; this.next = null; } correctly assigns value and sets next to null initially. Options A, B, and D misuse 'prev' or swap value and next.

3. Final Answer:

   function Node(value) { this.value = value; this.next = null; } -> Option D

4. Quick Check:

   Node with value and next = C [OK]

Hint: Node must have value and next pointer for singly linked list [OK]

Common Mistakes:

• Using 'prev' instead of 'next' for singly linked list
• Swapping value and next assignments
• Not initializing next to null

3. What will be the output of the following code snippet?

function Node(value) {
  this.value = value;
  this.next = null;
}

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

let current = head;
let result = '';
while(current) {
  result += current.value + ' -> ';
  current = current.next;
}
result += 'null';
console.log(result);

medium

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

B. 1 -> 2 -> null

C. null -> 1 -> 2 -> 3

D. 3 -> 2 -> 1 -> null

Solution

1. Step 1: Build the linked list nodes

   Nodes with values 1, 2, and 3 are created and linked: head -> 1 -> 2 -> 3 -> null.

2. Step 2: Traverse and build output string

   The while loop appends each node's value followed by ' -> ' until current is null, then adds 'null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Traverse nodes 1,2,3 then null = A [OK]

Hint: Traverse nodes from head, append values with arrows, end with null [OK]

Common Mistakes:

• Stopping traversal too early
• Appending 'null' at start instead of end
• Reversing node order in output

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

function Node(value) {
  this.value = value;
  this.next = null;
}

const head = new Node(1);
head.next = new Node(2);

const newNode = new Node(4);
newNode.next = head.next;
head = newNode;

medium

A. newNode.next should be null instead of head.next

B. Cannot assign to 'head' because it is a constant

C. Missing function to insert node

D. Node constructor is incorrect

Solution

1. Step 1: Identify variable declaration

   head is declared with const, so it cannot be reassigned to a new value.

2. Step 2: Check the reassignment line

   The line 'head = newNode;' tries to assign a new object to head, causing an error.

3. Final Answer:

   Cannot assign to 'head' because it is a constant -> Option B

4. Quick Check:

   Reassigning const variable = A [OK]

Hint: const variables cannot be reassigned after declaration [OK]

Common Mistakes:

• Thinking newNode.next should be null
• Assuming missing insert function causes error
• Believing Node constructor is wrong

5. You want to implement a playlist where songs can be added or removed anywhere efficiently. Which data structure best solves this problem and why?

hard

A. Array, because it allows fast random access to songs

B. Queue, because it follows first-in-first-out order

C. Linked list, because it allows efficient insertions and deletions anywhere

D. Stack, because it follows last-in-first-out order

Solution

1. Step 1: Understand playlist operations

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

2. Step 2: Compare data structures

   Arrays have slow insert/delete in middle due to shifting. Stacks and queues have restricted access order. Linked lists allow efficient insert/delete by changing pointers.

3. Final Answer:

   Linked list, because it allows efficient insertions and deletions anywhere -> Option C

4. Quick Check:

   Efficient insert/delete anywhere = D [OK]

Hint: Use linked list for efficient insert/delete anywhere [OK]

Common Mistakes:

• Choosing array for fast random access but ignoring insert/delete cost
• Confusing stack or queue with general insert/delete needs
• Ignoring linked list pointer advantages