Stack Using Linked List vs Array Stack Trade-offs in DSA Javascript - Build Both Approaches

Stack Using Linked List vs Array Stack Trade-offs

📖 Scenario: Imagine you are building a simple web app that needs to manage a stack of tasks. You want to understand how to create a stack using two different methods: an array and a linked list. This will help you see the differences and trade-offs between these two ways.

🎯 Goal: You will build two stacks: one using an array and one using a linked list. Then, you will compare how they work by pushing and popping items. This will help you learn the basics of stacks and see the pros and cons of each method.

📋 What You'll Learn

Create a stack using an array with push and pop methods

Create a stack using a linked list with push and pop methods

Use a variable to track the maximum size for the array stack

Push three items to both stacks

Pop one item from both stacks

Print the current state of both stacks

💡 Why This Matters

🌍 Real World

Stacks are used in many real-world applications like undo features in text editors, browser history, and expression evaluation.

💼 Career

Understanding stack implementations helps in writing efficient code and preparing for technical interviews where data structure knowledge is tested.

1

Create an Array Stack

Create a variable called arrayStack as an empty array. Then create a variable called maxSize and set it to 5.

DSA Javascript

// Create an empty array called arrayStack
// Create a variable maxSize and set it to 5
// Your code here

Hint

Use [] to create an empty array. Use const to declare variables.

2

Create a Linked List Stack

Create a class called Node with a constructor that takes value and sets this.value and this.next to null. Then create a class called LinkedListStack with a constructor that sets this.top to null and this.size to 0.

DSA Javascript

const arrayStack = [];
const maxSize = 5;
// Create class Node with constructor(value)
// Create class LinkedListStack with constructor()
// Your code here

Hint

Use class keyword to create classes. The constructor sets initial values.

3

Add Push and Pop Methods

Add a method called push to LinkedListStack that takes value, creates a new Node, sets its next to the current top, updates top to the new node, and increments size. Add a method called pop that removes the top node, updates top, decrements size, and returns the popped value. Also, add pushToArrayStack and popFromArrayStack functions that push to and pop from arrayStack respecting maxSize.

DSA Javascript

const arrayStack = [];
const maxSize = 5;

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

class LinkedListStack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Add push(value) method
  // Add pop() method
}

// Add pushToArrayStack(value) function
// Add popFromArrayStack() function
// Your code here

Hint

Remember to check if the stack is empty before popping. For the array stack, check the size before pushing.

4

Use Both Stacks and Show Results

Create an instance of LinkedListStack called linkedListStack. Push the values 10, 20, and 30 to both linkedListStack and arrayStack using the methods you created. Then pop one value from each stack. Finally, print the current state of arrayStack and the values in linkedListStack from top to bottom.

DSA Javascript

const arrayStack = [];
const maxSize = 5;

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

class LinkedListStack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

  pop() {
    if (this.top === null) return null;
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.size--;
    return poppedValue;
  }
}

function pushToArrayStack(value) {
  if (arrayStack.length < maxSize) {
    arrayStack.push(value);
  }
}

function popFromArrayStack() {
  if (arrayStack.length === 0) return null;
  return arrayStack.pop();
}

// Create linkedListStack instance
// Push 10, 20, 30 to both stacks
// Pop one value from both stacks
// Print arrayStack
// Print linkedListStack values from top to bottom
// Your code here

Hint

Use console.log to print. To print linked list stack, start from top and collect values until null.

Practice

1. Which of the following is a key advantage of using a linked list to implement a stack compared to using an array?

easy

A. Dynamic size without needing to resize

B. Faster access to elements by index

C. Uses less memory overall

D. Simpler syntax to implement

Solution

1. Step 1: Understand stack size behavior in arrays

   Arrays have fixed size or need resizing which costs time and memory.

2. Step 2: Understand linked list size behavior

   Linked lists grow dynamically by adding nodes without resizing.

3. Final Answer:

   Dynamic size without needing to resize -> Option A

4. Quick Check:

   Linked list stacks grow dynamically = B [OK]

