Introduction to Data Structures

Advantages of DS

1. Data structure facilitates effective data storage in storage devices.

2. The use of data structures makes it easier to retrieve data from a storage
device.

3. The data structure allows for the effective and efficient processing of both
little and big amounts of data.

4. Manipulation of vast amounts of data is simple when a proper data

structure technique is used.

5. The use of a good data structure may assist a programmer to save a lot of
time or processing time while performing tasks such as data storage,
retrieval, or processing.

6. Most well-organized data structures, including stacks, arrays, graphs,

queues, trees, and linked lists, have well-built and pre-planned approaches
for operations such as storage, addition, retrieval, modification, and
deletion. The programmer may totally rely on these facts while utilising
them.

7. Data structures such as arrays, trees, linked lists, stacks, graphs, and so on
are thoroughly verified and proved, so anybody may use them directly
without the need for study and development. If you opt to design your own
data structure, you may need to do some study, but it will almost certainly
be to answer a problem that is more sophisticated than what these can
supply.
8. In the long term, data structure utilization might merely encourage
reusability.

Data structure can be divided into two categories:

 Primitive data structure and
 Non-primitive data structure

 Primitive Data Structure

Key features of a primitive data structure:
The size of a primitive data structure is known as it can store can only
one data type.

The primitive data structure will always store some data. It cannot
contain the NULL value.

Examples of the primitive data type are

integer, character, boolean, float, double, long, etc.
  Non - primitive Data Structure

The non-primitive data structure is further classified into two categories, i.e.,
linear and non-linear data structure.

A list in C / C++, python can store various data types inside it.

Two main types of non-primitive data structures are

 Linear data structures and

 Non-linear data structure

Linear data structures

 Array
 Stack
 Queue
 Linked list
Array

An array is a data structure that can hold the elements of same type. It cannot
contain the elements of different types like integer with character. The
commonly used operation in an array is insertion, deletion, traversing,
searching.

For example:

int a[6] = {1,2,3,4,5,6};

The above example is an array that contains the integer type elements stored
in a contiguous manner.

Stack

Stack is a data structure that follows the principle LIFO (Last In First Out). All
the operations on the stack are performed from the top of the stack such as
PUSH and POP operation. The push operation is the process of inserting
element into the stack while the pop operation is the process of removing
element from the stack. The stack data structure can be implemented by using
either array or linked list.

Queue

Queue is a data structure that can be implemented by using array. The

difference between the stack and queue data structure is that the elements in
the queue are inserted from the rear end while the elements in the queue are
removed from the front end.

So the Queue data structure is just the opposite of the stack since it uses the
FIFO principle. FIFO stands for first in first out. In a queue, the element stored
first in the structure would be retrieved first.
Linked List

The functionality of a list is similar to an array. It also stores elements in a

linear sequence. List, however, uses dynamic memory allocation to store its
elements at different memory locations. Though elements are stored at
different memory locations, all are arranged in a sequence and linked with
another.

In linked list, the last node of a data structure is to be linked to the first node of
the next data structure. The first element of any data structure is known as the
Head of the List. The linked list helps in memory allocation, stores data in
internal structure etc. There are three types of Linked Lists. They are:

1. Single Linked List

2. Double Linked List
3. Circular Linked List

Non-linear data structure

In a non-linear data structure, the storage of elements doesn't follow a

sequential order.

There are two types of non-linear data structure:

 Graph
 Tree

Graph

Graph: Used for network representation. A graph data structure basically

uses two components vertices and edges. In the graph, Edges are used to
connect vertices.
 Figure : An example of graph data structure

Tree

Tree: The tree data structure uses a hierarchical form of structure to represent
its elements. One of the famous tree data structures is the Binary tree. A
tree uses a node-like structure to make a hierarchical form, where each node
represents a value. The uppermost node of the tree is known as the root node
and the bottom node is known as a leaf node. Tree data structures are the
most complex, and efficient, data structures we use in programming. As such,
we use these to solve many real-time problems.
Figure : An example of tree data structure
Linear Data Structure (Dynamic)

 Stack
 Queue
 Linked List

Stack

There are many different stack operations which can be applied on a stack.

A stack is a data structure which is used to store data in a linear fashion. It is

an Abstract data type (ADT) in which data is inserted and deleted from a single
end which is the stack's top. It follows a Last in, First out (LIFO) principle i.e.
the data which is inserted most recently in the stack will be deleted first from
the stack. Given below is the pictorial representation of how a stack looks like.

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.

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.
Syntax:

Example:

Header file:

There are many different stack operations which can be applied on a stack.

A stack follows a Last in, First out principle (LIFO). This means the data
inserted in the stack last will be first to be removed. Also, the data is inserted or
deleted through the stack top.
Given below is the stack representation to show how data is inserted and deleted
in a stack.

Push is a function in stack definition which is used to insert data at the stack's
top.
// CSD, AMU - Stack Push Operation

#include<iostream>

#include<stack>

using namespace std;

