Question

Describe different types of data structures in Computer Science with examples.

Answer 1

Data structures are the building blocks of any program or the software. Choosing the appropriate data structure for a program is the most difficult task for a programmer. Following terminology is used as far as data structures are concerned

Types of data structures

The given image shows the classification of data structures.

Linear Data Structure

Data is arranged in a linear fashion in which elements are linked one after the other. Data elements in a non-linear data structure are hierarchically related. All the data elements can be traversed in one go, but at a time only one element is directly reachable. All the data elements cannot be traversed in one go as the nodes are not visited sequentially. Linear data structure tends to waste the memory. Efficient utilization of memory. Linear data structures are easy to implement. Implementation of non-linear data structures is complex. Array, Queue, Stack, Linked List are linear data structures.

1.Array

An array is a data structure for storing more than one data item that has a similar data type. The items of an array are allocated at adjacent memory locations. These memory locations are called elements of that array.

The total number of elements in an

• Elements are stored at contiguous memory locations.
• An index is always less than the total number of array items.
• In terms of syntax, any variable that is declared as an array can store multiple values.
• Almost all languages have the same comprehension of arrays but have different ways of declaring and initializing them.
• However, three parts will always remain common in all the initializations, i.e., array name, elements, and the data type of elements.

The details of an array are accessed about its position. This reference is called index

Why do we need arrays?

Here, are some reasons for using arrays:

• Arrays are best for storing multiple values in a single variable
• Arrays are better at processing many values easily and quickly
• Sorting and searching the values is easier in arrays

Array examples

An array is a variable that can store multiple values. For example, if you want to store 100 integers, you can create an array for it.

int data[100]; 

How to declare an array?

dataType arrayName[arraySize];

For example,

float mark[5];

Here, we declared an array, mark, of floating-point type. And its size is 5. Meaning, it can hold 5 floating-point values.

It's important to note that the size and type of an array cannot be changed once it is declared.

Access Array Elements

You can access elements of an array by indices.

Suppose you declared an array mark as above. The first element is mark[0], the second element is mark[1] and so on.

2.Stack

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack, just like a pile of objects.

Basic features of Stack

1. Stack is an ordered list of similar data type.
2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

Applications of Stack

The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.

There are other uses also like:

1. Parsing
2. Expression Conversion(Infix to Postfix, Postfix to Prefix etc)

3.Queue

A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.

Queue follows the First In First Out(FIFO) rule - the item that goes in first is the item that comes out first too.

FIFO Representation of Queue

In the above image, since 1 was kept in the queue before 2, it was the first to be removed from the queue as well. It follows the FIFO rule.

In programming terms, putting an item in the queue is called an "enqueue" and removing an item from the queue is called "dequeue".

Basic Operations of Queue

A queue is an object or more specifically an abstract data structure(ADT) that allows the following operations:

• Enqueue: Add an element to the end of the queue
• Dequeue: Remove an element from the front of the queue
• IsEmpty: Check if the queue is empty
• IsFull: Check if the queue is full
• Peek: Get the value of the front of the queue without removing it

Working of Queue

Queue operations work as follows:

• two pointers FRONT and REAR
• FRONT track the first element of the queue
• REAR track the last elements of the queue
• initially, set value of FRONT and REAR to -1

Enqueue Operation

• check if the queue is full
• for the first element, set value of FRONT to 0
• increase the REAR index by 1
• add the new element in the position pointed to by REAR

Dequeue Operation

• check if the queue is empty
• return the value pointed by FRONT
• increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1

4.Linked Lists

A linked list is a linear data structure where each element is a separate object.
Linked list elements are not stored at contiguous location; the elements are linked using pointers.

Each node of a list is made up of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

NonLinear Data Structures

Non Linear Data Structures: The data structure where data items are not organized sequentially is called non linear data structure. In other words, A data elements of the non linear data structure could be connected to more than one elements to reflect a special relationship among them. All the data elements in non linear data structure can not be traversed in single run.

Examples of non linear data structures are Trees and Graphs.

A tree is collection of nodes where these nodes are arranged hierarchically and form a parent child relationships. A Graph is a collection of a finite number of vertices and an edges that connect these vertices. Edges represent relationships among vertices that stores data elements.

1.Tree

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Node

A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to child nodes.

The node having at least a child node is called an internal node.

Edge

It is the link between any two nodes.

Nodes and edges of a tree

Root

It is the topmost node of a tree.

Height of a Node

The height of a node is the number of edges from the node to the deepest leaf (ie. the longest path from the node to a leaf node).

2.Graph A graph can be defined as group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent child relationship. Definition A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following figure. Directed and Undirected Graph A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph is shown in the above figure since its edges are not attached with any of the directions. If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B. In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex A to another vertex B. Node A is called initial node while node B is called terminal node.