In this article, I am going to walk you through the concepts of the common Data Structures that every student, colleague working with computers should be aware of. Data Structure forms an integral part of any system or database design. It is a very interesting and intuitive concept that you can apply anywhere. Through this article, I aim to introduce the beginners to the concepts of Data Structures and brush up the same for colleagues who have already been associated with the industry for years. This will also help you understand some database concepts more easily once you have a grasp over these concepts.
In this article, I am going to cover the most important and frequently used Data Structures in day-to-day life of a software developer. Please note other data structures might not be covered in this article and I will explain those in some other article.
- Arrays
- Linked Lists
- Stacks
- Queues
Let us now begin understanding these, one by one.
Arrays
An array is a collection of elements that are stored at adjacent memory locations. These are structures that can hold data for the same data type and are fixed in length. Be it an array of integers, strings, or even an array of array. These arrays have indexes which means they can be accessed randomly by providing the index of the position. Each of the elements in the array is stored in the memory with a specific address that can be used to retrieve the element back. The last element in an array is always NULL.
Figure 1 – Data Structures – Arrays
Considering an analogy, you may think of a multi-story building as an array. In that building, all the floors have the same floor plan (same data type) and your friend might reside on the second floor (index = 2).
Figure 2 – Array Analogy by using a building (Source)
Basically, we can perform the following operations on an array.
- Traverse – Navigate through the elements in the array and display each of them
- Search – We can also search for a specific element by providing the index of the element
- Update – Values at certain specified indexes can also be updated
A limitation of an array is that we cannot insert or remove elements from the array dynamically. This is because the arrays are mostly fixed in size. If you need to add an element to the array, then you might need to create a new array with length greater than that of the current one and then copy the elements from one array to the other. Same goes for deletion as well, you need to create a new array with reduced size.
Arrays are mostly used to build or develop other complex data structures such as heaps, hash tables, array lists, etc.
Linked Lists
Linked Lists are sequential data structures which are connected to one another in a linear fashion. For this reason, you cannot access a linked list randomly, but only sequential access is possible. There are three types of linked lists. All the elements in a linked list are known as nodes. Each node comprises of a key and a pointer to the next node. The Head and Tail are the starting and ending nodes of the linked list, respectively.
Figure 3 – Data Structures – Linked Lists
- Singly Linked Lists – In these, we can only navigate only forward
- Doubly Linked Lists – Here, we can traverse both forward and reverse. This is done by an additional pointer known as the previous
- Circular Linked Lists – In this case, the next pointer of the tail is connected to the head and the previous pointer of the head is connected to the tail of the list
The following operations can be performed on a linked list.
- Search – You can find the first element with a key k and return the pointer to this element
- Insert – You can insert elements either at the beginning of the list, in the end, or in the middle of the linked list
- Delete – Similarly, you can remove elements from either beginning of the list, from the middle, or the end of the list
An important application of a circular linked list can be seen in Windows while switching between multiple programs using the Alt + Tab keys.
Stacks
Stacks are also very commonly used data structures used in most of the major applications around the world. It follows the common acronym LIFO, which means Last In First Out. You can resemble it to something like a stack of plates, so, the one which is kept at the last is taken at the first.
Figure 4 – Stack of plates (Source)
There are two prime operations that you can perform on a stack – Push and Pop.
- Push – Add an element to the top of the stack
- Pop – Remove an element from the top of the stack and return it
Apart from these two, you can also use the following operations on a stack.
- Peek – It is used to return the top element of the stack without removing or deleting it
- isFull – Used to check if the stack is full
- isEmpty – Used to check if the stack is empty
The most common applications of stacks are used in implementing function calls in recursive programming. This also gives rise to a very common and frequent error, known as the stack overflow error.
Queues
A queue is another data structure that follows FIFO or First In First Out. You can resemble this with a real-life queue and hence the name. It is also a dynamic data structure which means you can only add elements to the end of the queue and remove only from the beginning. Unlike a stack, a queue is open at both ends, and thus it allows the addition of elements at the end of the queue while removal of the items can be done from the beginning of the queue.
Figure 5 – Example of a real-life queue
The following operations can be performed in a queue.
Figure 6 – Data Structures – Queue in programming (Source)
- Enqueue – Used to add an item to the end of the queue. If the queue is already full, then it will throw an Overflow condition
- Dequeue – Used to remove an item from the beginning of the queue. If the queue is empty, then it will throw an Underflow condition
- Front – Used to return the item at the front of the queue
- Rear – Used to return the item at the end of the queue
Queues are mostly used while designing multi-threaded applications such that the first thread gets executed first and the last executes at the last. Also, another application would be using priority queues while designing microservice architecture systems. Amazon SQS and Azure Service Bus are examples of a cloud-based message queue system which implements the concept of queues to send and receive messages.
Conclusion
In this article, we have seen how important it is to understand the concepts of the common Data Structures. These concepts will help you when you start designing a new system from scratch or while trying to understand some of the existing data systems. I remember during my days back in college, it was one of the most important topics that we had to learn thoroughly. Yet today, these are one of the most frequently asked questions in any software development interview. I would strongly recommend everyone to have a good understanding of these concepts before appearing for any technical discussion.
He is a prolific author, with over 100 articles published on various technical blogs, including his own blog, and a frequent contributor to different technical forums.
In his leisure time, he enjoys amateur photography mostly street imagery and still life. Some glimpses of his work can be found on Instagram. You can also find him on LinkedIn
View all posts by Aveek Das
- Getting started with PostgreSQL on Docker - August 12, 2022
- Getting started with Spatial Data in PostgreSQL - January 13, 2022
- An overview of Power BI Incremental Refresh - December 6, 2021