What are the advantages of linked list implementation of stacks & queues over array implementation?

Implement a stack using singly linked list

To implement a stack using singly linked list concept , all the singly linked list operations are performed based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list. Using singly linked lists , we implement stack by storing the information in the form of nodes and we need to follow the stack rules and implement using singly linked list nodes . So we need to follow a simple rule in the implementation of a stack which is last in first out and all the operations can be performed with the help of a top variable .Let us learn how to perform Pop , Push , Peek ,Display operations in the following article .

Table of Contents Show

• Implement a stack using singly linked list
• Advantages and Disadvantages of Linked List
• Advantages of Linked List
• Disadvantages of Linked List
• Video Tutorial
• You May Also Like:
• Advantages and Disadvantages of Linked List
• Advantages of Linked List
• Disadvantages of Linked List
• Application of Linked List
• Difference between linked list and array
• A quick brush up on the advantages and disadvantages of Linked Lists!

A stack can be easily implemented using the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. First node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.
The main advantage of using linked list over an arrays is that it is possible to implement a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.
Stack Operations:

1. push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.
2. pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
3. peek(): Return the top element.
4. display(): Print all elements in Stack.

Below is the implementation of the above approach:

C++

// C++ program to Implement a stack //using singly linked list #include <bits/stdc++.h> using namespace std; // Declare linked list node struct Node { int data; Node* link; }; Node* top; // Utility function to add an element // data in the stack insert at the beginning void push(int data) { // Create new node temp and allocate memory in heap Node* temp = new Node(); // Check if stack (heap) is full. // Then inserting an element would // lead to stack overflow if (!temp) { cout << "\nStack Overflow"; exit(1); } // Initialize data into temp data field temp->data = data; // Put top pointer reference into temp link temp->link = top; // Make temp as top of Stack top = temp; } // Utility function to check if // the stack is empty or not int isEmpty() { //If top is NULL it means that //there are no elements are in stack return top == NULL; } // Utility function to return top element in a stack int peek() { // If stack is not empty , return the top element if (!isEmpty()) return top->data; else exit(1); } // Utility function to pop top // element from the stack void pop() { Node* temp; // Check for stack underflow if (top == NULL) { cout << "\nStack Underflow" << endl; exit(1); } else { // Assign top to temp temp = top; // Assign second node to top top = top->link; //This will automatically destroy //the link between first node and second node // Release memory of top node //i.e delete the node free(temp); } } // Function to print all the // elements of the stack void display() { Node* temp; // Check for stack underflow if (top == NULL) { cout << "\nStack Underflow"; exit(1); } else { temp = top; while (temp != NULL) { // Print node data cout << temp->data << "-> "; // Assign temp link to temp temp = temp->link; } } } // Driver Code int main() { // Push the elements of stack push(11); push(22); push(33); push(44); // Display stack elements display(); // Print top element of stack cout << "\nTop element is " << peek() << endl; // Delete top elements of stack pop(); pop(); // Display stack elements display(); // Print top element of stack cout << "\nTop element is " << peek() << endl; return 0; }

Java

// Java program to Implement a stack // using singly linked list // import package import static java.lang.System.exit; // Create Stack Using Linked list class StackUsingLinkedlist { // A linked list node private class Node { int data; // integer data Node link; // reference variable Node type } // create global top reference variable global Node top; // Constructor StackUsingLinkedlist() { this.top = null; } // Utility function to add an element x in the stack public void push(int x) // insert at the beginning { // create new node temp and allocate memory Node temp = new Node(); // check if stack (heap) is full. Then inserting an // element would lead to stack overflow if (temp == null) { System.out.print("\nHeap Overflow"); return; } // initialize data into temp data field temp.data = x; // put top reference into temp link temp.link = top; // update top reference top = temp; } // Utility function to check if the stack is empty or not public boolean isEmpty() { return top == null; } // Utility function to return top element in a stack public int peek() { // check for empty stack if (!isEmpty()) { return top.data; } else { System.out.println("Stack is empty"); return -1; } } // Utility function to pop top element from the stack public void pop() // remove at the beginning { // check for stack underflow if (top == null) { System.out.print("\nStack Underflow"); return; } // update the top pointer to point to the next node top = (top).link; } public void display() { // check for stack underflow if (top == null) { System.out.printf("\nStack Underflow"); exit(1); } else { Node temp = top; while (temp != null) { // print node data System.out.printf("%d->", temp.data); // assign temp link to temp temp = temp.link; } } } } // main class public class GFG { public static void main(String[] args) { // create Object of Implementing class StackUsingLinkedlist obj = new StackUsingLinkedlist(); // insert Stack value obj.push(11); obj.push(22); obj.push(33); obj.push(44); // print Stack elements obj.display(); // print Top element of Stack System.out.printf("\nTop element is %d\n", obj.peek()); // Delete top element of Stack obj.pop(); obj.pop(); // print Stack elements obj.display(); // print Top element of Stack System.out.printf("\nTop element is %d\n", obj.peek()); } }

