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

Stack Using Linked List vs Array Stack Trade-offs

📖 Scenario: Imagine you are building a simple program to manage a stack of books. You want to try two ways to store the books: one using a linked list and another using an array. This will help you understand how each method works and their differences.

🎯 Goal: You will create two stacks: one using a linked list and one using an array. You will add some books to each stack and then print the contents to see how they look. This will help you learn the trade-offs between these two stack implementations.

📋 What You'll Learn

Create a linked list based stack with push and print methods

Create an array based stack with push and print methods

Add the same books to both stacks

Print the contents of both stacks to compare

💡 Why This Matters

🌍 Real World

Stacks are used in many programs like undo features, browser history, and expression evaluation. Knowing different ways to build stacks helps choose the best method for your needs.

💼 Career

Understanding stack implementations and their trade-offs is important for software developers, especially when optimizing for memory or speed in applications.

1

Create a linked list based stack

Create a class called LinkedListStack with a nested Node class. Add a method push(String book) to add a book to the top of the stack. Also add a method printStack() to print all books from top to bottom.

DSA Java

// Your code here to create LinkedListStack class with push and printStack methods

Hint

Think of the stack as a pile of books where you add new books on top. The Node holds each book and points to the next one below it.

2

Create an array based stack

Create a class called ArrayStack with an array of String called books of size 5 and an integer top to track the top index. Add a method push(String book) to add a book to the stack and a method printStack() to print all books from top to bottom.

DSA Java

public class LinkedListStack {
    private Node top;

    private static class Node {
        String book;
        Node next;

        Node(String book) {
            this.book = book;
            this.next = null;
        }
    }

    public void push(String book) {
        Node newNode = new Node(book);
        newNode.next = top;
        top = newNode;
    }

