Implement Stack using Linked List Editorial

Practice Problem Link: Implement Stack using Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement a stack using a Linked List as the underlying container.

The Stack class should support the following methods:

• int size()
• boolean isEmpty()
• int top()
• void push(int element)
• void pop()

Approach

We keep a LinkedList pointer to point to the top of the stack and keep its track. We also keep track of the size and capacity of the stack. During pop operation, we reduce the size of the stack by 1 and adjust the top point accordingly. Similarly, we increase the stack size by 1 and adjust the top pointer during the push operation. Similarly, using the Top pointer, we can simulate all other properties of the stack in O(1) time.

Analysis

• Time Complexity: O(1) for all the operations.
• Space Complexity: O(1) for all the operations.

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

// Implement the Stack class
class Stack {
public:
	
	ListNode *topTrack;
	int stackSize;
	int totalSize;
	Stack (int capacity) {
		topTrack = NULL;
		stackSize = 0;
		totalSize = capacity;
	}

	bool isEmpty() {
		return topTrack == NULL;
	}
	
	int size() {
		return stackSize;
	}
	
	int top() {
		 if (!isEmpty()) {
            return topTrack->data;
        }
        else {
            return -1;
		}
	}
	
	void push(int element) {
		ListNode *temp = new ListNode(element);       
        temp->data = element;
        temp->next = topTrack;
        topTrack = temp;
		stackSize++;
	}
	
	void pop() {
		 if (topTrack == NULL) {
            return;
        }
        topTrack = topTrack->next;
		stackSize--;
	}
};

Java

/* This is the ListNode class definition
class ListNode {
	int data;
	ListNode next;
	
	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
*/

// Implement the Stack class
class Stack {
	ListNode top;
	int size;
	int totalSize;
	public Stack (int capacity) {
		this.top = null;
		size = 0;
		totalSize = capacity;
	}

	public boolean isEmpty() {
		return top == null;
	}
	
	public int size() {
		return size;
	}
	
	public int top() {
		 if (!isEmpty()) {
            return top.data;
        }
        else {
            return -1;
		}
	}
	
	public void push(int element) {
		ListNode temp = new ListNode(0);       
        temp.data = element;
        temp.next = top;
        top = temp;
		size++;
	}
	
	public void pop() {
		 if (top == null) {
            return;
        }
        top = top.next;
		size--;
	}
}