Data structures are broadly classified into primitive and non-primitive data structures. The non-primitive data structure is further classified into linear and non-linear data structures.
Primitive Data Structures
Primitive data types or structures are predefined data types. They are supported by all programming languages.
Integer (int) – It is used to store the whole numbers. It allows both positive and negative numbers represented as signed and unsigned. The storage size of the int data type is 2 or 4 or 8 bytes.
Float ( float ) – Float data type allows a variable to store decimal values. The storage size of the float data type is 4 bytes.
Characters (char) – It is used to store the characters and these are stored as integers. Each char has equivalent ASCII values. The storage size of the character data type is 1 byte.
Double (double) – Double data type is also the same as float data type which allows up- to 10 digits after the decimal.
Pointer (*) – Pointer is a variable that holds the address of another variable or holds the address of an integer value. The storage size of the pointer is 4 or 8 bytes.
Non – Primitive Data Structures
Non-primitive data types are not predefined in programming languages. They can be implemented with the help of primitive data types. They are linear or non – linear in nature. Examples:
Linear DS: Arrays, Linked Lists.
Non-Linear DS: Trees and Graphs
Linear Data Structures
Linear data structure grows linearly. Different operations that can be performed are in a linear way.
Examples for Linear DS are,
Array is a data structure that has a collection of elements of the same data types. Each data item is stored in a contiguous memory location. An array index or key is used to identify each element. The following example represents an integer array. The index of the array starts with 0.
Linked list is a linear data structure. It does not use a contiguous memory location. The elements are linked using pointers. The first node is called the head. Each node has two parts – the data and the reference to the next node. The last node has a reference to null.
Stack is a linear data structure. In stack, elements are arranged in a sequential order. It follows Last In First Out (LIFO) or First In Last Out (FILO) mechanisms. Elements are inserted and removed according to the above mechanism. The elements are inserted and removed only at the top of the stack. Push operation adds an element and pop operation removes an element at the top of the stack.
There are many real-time examples: Arranging the plates in a tray, arranging the coins, and arranging the books on the shelves one over the other. Let’s take an example of arranging books on the shelves. We have to arrange 10 books on the shelves. Arranging the books one over the other. When all the books are arranged, we can see that the first book we placed is at the bottom and the last book we placed is at the top. So, when we need to remove the book at the bottom, first we have to remove the first book which is we placed last on the shelf. So, it follows the LIFO mechanism.
Queue is also a linear data structure similar to a stack in which the elements are arranged in a sequential manner. But, unlike stack it follows the First In First Out (FIFO) mechanism. In Queue, Insertion and deletion operations are performed in different positions. Enqueue operation is used to insert an element into the queue and dequeue operation is used to remove an element from the queue. The end in which the element is inserted is called REAR and the other end in which the element is deleted is called FRONT.
The real-time example for the queue is, Standing on a line for ticket reservations. The person who is standing first in the queue will get the ticket first (i.e. first come first serve)
Non – Linear Data Structures
Non – linear data structure does not grow linearly. They grow level wise.
Examples for Non – linear DS:
A tree is a non-linear data structure. Here, the elements are arranged in a hierarchical fashion without any closed relation. The elements are represented as nodes. The nodes which are interrelated to each other. Each node is connected by edges. Each tree that has a starting node is called the root node. There is only one root node for a tree.
In a computer, the files are stored in the folders in drives. Each folder has sub-folders and so on. This is a classical example of a Tree data structure.
A graph is also a non-linear data structure. It consists of nodes and edges. It is defined as a set of (V, E) pairs. Here, the nodes are represented as vertices and lines are represented as edges. The edges are used to connect the nodes or vertices.
For example, In google maps, usually it will show one or more routes from source to destination. An algorithm is used to calculate which route is the best route (less time to reach the destination). This representation is done using a graph data structure.
Also check, “What is data structure?”