Is linked list better for stack?

What is Stack

A stack is a data structure similar to real-world stacks such as a pile of plates, books or a deck of cards. It is only possible to read a single element at a given time. It works according to the “First In Last Out” (FIFO) mechanism. In this mechanism, the first inserted element is the last element to remove from the stack. The last inserted element is the first element to remove from the stack. It is also called Last In First Out (LIFO).

Stack performs various operations. The push operation allows storing an element at the top of the stack while the pop operation helps to remove the topmost element from the stack. Furthermore, the peek operation helps to read the top element without eliminating it from the stack. If there are no elements, the stack is empty. Moroever, it is not possible to insert elements when the stack is full.

What is Linked List

Linked List is a data structure with a set of nodes arranged in a sequential manner.

There are three types of linked lists.

Single linked list – A node in this type of list stores the data and the address of the next node. It forms a structure similar to a chain. Inserting, deleting and traversing through the elements are some operations that can be performed on a single linked list.

Double linked list (Doubly linked list) – A node in this type of list stores data and two addresses. These are the address of the next node and the address of the previous node. The two references allow going forward and backwards through the elements in the list. Similar to a single linked list, the programmer can perform operations such as insertion, deletion and traverse on a double linked list.

Circular linked list – In these lists, the last node stores the address of the first node. Thus, it forms a circular chain structure.

Linked lists are dynamic. Therefore, it is not necessary to allocate memory initially. It is possible to allocate memory as required. On the other hand, it is not possible to access a specific element at once. One has to go through each node to one after the other to access a particular element.

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 .

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

Read Full Article

Linked List vs Array

Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tagsgiving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation.

Data storage scheme of an array

Data storage scheme of a linked list

Major differences are listed below:

• Size: Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to the risk of overwriting other data. However, in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size that can change at runtime.
• Memory allocation: For arrays at compile time and at runtime for linked lists. but, a dynamically allocated array also allocates memory at runtime.
• Memory efficiency: For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.
• Execution time: Any element in an array can be directly accessed with its index; however in the case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while some others (such as inserting/deleting an element in the data) are faster in linked lists.

Following are the points in favor of Linked Lists.
(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive because room has to be created for the new elements and to create room existing elements have to be shifted.

For example, suppose we maintain a sorted list of IDs in an array id[ ].

id[ ] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides the following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Linked lists have the following drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

4) It takes a lot of time in traversing and changing the pointers.

5) It will be confusing when we work with pointers.

References:
//cslibrary.stanford.edu/103/LinkedListBasics.pdf

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Arrays

Linked List

Practice Tags :

Linked List

Arrays

Read Full Article

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.

Stack Implementation Using Linked List

Lesson 12 of 54By Simplilearn

Last updated on Sep 15, 20213609

PreviousNext