    public void printStack() {
        Node current = top;
        while (current != null) {
            System.out.print(current.book + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

// Your code here to create ArrayStack class with push and printStack methods

Hint

Think of the array stack as a fixed shelf with 5 slots. You add books from left to right and keep track of the top slot.

3

Add books to both stacks

Create a public static void main(String[] args) method. Inside it, create one LinkedListStack object called linkedStack and one ArrayStack object called arrayStack. Use push to add these books in order: "Book1", "Book2", "Book3" to both stacks.

DSA Java

public class LinkedListStack {
    private Node top;

    private static class Node {
        String book;
        Node next;

        Node(String book) {
            this.book = book;
            this.next = null;
        }
    }

    public void push(String book) {
        Node newNode = new Node(book);
        newNode.next = top;
        top = newNode;
    }

    public void printStack() {
        Node current = top;
        while (current != null) {
            System.out.print(current.book + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class ArrayStack {
    private String[] books = new String[5];
    private int top = -1;

    public void push(String book) {
        if (top = 0; i--) {
            System.out.print(books[i] + " -> ");
        }
        System.out.println("null");
    }
}

// Your code here to create main method and push books to both stacks

Hint

Use the push method on both stacks to add the books in the same order.

4

Print the contents of both stacks

In the main method, after pushing the books, call printStack() on linkedStack and then on arrayStack to print their contents.

DSA Java

public class LinkedListStack {
    private Node top;

    private static class Node {
        String book;
        Node next;

        Node(String book) {
            this.book = book;
            this.next = null;
        }
    }

    public void push(String book) {
        Node newNode = new Node(book);
        newNode.next = top;
        top = newNode;
    }

    public void printStack() {
        Node current = top;
        while (current != null) {
            System.out.print(current.book + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class ArrayStack {
    private String[] books = new String[5];
    private int top = -1;

    public void push(String book) {
        if (top = 0; i--) {
            System.out.print(books[i] + " -> ");
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedListStack linkedStack = new LinkedListStack();
        ArrayStack arrayStack = new ArrayStack();

        linkedStack.push("Book1");
        linkedStack.push("Book2");
        linkedStack.push("Book3");

        arrayStack.push("Book1");
        arrayStack.push("Book2");
        arrayStack.push("Book3");

        // Print the contents of linkedStack and arrayStack
        linkedStack.printStack();
        arrayStack.printStack();
    }
}

Hint

Call printStack() on both stacks to see the order of books.

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. Accessing elements by index is faster.

B. Memory usage is always less than an array.

C. The stack size can grow dynamically without a fixed limit.

D. It uses less memory overhead per element.

Solution

1. Step 1: Understand stack size behavior in linked list

   A linked list stack can grow dynamically as nodes are added, limited only by available memory.

2. Step 2: Compare with array stack size

   An array stack has a fixed size or requires resizing, which can be costly and limits immediate growth.

3. Final Answer:

   The stack size can grow dynamically without a fixed limit. -> Option C

4. Quick Check:

   Dynamic size = B [OK]

Hint: Linked list stacks grow dynamically; arrays have fixed size [OK]

Common Mistakes:

• Thinking array stacks grow dynamically without resizing
• Assuming linked list uses less memory always
• Confusing access speed advantages

2. Which of the following is the correct way to declare an array-based stack of integers in Java?

easy

A. int stack = new int[10];

B. int[] stack = new int[10];

C. int[] stack = int[10];

D. int stack[] = int(10);

Solution

1. Step 1: Recall Java array declaration syntax

   In Java, arrays are declared with type[], variable = new type[size];

2. Step 2: Check each option

   int[] stack = new int[10]; matches correct syntax: int[] stack = new int[10]; others have syntax errors.

3. Final Answer:

   int[] stack = new int[10]; -> Option B

4. Quick Check:

   Correct Java array syntax = A [OK]

Hint: Java arrays use type[] var = new type[size]; [OK]

Common Mistakes:

• Missing 'new' keyword
• Using parentheses instead of brackets
• Declaring array without []

3. Consider the following Java code implementing a stack using a linked list. What will be printed after pushing 10, 20, then popping once?

class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

class Stack {
  Node top;
  void push(int x) {
    Node n = new Node(x);
    n.next = top;
    top = n;
  }
  int pop() {
    if (top == null) return -1;
    int val = top.data;
    top = top.next;
    return val;
  }
}

public class Main {
  public static void main(String[] args) {
    Stack s = new Stack();
    s.push(10);
    s.push(20);
    System.out.println(s.pop());
  }
}

medium

A. 20

B. null

C. 10

D. Compilation error

Solution

1. Step 1: Trace push operations

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

2. Step 2: Trace pop operation

   Pop removes top node (20), returns 20, top now points to node with 10.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Last pushed, first popped = 20 [OK]

Hint: Stack pop returns last pushed value [OK]

Common Mistakes:

• Confusing order of push and pop
• Assuming pop returns bottom element
• Ignoring null check in pop

4. The following code attempts to implement a stack using an array but has a bug. What is the error?

class ArrayStack {
  int[] stack = new int[5];
  int top = -1;
  void push(int x) {
    top++;
    stack[top] = x;
  }
}

medium

A. stack array should be declared static

B. top should start at 0, not -1

C. Array size should be dynamic

D. No check for stack overflow before push

Solution

1. Step 1: Analyze push method

   Push increments top and assigns value without checking if top exceeds array size.

2. Step 2: Identify missing overflow check

   Without checking top < stack.length, pushing beyond capacity causes ArrayIndexOutOfBoundsException.

3. Final Answer:

   No check for stack overflow before push -> Option D

4. Quick Check:

   Missing overflow check = A [OK]

Hint: Always check stack size before pushing [OK]

Common Mistakes:

• Assuming top starts at 0 is mandatory
• Thinking array must be dynamic always
• Confusing static keyword necessity

5. You need to implement a stack for a program where the maximum number of elements is unknown and memory efficiency is important. Which implementation is best and why?

hard

A. Linked list stack, because it grows dynamically and uses memory only as needed.

B. Linked list stack, because it uses less memory overhead per element than arrays.

C. Array stack, because it provides faster push and pop operations always.

D. Array stack, because arrays use less memory per element and resizing is automatic.

Solution

1. Step 1: Consider unknown max size and memory efficiency

   Unknown max size means dynamic growth is needed; linked list grows as needed without fixed size.

2. Step 2: Compare memory usage and operation speed

   Linked list uses extra memory per node for pointers but avoids wasted space from large arrays; resizing arrays can be costly.

3. Step 3: Choose best fit

   Linked list stack fits unknown size and memory efficiency better despite pointer overhead.

4. Final Answer:

   Linked list stack, because it grows dynamically and uses memory only as needed. -> Option A

5. Quick Check:

   Dynamic size + memory efficient = D [OK]

Hint: Unknown size? Use linked list stack for dynamic memory [OK]

Common Mistakes:

• Assuming arrays resize automatically without cost
• Ignoring pointer memory overhead in linked lists
• Confusing speed with memory efficiency