Types of Data Structures
-
Data Structures can be broadly classified into two, based on how data elements are held together.
- Linear Data Structures
- Non-linear Data Structures
Linear Data Structures
Simply put, Linear Data Structures contains data elements arranged in a sequential order. For linear data structures, there can only be two immediate neighbors at max. These types of data structures are comparatively simpler and operations like search and traversal are usually faster.
Use linear data structures if the data is not to be represented in a hierarchical manner. Arrays, stack, queue and linked list are the most commonly used linear data structures.
Linear data structures can be further classified in to Static and Dynamic. Arrays are usually static in most programming languages and rest are dynamic.
Static means, at the time of declaration we specify the size and then not possible to extend the size during runtime. You might remember that in many programming languages like Java, C#, when we declare an array, we also initialize the size as well.
int a[]=new int[10];For Dynamic data structures size is allocated at run time and can be changed when needed.
Non-linear Data Structures
Non-linear Data Structures represents data elements in a non-sequential order. Use this, when we need to represent data in a hierarchical manner or to represent points on a two or three dimensional surface like a map.
Each node within a non-linear structure can be connected to any number of other nodes. As you can imagine, traversal and search operations can become a bit trickier and a bit slower.
Graphs and trees are non-linear data structures.
Let us further understand each type of data structures.
-
Array Data Structure
Arrays store a collection of data of similar types. Data can be of number, string or boolean formats. Arrays can be accessed using the index values, which are essentially number sequences that start with 0.
Arrays can also be multi-dimensional. That means a collections of arrays can be grouped together to form another array.
Eg: [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]We can modify array elements, perform other operations like copy, slicing, etc. Arrays are useful to easily represent mathematical structures like matrices, tables, etc. Arrays form the basis of other data structures like stacks, queues.
-
Stack Data Structure
Stack can be considered as a version of array that can be used to dynamically add or remove elements. Stack data structures are implemented based on LIFO principle. That means the elements are added in such a way that the first element entered to a stack can only be removed last.
Most programming languages provide methods like push() and pop() to add/remove items to a stack.
-
Queue Data Structure
Queues differ from stacks only in the order in which inserted elements comes off. Queues follow FIFO principle. First element entered to a queue comes out first on using the pop() method.
Queues and stacks are mostly useful when we write programs that needs to remember some values, to be used for next iterations. As an example, these can be used to implement an algorithm to search from a tree data structure. The adjacent nodes to visited node can be added to a queue to do the next set of search till the final node is reached.
-
Linked List Data Structure
Linked list is a slightly different kind of linear data structure compared to arrays, queues or stacks. This is like a chain of nodes, with each node having 2 parts. One part of the node to store the data and another part to store the reference to the next node memory location. So the nodes need not be placed in continuous memory location.
The advantage is that linked lists allows better insertion or removal of nodes from any point of the list by just replacing the address location of only 2 nodes. For an array, if an element gets inserted or removed, reorganizing the entire structure may be needed.
Disadvantage of linked list compared to array comes in search actions, as to find a node, it may be required to iterate through entire list as we are chaining each node using reference pointers.
-
Tree Data Structure
A Tree is a non-linear data structure mostly used to represent hierarchical data like a folder structure. A tree node can have zero of more child nodes, but there should be only one parent. So a closed path cannot be created in a tree.
Different types of tree structures are there like, binary tree, ordered tree, etc. For tree traversals, we have different algorithms like BFS and uses queues/stacks to record visited nodes.
-
Graph Data Structure
A Graph also contains nodes connected to other nodes. The most important difference of a Graph from Tree is that a graph node can have more than one parent. This means, a graph can have circular paths and can represent a more interconnected structure.
Graphs are better suited to represent diagrams and maps on a two dimensional or three dimensional surface. Graphs can handle much more complicated structures compared to a tree.
This also means that data structure operations can become a bit more challenging as well. Algorithms like BFS can still be used for graphs, but with more space and time complexities.