Hint: Linked lists grow dynamically, arrays need resizing [OK]

Common Mistakes:

• Thinking arrays resize automatically without cost
• Confusing access speed advantage
• Assuming linked lists use less memory

2. Which of the following is the correct way to push an element onto a stack implemented using an array in JavaScript?

easy

A. stack.insert(element);

B. stack.add(element);

C. stack.append(element);

D. stack.push(element);

Solution

1. Step 1: Recall JavaScript array methods

   The method to add an element at the end of an array is push().

2. Step 2: Match method to stack push operation

   Stack push adds element on top, which is end of array, so push() is correct.

3. Final Answer:

   stack.push(element); -> Option D

4. Quick Check:

   Array push method = stack.push(element) [OK]

Hint: Use push() to add element at array end [OK]

Common Mistakes:

• Using non-existent methods like add() or append()
• Confusing push with pop
• Trying to use insert() which is not an array method

3. Consider this JavaScript code using a linked list stack implementation:

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

class Stack {
  constructor() {
    this.top = null;
  }
  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
  }
  pop() {
    if (!this.top) return null;
    const val = this.top.value;
    this.top = this.top.next;
    return val;
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

What is the output?

medium

A. 20
10
null

B. 10
20
null

C. null
10
20

D. 20
null
10

Solution

1. Step 1: Trace push operations

   Push 10: top points to node with value 10. Push 20: top points to node with value 20, next points to 10.

2. Step 2: Trace pop operations

   First pop returns 20, top moves to node with 10. Second pop returns 10, top becomes null. Third pop returns null as stack is empty.

3. Final Answer:

   20 10 null -> Option A

4. Quick Check:

   Stack LIFO pop order = 20, 10, null [OK]

Hint: Stack pops last pushed first (LIFO) [OK]

Common Mistakes:

• Assuming FIFO order instead of LIFO
• Forgetting to return null when empty
• Mixing push and pop order

4. The following code attempts to implement a stack using an array but has a bug:

class Stack {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items[this.items.length] = element;
  }
  pop() {
    return this.items.pop;
  }
}

What is the error and how to fix it?

medium

A. push method should use push() instead of indexing

B. pop method is missing parentheses; fix by using this.items.pop()

C. items array should be initialized as null

D. pop method should return this.items.pop without parentheses

Solution

1. Step 1: Identify pop method usage

   pop is a function, so calling this.items.pop without () returns the function itself, not the popped element.

2. Step 2: Fix pop method call

   Add parentheses to call the function: this.items.pop() returns the last element and removes it.

3. Final Answer:

   pop method is missing parentheses; fix by using this.items.pop() -> Option B

4. Quick Check:

   Call pop() with parentheses to execute [OK]

Hint: Remember to call pop() as a function with () [OK]

Common Mistakes:

• Forgetting parentheses on pop() call
• Changing push to incorrect method
• Initializing items as null instead of array

5. You want to implement a stack that can handle millions of push and pop operations efficiently without resizing overhead and with minimal memory waste. Which implementation is better and why?

1. Array-based stack
2. Linked list-based stack

hard

A. Array stack, because it has faster push and pop operations always

B. Array stack, because arrays use less memory per element

C. Linked list stack, because it grows dynamically and avoids resizing overhead

D. Linked list stack, because it allows random access to elements

Solution

1. Step 1: Consider resizing overhead in array stacks

   Arrays need resizing when full, which is costly for millions of operations.

2. Step 2: Consider linked list memory and dynamic growth

   Linked lists grow node by node, avoiding resizing and memory waste from unused array slots.

3. Final Answer:

   Linked list stack, because it grows dynamically and avoids resizing overhead -> Option C

4. Quick Check:

   Dynamic growth avoids resizing overhead = A [OK]

Hint: For huge stacks, linked lists avoid costly resizing [OK]

Common Mistakes:

• Assuming arrays always have faster push/pop
• Ignoring resizing cost in arrays
• Thinking linked lists allow random access