Python3

'''Python supports automatic garbage collection so deallocation of memory is done implicitly. However to force it to deallocate each node after use, add the following code: import gc #added at the start of program gc.collect() #to be added wherever memory is to be deallocated ''' class Node: # Class to create nodes of linked list # constructor initializes node automatically def __init__(self,data): self.data = data self.next = None class Stack: # head is default NULL def __init__(self): self.head = None # Checks if stack is empty def isempty(self): if self.head == None: return True else: return False # Method to add data to the stack # adds to the start of the stack def push(self,data): if self.head == None: self.head=Node(data) else: newnode = Node(data) newnode.next = self.head self.head = newnode # Remove element that is the current head (start of the stack) def pop(self): if self.isempty(): return None else: # Removes the head node and makes #the preceding one the new head poppednode = self.head self.head = self.head.next poppednode.next = None return poppednode.data # Returns the head node data def peek(self): if self.isempty(): return None else: return self.head.data # Prints out the stack def display(self): iternode = self.head if self.isempty(): print("Stack Underflow") else: while(iternode != None): print(iternode.data,"->",end = " ") iternode = iternode.next return # Driver code MyStack = Stack() MyStack.push(11) MyStack.push(22) MyStack.push(33) MyStack.push(44) # Display stack elements MyStack.display() # Print top element of stack print("\nTop element is ",MyStack.peek()) # Delete top elements of stack MyStack.pop() MyStack.pop() # Display stack elements MyStack.display() # Print top element of stack print("\nTop element is ", MyStack.peek()) # This code is contributed by Mathew George

C#

// C# program to Implement a stack // using singly linked list // import package using System; // Create Stack Using Linked list public class StackUsingLinkedlist { // A linked list node private class Node { // integer data public int data; // reference variable Node type public Node link; } // create global top reference variable Node top; // Constructor public StackUsingLinkedlist() { this.top = null; } // Utility function to add // an element x in the stack // insert at the beginning public void push(int x) { // create new node temp and allocate memory Node temp = new Node(); // check if stack (heap) is full. // Then inserting an element // would lead to stack overflow if (temp == null) { Console.Write("\nHeap Overflow"); return; } // initialize data into temp data field temp.data = x; // put top reference into temp link temp.link = top; // update top reference top = temp; } // Utility function to check if // the stack is empty or not public bool isEmpty() { return top == null; } // Utility function to return // top element in a stack public int peek() { // check for empty stack if (!isEmpty()) { return top.data; } else { Console.WriteLine("Stack is empty"); return -1; } } // Utility function to pop top element from the stack public void pop() // remove at the beginning { // check for stack underflow if (top == null) { Console.Write("\nStack Underflow"); return; } // update the top pointer to // point to the next node top = (top).link; } public void display() { // check for stack underflow if (top == null) { Console.Write("\nStack Underflow"); return; } else { Node temp = top; while (temp != null) { // print node data Console.Write("{0}->", temp.data); // assign temp link to temp temp = temp.link; } } } } // Driver code public class GFG { public static void Main(String[] args) { // create Object of Implementing class StackUsingLinkedlist obj = new StackUsingLinkedlist(); // insert Stack value obj.push(11); obj.push(22); obj.push(33); obj.push(44); // print Stack elements obj.display(); // print Top element of Stack Console.Write("\nTop element is {0}\n", obj.peek()); // Delete top element of Stack obj.pop(); obj.pop(); // print Stack elements obj.display(); // print Top element of Stack Console.Write("\nTop element is {0}\n", obj.peek()); } } // This code is contributed by 29AjayKumar

Javascript

