Stack, queue, linked list (construction, understanding, usage)
Last updated
Last updated
Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack, just like a pile of objects.
Basic features of Stack
Stack is an ordered list of similar data type.
Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.
Applications of Stack
The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack. There are other uses also like:
Parsing
Expression Conversion(Infix to Postfix, Postfix to Prefix etc)
Implementation of Stack Data Structure
Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.
Algorithm for PUSH operation
Check if the stack is full or not.
If the stack is full, then print error of overflow and exit the program.
If the stack is not full, then increment the top and add the element.
Algorithm for POP operation
Check if the stack is empty or not.
If the stack is empty, then print error of underflow and exit the program.
If the stack is not empty, then print the element at the top and decrement the top.
Analysis of Stack Operations
Below mentioned are the time complexities for various operations that can be performed on the Stack data structure.
Push Operation : O(1)
Pop Operation : O(1)
Top Operation : O(1)
Search Operation : O(n)
The time complexities for push() and pop() functions are O(1) because we always have to insert or remove the data from the top of the stack, which is a one step process.
Queue is an abstract data type or a linear data structure, just like stack data structure, in which the first element is inserted from one end called the REAR(also called tail), and the removal of existing element takes place from the other end called as FRONT(also called head).
This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will be removed first.
Which is exactly how queue system works in real world. If you go to a ticket counter to buy movie tickets, and are first in the queue, then you will be the first one to get the tickets. Right? Same is the case with Queue data structure. Data inserted first, will leave the queue first.
The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.
Basic features of Queue
Like stack, queue is also an ordered list of elements of similar data types.
Queue is a FIFO( First in First Out ) structure.
Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
peek() function is oftenly used to return the value of first element without dequeuing it.
Applications of Queue
Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios:
Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.
Implementation of Queue Data Structure
Queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array.
Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.
When we remove an element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one shift all the other elements in forward position.
In approach [B] we remove the element from head position and then move head to the next position.
In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element.
In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.
Algorithm for ENQUEUE operation
Check if the queue is full or not.
If the queue is full, then print overflow error and exit the program.
If the queue is not full, then increment the tail and add the element.
Algorithm for DEQUEUE operation
Check if the queue is empty or not.
If the queue is empty, then print underflow error and exit the program.
If the queue is not empty, then print the element at the head and increment the head.
Complexity Analysis of Queue Operations
Just like Stack, in case of a Queue too, we know exactly, on which position new element will be added and from where an element will be removed, hence both these operations requires a single step.
Enqueue: O(1)
Dequeue: O(1)
Size: O(1)
LinkedList
Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence. Each node holds its own data and the address of the next node hence forming a chain like structure.
Linked Lists are used to create trees and graphs.
Advantages of Linked Lists
They are a dynamic in nature which allocates the memory when required.
Insertion and deletion operations can be easily implemented.
Stacks and queues can be easily executed.
Linked List reduces the access time.
Disadvantages of Linked Lists
The memory is wasted as pointers require extra memory for storage.
No element can be accessed randomly; it has to access each node sequentially.
Reverse Traversing is difficult in linked list.
Applications of Linked Lists
Linked lists are used to implement stacks, queues, graphs, etc.
Linked lists let you insert elements at the beginning and end of the list.
In Linked Lists we don't need to know the size in advance.
There are 3 different implementations of Linked List available, they are:
Singly Linked List
Doubly Linked List
Circular Linked List
#Singly Linked List
Singly linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in the sequence of nodes.
The operations we can perform on singly linked lists are insertion, deletion and traversal.
#Doubly Linked List
In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.
#Circular Linked List
In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
#Difference between Array and Linked List
Both Linked List and Array are used to store linear data of similar type, but an array consumes contiguous memory locations allocated at compile time, i.e. at the time of declaration of array, while for a linked list, memory is assigned as and when data is added to it, which means at runtime.
This is the basic and the most important difference between a linked list and an array. In the section below, we will discuss this in details along with highlighting other differences.
*Linked List vs. Array Array is a datatype which is widely implemented as a default type, in almost all the modern programming languages, and is used to store data of similar type.
But there are many usecases, like the one where we don't know the quantity of data to be stored, for which advanced data structures are required, and one such data structure is linked list.
ARRAY
LINKED LIST
Array is a collection of elements of similar data type.
Linked List is an ordered collection of elements of same type, which are connected to each other using pointers.
Array supports Random Access, which means elements can be accessed directly using their index, like arr[0] for 1st element, arr[6] for 7th element etc. Hence, accessing elements in an array is fast with a constant time complexity of O(1).
Linked List supports Sequential Access, which means to access any element/node in a linked list, we have to sequentially traverse the complete linked list, upto that element. To access nth element of a linked list, time complexity is O(n).
In an array, elements are stored in contiguous memory location or consecutive manner in the memory.
In a linked list, new elements can be stored anywhere in the memory. Address of the memory location allocated to the new element is stored in the previous node of linked list, hence formaing a link between the two nodes/elements.
In array, Insertion and Deletion operation takes more time, as the memory locations are consecutive and fixed.
In case of linked list, a new element is stored at the first free and available memory location, with only a single overhead step of storing the address of memory location in the previous node of linked list. Insertion and Deletion operations are fast in linked list.
Memory is allocated as soon as the array is declared, at compile time. It's also known as Static Memory Allocation.
Memory is allocated at runtime, as and when a new node is added. It's also known as Dynamic Memory Allocation.
In array, each element is independent and can be accessed using it's index value.
In case of a linked list, each node/element points to the next, previous, or maybe both nodes.
Array can single dimensional, two dimensional or multidimensional
Linked list can be Linear(Singly), Doubly or Circular linked list.
Size of the array must be specified at time of array decalaration.
Size of a Linked list is variable. It grows at runtime, as more nodes are added to it.
Array gets memory allocated in the Stack section.
Whereas, linked list gets memory allocated in Heap section.
Below we have a pictorial representation showing how consecutive memory locations are allocated for array, while in case of linked list random memory locations are assigned to nodes, but each node is connected to its next node using pointer.
Why we need pointers in Linked List? In case of array, memory is allocated in contiguous manner, hence array elements get stored in consecutive memory locations. So when you have to access any array element, all we have to do is use the array index, for example arr[4] will directly access the 5th memory location, returning the data stored there.
But in case of linked list, data elements are allocated memory at runtime, hence the memory location can be anywhere. Therefore to be able to access every node of the linked list, address of every node is stored in the previous node, hence forming a link between every node.
We need this additional pointer because without it, the data stored at random memory locations will be lost. We need to store somewhere all the memory locations where elements are getting stored.
Yes, this requires an additional memory space with each node, which means an additional space of O(n) for every n node linked list.