int main() {

stack<int> s; // creating a stack of integers

[Link](1); // This pushes 1 to the stack top

[Link](2); // This pushes 2 to the stack top

[Link](3); // This pushes 3 to the stack top

[Link](4); // This pushes 4 to the stack top

[Link](5); // This pushes 5 to the stack top

// printing the stack

while(![Link]())

cout<<[Link]()<<" ";

[Link]();

}
Sample Output

Pop is a function in the stack definition which is used to remove data from the
stack's top.
Applications of Stacks
Queue

Suppose you want to order food in a fast-food chain restaurant. You see a queue
of people, and you join the queue where the last person of the queue is standing.
A person standing before you in the queue will also reach the counter before
you. So you can place your order only when you reach the front of the queue.

Queue works in similar fashion in C++.

As we know that a queue is a linear data structure in which insertion takes place
at the back, and deletion takes place from the front. It works on the principle of
First In First Out(FIFO).

Syntax of declaring a queue in C++

Header file required in declaring queue.

There are two basic operations in queue: enqueue and dequeue.

Enqueue: When we add an element to a queue, it is said to be an enqueue

operation. If the queue is full, we cannot add more elements to it. Such a
condition is called an overflow condition. We use the push function to perform
an enqueue operation in a queue. Time Complexity - O(1)

Syntax:
Dequeue: When we remove an element from a queue, it is said to be a dequeue
operation. If the queue is already empty, i.e., there are no elements in the queue,
we cannot remove elements from it. Such a condition is called an underflow
condition. We use the pop function to perform a dequeue operation in the
queue. Time Complexity - O(1)

Syntax:

Note: Since a queue works on the FIFO technique, the element which was
pushed in first will pop out first as well, i.e., the relative order of elements in a
dequeue operation is the same as the enqueue operation.
//CSD, AMU
// Sample program to show operations on QUEUE
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue < int > q;
// Enqueue operations
[Link](5);
[Link](23);
[Link](29);
// Dequeue operations
cout << "The elements in the queue are: ";
while (![Link]()) {
int first = [Link]();
[Link]();
cout << first << " ";
}
return 0;
}
Output

Functions in Queue

Function Description

empty() This function returns 0 if the queue is not empty and a

non-zero value if the queue is empty.

front() This function returns the value of the first element in the
queue. The first element is the one that was pushed into
the queue before all the elements were present in the
queue.

back() This function returns the value of the last element in the
queue. The last element is the one that was pushed into
the queue after all the elements present in the queue.
 push(a) This function inserts an element to the end of the queue.

pop() This function removes the first element from the queue,
i.e., the element returned by the front method.

size() This function returns the size of the queue.

swap() This function exchanges the contents of the two queues.

The two queue types should be of the same type.

emplace() This function constructs and inserts a new element at the

end of the queue.

Note: The push() creates a copy of the element and appends it to the end of
the queue while emplace() creates the new instance in-place at the end of the
queue. The end result of both the functions is completely same.
Applications of queue

Linked List

A linked list is a linear data structure that includes a series of connected

nodes. Here, each node stores the data and the address of the next node.

A linked list is a sequence of data structures, which are connected together

via links.

Linked List is a sequence of links which contains items. Each link contains a
connection to another link. Linked list is the second most-used data structure
after array.

A music player displays the property of a linked list. In a music player, each song is
linked with the next song.

Following are the important terms to understand the concept of Linked List.

 Link − Each link of a linked list can store a data called an element.
 Next − Each link of a linked list contains a link to the next link called
Next.
 LinkedList − A Linked List contains the connection link to the first link
called First.
 Linked list can be visualized as a chain of nodes, where every node
points to the next node.

As per the above illustration, following are the important points to be

considered.
 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.
 Last link carries a link as null to mark the end of the list.

Syntax of linked list contains data item & an address of another node such as:

Syntax:

Why use linked list over array?

Till now, we were using array data structure to organize the group of elements
that are to be stored individually in the memory. However, Array has several
advantages and disadvantages which must be known in order to decide the
data structure which will be used throughout the program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the

program.
2. Increasing size of the array is a time taking process. It is almost
impossible to expand the size of the array at run time.
3. All the elements in the array need to be contiguously stored in the
memory. Inserting any element in the array needs shifting of all its
predecessors.

Linked list is the data structure which can overcome all the limitations of an
array. Using linked list is useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-
contiguously stored in the memory and linked together with the help of
pointers.
2. Sizing is no longer a problem since we do not need to define its size at
the time of declaration. List grows as per the program's demand and
limited to the available memory space.
Applications of Linked List

Differentiate between Array and Linked List

Array Linked List

Static Dynamic
Contiguous Non - Contiguous
Direct Access No Direct Access
Homogenous Homogenous
Linear Linear
Physical Physical
Types of Linked List

Following are the various types of linked list.

 Simple Linked List − Item navigation is forward only.
 Doubly Linked List − Items can be navigated forward and backward.
 Circular Linked List − Last item contains link of the first element as
next and the first element has a link to the last element as previous.
Basic Operations
Following are the basic operations supported by a list.
 Is Empty
 Traversing
 Searching
 Insertion
 Deletion
 Merging