<script> // Javascript program to Implement a stack // using singly linked list // import package // A linked list node class Node { constructor() { this.data=0; this.link=null; } } // Create Stack Using Linked list class StackUsingLinkedlist { constructor() { this.top=null; } // Utility function to add an element x in the stack push(x) { // create new node temp and allocate memory let temp = new Node(); // check if stack (heap) is full. Then inserting an // element would lead to stack overflow if (temp == null) { document.write("<br>Heap Overflow"); return; } // initialize data into temp data field temp.data = x; // put top reference into temp link temp.link = this.top; // update top reference this.top = temp; } // Utility function to check if the stack is empty or not isEmpty() { return this.top == null; } // Utility function to return top element in a stack peek() { // check for empty stack if (!this.isEmpty()) { return this.top.data; } else { document.write("Stack is empty<br>"); return -1; } } // Utility function to pop top element from the stack pop() // remove at the beginning { // check for stack underflow if (this.top == null) { document.write("<br>Stack Underflow"); return; } // update the top pointer to point to the next node this.top = this.top.link; } display() { // check for stack underflow if (this.top == null) { document.write("<br>Stack Underflow"); } else { let temp = this.top; while (temp != null) { // print node data document.write(temp.data+"->"); // assign temp link to temp temp = temp.link; } } } } // main class // create Object of Implementing class let obj = new StackUsingLinkedlist(); // insert Stack value obj.push(11); obj.push(22); obj.push(33); obj.push(44); // print Stack elements obj.display(); // print Top element of Stack document.write("<br>Top element is ", obj.peek()+"<br>"); // Delete top element of Stack obj.pop(); obj.pop(); // print Stack elements obj.display(); // print Top element of Stack document.write("<br>Top element is ", obj.peek()+"<br>"); // This code is contributed by rag2127 </script>

Output:

44->33->22->11-> Top element is 44 22->11-> Top element is 22

Time Complexity:

The time complexity for all push(), pop(), and peek() operations is O(1) as we are not performing any kind of traversal over the list. We perform all the operations through the current pointer only.

Article Tags :

Linked List

Stack

Technical Scripter

Technical Scripter 2018

Practice Tags :

Linked List

Stack

Advantages and Disadvantages of Linked List

Advantages of Linked List

Dynamic Data Structure

Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memeory. So there is no need to give initial size of linked list.

Insertion and Deletion

Insertion and deletion of nodes are really easier. Unlike array here we don’t have to shift elements after insertion or deletion of an element. In linked list we just have to update the address present in next pointer of a node.

No Memory Wastage

As size of linked list can increase or decrease at run time so there is no memory wastage. In case of array there is lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements are wasted. There is no such problem in linked list as memory is allocated only when required.

Implementation

Data structures such as stack and queues can be easily implemented using linked list.

Disadvantages of Linked List

Memory Usage

More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.

Traversal

Elements or nodes traversal is difficult in linked list. We can not randomly access any element as we do in array by index. For example if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large.

Reverse Traversing

In linked list reverse traversing is really difficult. In case of doubly linked list its easier but extra memory is required for back pointer hence wastage of memory.

Video Tutorial

If you know some other advantages and disadvantages of linked list then please mention by commenting below.

Advantages and Disadvantages of Linked List

Advantages of Linked List

1. The linked list is a dynamic data structure.
2. You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at run-time itself.
3. In this, you can easily do insertion and deletion functions. That is, you can easily insert and delete the node.
4. Memory is well utilized in the linked list. Because in it, we do not have to allocate memory in advance.
5. Its access time is very fast, and it can be accessed at a certain time without memory overhead.
6. You can easily implement linear data structures using the linked list like a stack, queue.

Disadvantages of Linked List

1. The linked list requires more memory to store the elements than an array, because each node of the linked list points a pointer, due to which it requires more memory.
2. It is very difficult to traverse the nodes in a linked list. In this, we cannot access randomly to any one node. (As we do in the array by index.) For example: - If we want to traverse a node in an n position, then we have to traverse all the nodes that come before n, which will spoil a lot of our time.
3. Reverse traversing in a linked list is very difficult, because it requires more memory for the pointer.

Application of Linked List

The linked list is a primitive data structure, which is used in various types of applications.

1. It is used to maintain directory names.
2. The linked list can perform arithmetic operations in the long integer.
3. Polynomials can be manipulated by storing constant in the node of the linked list.
4. We can also use it to next and previous images in the image viewer.
5. With the help of the linked list, we can move songs back and forth in the music player.
6. The linked list is also used for undo in word and Photoshop applications.
7. All the running applications in the computer are stored in the circular linked list, and the operating system provides them with a fixed time slot.
8. It can also be used to implement hash tables.

Difference between linked list and array

Both array and linked list are used to store the same type of linear data, but array is allocated contiguous memory location in the compile-time while the linked list is allocated memory in run-time.

A quick brush up on the advantages and disadvantages of Linked Lists!