Types of Data Structures
Data structures are an integral part of computers used for the arrangement of data in memory. They are essential and responsible for organizing, processing, accessing, and storing data efficiently.
An array is a linear data structure and it is a collection of items stored at contiguous memory locations.
The idea is to store multiple items of the same type together in one place.
It allows the processing of a large amount of data in a relatively short period.
The first element of the array is indexed by a subscript of 0.
There are different operations possible in an array, like Searching, Sorting, Inserting, Traversing, Reversing, and Deleting.
Characteristics of an Array
An array has various characteristics which are as follows:
Arrays use an index-based data structure which helps to identify each of the elements in an array easily using the index.
If a user wants to store multiple values of the same data type, then the array can be utilized efficiently.
An array can also handle complex data structures by storing data in a two-dimensional array.
An array is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
The search process in an array can be done very easily.
A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
Types of linked list
Doubly linked list
Circular linked list
Doubly circular linked list
Characteristics of a Linked list
A linked list has various characteristics which are as follows:
A linked list uses extra memory to store links.
During initialization of linked list, there is no need to know the size of the elements.
Linked lists are used to implement stacks, queues, graphs, etc.
The first node of the linked list is called the Head.
The next pointer of the last node always points to NULL.
In linked list, insertion and deletion is possible easily.
Each node of the linked list consists of a pointer/link which is the address of the next node.
Linked list can shrink or grow at any point in time easily.
Stack is a linear data structure that follows a particular order in which the operations are performed.
The order is LIFO(Last in first out).
Entering and retrieving data is possible from only one end.
The entering and retrieving of data is also called push and pop operation in a stack.
There are different operations possible in a stack like reversing a stack using recursion, Sorting, Deleting the middle element of a stack, etc.
Characteristics of a Stack
Stack has various different characteristics which are as follows:
Stack is used in many different algorithms like Tower of Hanoi, tree traversal, recursion etc.
Stack is implemented through array or linked list.
It follows Last In First Out operation i.e., element which is inserted first will pop in last and vice versa.
The insertion and deletion happens at one end i.e. from the top of the stack.
In stack, if allocated space for stack is full, and still anyone attempts to add more elements, it will lead to stack overflow.
Queue is a linear data structure that follows a particular order in which the operations are performed.
The order is First In First Out(FIFO) i.e. the data item stored first will be accessed first.
In this, entering and retrieving data is not done from only one end.
An example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
Different operations are performed on Queue like Reversing a Queue (with or without using recursion), Reversing the first K elements of a Queue, etc.
Few basic operations performed In Queue are enqueue, dequeue, front, rear, etc.
Characteristics of a Queue
Queue has various different characteristics which are as follows:
Queue is a FIFO (First In First Out) structure.
To remove the last element of Queue, all the elements inserted before the new element in the queue must be removed.
A queue is an ordered list of elements of similar data types.
A tree is a non-linear and hierarchal data structure where the elements are arranged in a tree-like structure.
In a tree, the topmost node is called the root node. Each node contains some data, and data can be of any type.
It consists of a central node, structural nodes, and sub-nodes which are connected via edges.
Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.
A tree has various terminologies like Node, Root, Edge, Height of a tree, Degree of a tree, etc.
Types of Trees
Binary Search Tree
Characteristics of a Tree
Tree has various different characteristics which are as follows:
A tree is also known as a Recursive data structure.
In a tree, Height of the root can be defined as the longest path from the root node to the leaf node.
In a tree, one can also calculate the depth from the top to any node. The root node has depth of 0.
A graph is a non-linear data structure that consists of vertices (or nodes) and edges.
It consists of a finite set of vertices and set of edges that connect a pair of nodes.
Graph is used to solve the most challenging and complex programming problems.
It has different terminologies which are Path, Degree, Adjacent vertices, Connected components, etc.
Characteristics of Graph
Graph has various different characteristics which are as follows:
The maximum distance from a vertex to all the other vertices is considered as the Eccentricity of that vertex.
The vertex having minimum Eccentricity is considered the central point of the graph.
The minimum value of Eccentricity from all vertices is considered as the radius of a connected graph.