Posts

Difference between Array and Linked List

Image
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 . Let's understand how array is different from 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

Introduction to Linked Lists

Image
Introduction to Linked Lists 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

Implement Queue using Stacks

Image
Implement Queue using Stacks A Queue is defined by its property of  FIFO , which means First in First Out, i.e the element which is added first is taken out first. This behaviour defines a queue, whereas data is actually stored in an  array  or a  list  in the background. What we mean here is that no matter how and where the data is getting stored, if the first element added is the first element being removed and we have implementation of the functions  enqueue() and  dequeue()  to enable this behaviour, we can say that we have implemented a Queue data structure. In our previous tutorial, we used a simple  array  to store the data elements, but in this tutorial we will be using  Stack data structure  for storing the data. While implementing a queue data structure using stacks, we will have to consider the natural behaviour of stack too, which is  First in Last Out . For performing  enqueue  we require only  one stack  as we can directly  push  data onto the stack, but to pe

What is a Circular Queue?

Image
What is a Circular Queue? Before we start to learn about Circular queue, we should first understand, why we need a circular queue, when we already have  linear queue data structure . In a Linear queue, once the queue is completely full, it's not possible to insert more elements. Even if we dequeue the queue to remove some of the elements, until the queue is reset, no new elements can be inserted. You must be wondering why? When we  dequeue  any element to remove it from the queue, we are actually moving the  front  of the queue forward, thereby reducing the overall size of the queue. And we cannot insert new elements, because the  rear  pointer is still at the end of the queue. The only way is to reset the linear queue, for a fresh start. Circular Queue  is also a linear data structure, which follows the principle of  FIFO (First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last, hence making