Few Data Structures That Every Developer Should Master
A computer program or an application is a collection of instructions to perform a specific task. For this, it may require to store, retrieve, and manipulate data. Thus a data structure is a named location that can be used to store and organize data. Below are a few data structure that you should master as a programmer,
An array is one of the most useful and popular data structures. An array is a collection of items stored at contiguous memory locations. Basically it can store various data of the same type at a single memory location. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array. When we talk about an array, the following are two important terms that you should know,
- Element − Each item stored in an array is called an element.
- Index − Each location of an element in an array has a numerical index, which is used to identify the element.
The stack data structure is also known as an abstract data type i.e ADT in most of the languages works similar to the real world stacks such as a deck of cards or a pile of books, etc. Think about the operations that you could do like,
- Put a new book on the top (Push)
- Remove a book from the top (Pop)
If you want the book at the bottom, you have to first remove all the books on top. Such an arrangement is called Last In First Out - the last item that was placed is the first item to go out. Similarly, Stack allows all data operations at one end only. At any given time, we can only access the top element of a stack.
In pro grammatical terms, putting a book is called a push operation, and removing a book is called a pop operation. Above is the representation of how Stack works.
The queue is a data structure that is similar to Stack and is also an Abstract Data Type i.e ADT. Unlike Stack, Queue allows operations from both its ends. As the name suggests, it’s just like a normal Queue in which you may stand at a shop. The first person in the Queue will always be the first one to come out of Queue. This is how the Queue works. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows the First In First Out rule - the item that goes in first is the item that comes out first too. The most basic operations that can be performed are,
- Enqueue - adding an element to the queue
- Dequeue - removing an element from the queue.
Above is the representation of a Queue data structure.
A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links that contains items. Each link contains a connection to another link. The linked list is the second most-used data structure after array. Think of the running race where you run in partners, you have a rod, that you pass to another partner and so on, that has linked list works, the first element has the information that passes us to the next element and so on.
It is a series of connected "nodes" that contains the "address" of the next node. Each node can store a data point which may be a number, a string, or any other type of data. Below are some points to remember,
- Linked List contains a link element called first.
- Each link carries a data field(s) and a link field called next.
- Each link is linked with its next link using its next link.
- The last link carries a link as null to mark the end of the list.
A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges. Of which, Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operations are as fast as in the linked list.
When we talk about trees, below are some important terminologies one should know,
- Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
- Parent − Any node except the root node has one edge upward to a node called the parent.
- Path − Path refers to the sequence of nodes along the edges of a tree.
- Child − The node below a given node connected by its edge downward is called its child node.
- Leaf − The node which does not have any child node is called the leaf node.
- Subtree − Subtree represents the descendants of a node.
- Height - The height of a Tree is the height of the root node or the depth of the deepest node.
- Depth - The depth of a node is the number of edges from the root to the node.
What are your thoughts on DSA? Learn Data Structures using Python the right way using - Programming Hero. A fun way of learning.