• Tutorial Playlist

  Data Structure Tutorial

  Overview

  Arrays in Data Structures: A Guide With Examples

  Lesson - 1

  All You Need to Know About Two-Dimensional Arrays

  Lesson - 2

  All You Need to Know About a Linked List in a Data Structure

  Lesson - 3

  The Complete Guide to Implement a Singly Linked List

  Lesson - 4

  The Ultimate Guide to Implement a Doubly Linked List

  Lesson - 5

  The Fundamentals for Understanding Circular Linked List

  Lesson - 6

  The Ultimate Guide To Understand The Differences Between Stack And Queue

  Lesson - 7

  Implementing Stacks in Data Structures

  Lesson - 8

  Your One-Stop Solution for Stack Implementation Using Array

  Lesson - 9

  Your One-Stop Solution for Queue Implementation Using Array

  Lesson - 10

  Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

  Lesson - 11

  Your One-Stop Solution for Stack Implementation Using Linked-List

  Lesson - 12

  The Definitive Guide to Understand Stack vs Heap Memory Allocation

  Lesson - 13

  All You Need to Know About Linear Search Algorithm

  Lesson - 14

  All You Need to Know About Breadth-First Search Algorithm

  Lesson - 15

  A One-Stop Solution for Using Binary Search Trees in Data Structure

  Lesson - 16

  The Best Tutorial to Understand Trees in Data Structure

  Lesson - 17

  A Complete Guide to Implement Binary Tree in Data Structure

  Lesson - 18

  A Holistic Look at Using AVL Trees in Data Structures

  Lesson - 19

  All You Need to Know About Tree Traversal in Data Structure

  Lesson - 20

  The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

  Lesson - 21

  The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

  Lesson - 22

  The Best and Easiest Way to Understand an Algorithm

  Lesson - 23

  Your One-Stop Solution to Understand Shell Sort Algorithm

  Lesson - 24

  Your One-Stop Solution to Quick Sort Algorithm

  Lesson - 25

  The Most Useful Guide to Learn Selection Sort Algorithm

  Lesson - 26

  Everything You Need to Know About Radix Sort Algorithm

  Lesson - 27

  Everything You Need to Know About the Counting Sort Algorithm

  Lesson - 28

  Everything You Need to Know About the Merge Sort Algorithm

  Lesson - 29

  Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

  Lesson - 30

  Everything You Need to Know About the Bubble Sort Algorithm

  Lesson - 31

  The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

  Lesson - 32

  Your One-Stop Solution to Understand Recursive Algorithm in Programming

  Lesson - 33

  The Definitive Guide to Understanding Greedy Algorithm

  Lesson - 34

  Your One-Stop Solution to Understand Backtracking Algorithm

  Lesson - 35

  The Fundamentals of the Bellman-Ford Algorithm

  Lesson - 36

  Your One-Stop Solution for Graphs in Data Structures

  Lesson - 37

  The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

  Lesson - 38

  A Simplified and Complete Guide to Learn Space and Time Complexity

  Lesson - 39

  All You Need to Know About the Knapsack Problem : Your Complete Guide

  Lesson - 40

  The Fibonacci Series: Mathematical and Programming Interpretation

  Lesson - 41

  The Holistic Look at Longest Common Subsequence Problem

  Lesson - 42

  The Best Article to Understand What Is Dynamic Programming

  Lesson - 43

  A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

  Lesson - 44

  A Holistic Guide to Learn Stop Solution Using Dynamic Programming

  Lesson - 45

  One Stop Solution to All the Dynamic Programming Problems

  Lesson - 46

  Understanding the Fundamentals of Binomial Distribution

  Lesson - 47

  Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

  Lesson - 48

  Understanding the Difference Between Array and Linked List

  Lesson - 49

  The Best Article Out There to Understand the B+ Tree in Data Structure

  Lesson - 50

  A Comprehensive Look at Queue in Data Structure

  Lesson - 51

  Your One-Stop Solution to Understand Coin Change Problem

  Lesson - 52

  The Best Way to Understand the Matrix Chain Multiplication Problem

  Lesson - 53

  Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

  Lesson - 54

Table of Contents

View More

The problem with stack implementation using an array is working with only a fixed number of data elements, so we can also go for stack implementation using linked-list. Linked-list is the data structure that allocated memory dynamically, but in both cases, the time complexity is the same for all the operations like push, pop and peek.

Stack Implementation Using Linked-List

We already knew that linked lists allocate memory dynamically. Stack implementation using linked-list, the nodes are maintained in non-contiguous memory. Each node contains a pointer to the immediate next in line node in the Stack.

In Stack, implementation using Linked-List, every new element inserted to the top of the Stack which means every new inserting element pointed by the top and whenever we want to delete element from the Stack which is pointing to the top of the Stack by moving the top by moving top to is the previous node in the linked -list. The following field of the first element must always be NULL. There is an overflow condition in the Stack if the space left in the memory heap is not sufficient to create a node.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course

Video liên quan