Data Structures Tutorial
Data Structure is a way to store and organize data so that it
can be used efficiently. The data structure name indicates itself that
organizing the data in memory. There are many ways of organizing the data in
the memory as we have already seen one of the data structures, i.e., array in C
language. Array is a collection of memory elements in which data is stored
sequentially, i.e., one after another. In other words, we can say that array
stores the elements in a continuous manner. This organization of data is done
with the help of an array of data structures. There are also other ways to organize
the data in memory.
A data structure is a way of organizing the
data so that it can be used efficiently. The word efficiently, which in terms of
both the space and time. For example, a stack is an ADT (Abstract data type)
which uses either arrays or linked list data structure for the implementation.
Therefore, we conclude that we require some data structure to implement a
particular ADT.
An ADT tells what is to be
done and data structure tells how it is to be done. In other
words, we can say that ADT gives us the blueprint while data structure provides
the implementation part. As the different data structures can be implemented in
a particular ADT, but the different implementations are compared for time and
space. For example, the Stack ADT can be implemented by both Arrays and linked
list. Suppose the array is providing time efficiency while the linked list is
providing space efficiency.
Types of Data
Structures
There are two types of data structures:
- Primitive
data structure
- Non-primitive
data structure
Primitive Data structure
The primitive data structures are primitive data types. The int,
char, float, double, and pointer are the primitive data structures that can
hold a single value.
Non-Primitive Data structure
The non-primitive data structure is divided into two types:
- Linear
data structure
- Non-linear
data structure
Linear Data Structure
The arrangement of data in a sequential manner is known as a
linear data structure. The data structures used for this purpose are Arrays,
Linked list, Stacks, and Queues. In these data structures, one element is
connected to only one another element in a linear form.
Non-Linear Data Structure
When one element is connected to the 'n' number of elements
known as a non-linear data structure. The best example is trees and graphs. In
this case, the elements are arranged in a random manner.
Data structures can also be classified as:
- Static
data structure: It is a type of data
structure where the size is allocated at the compile time. Therefore, the
maximum size is fixed.
- Dynamic
data structure: It is a type of data
structure where the size is allocated at the run time. Therefore, the maximum
size is flexible.
Major Operations
The major or the common operations that can be performed on the
data structures are:
- Searching: We can search for any element in a data
structure.
- Sorting: We can sort the elements of a data structure
either in an ascending or descending order.
- Insertion: We can also insert the new element in a data
structure.
- Updation: We can also update the element, i.e., we can
replace the element with another element.
- Deletion: We can also perform the delete operation to remove
the element from the data structure.
Advantages of Data
structures
The following are the advantages of a data structure:
- Efficiency: If the choice of a data structure for
implementing a particular ADT is proper, it makes the program very
efficient in terms of time and space.
- Reusability: The data structure provides reusability means
that multiple client programs can use the data structure.
- Abstraction: The data structure specified by an ADT also
provides the level of abstraction. The client cannot see the internal
working of the data structure, so it does not have to worry about the
implementation part. The client can only see the interface.
Data
Structure can be defined as the group of data elements which provides an
efficient way of storing and organising data in the computer so that it can be
used efficiently. Some examples of Data Structures are arrays, Linked List,
Stack, Queue, etc. Data Structures are widely used in almost every aspect of
Computer Science i.e., Operating System, Compiler Design, Artifical
intelligence, Graphics and many more. Data Structures are the main part of many
computer science algorithms as they enable the programmers to handle the data
in an efficient way. It plays a vital role in enhancing the performance of a
software or a program as the main function of the software is to store and
retrieve the user's data as fast as possible.
Basic Terminology
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.
o Data: An elementary value or the collection of values, for
example, student's name and its id are the data about the student.
o Group Items: Data items which have subordinate data items are called
Group item, for example, name of a student can have first name and the last
name.
Record: The collection of
various data items, for example, if we talk about the student entity, then its
name, address, course and marks can be grouped together to form the record for
the student.
File: A File is a
collection of various records of one type of entity, for example, if there are
60 employees in the class, then there will be 20 records in the related file
where each record contains the data about each employee.
Attribute and Entity: An entity
represents the class of certain objects. it contains various attributes. Each
attribute represents the particular property of that entity.
Field: Field is a single
elementary unit of information representing the attribute of an entity.
Data Structure Classification
Linear
Data Structures: A data structure is called linear if all of its elements
are arranged in the linear order. In linear data structures, the elements are
stored in non-hierarchical way where each element has the successors and
predecessors except the first and last element. Types of Linear Data Structures
are given below:
Arrays: An array is a
collection of similar type of data items and each data item is called an
element of the array. The data type of the element may be any valid data type
like char, int, float or double. The elements of array share the same variable
name but each one carries a different index number known as subscript. The
array can be one dimensional, two dimensional or multidimensional.
The individual elements of the array age are:
age [0], age [1], age [2], age [3], ......... age [98], age [99].
Linked List: Linked list is a
linear data structure which is used to maintain a list in the memory. It can be
seen as the collection of nodes stored at non-contiguous memory locations. Each
node of the list contains a pointer to its adjacent node.
Stack: Stack is a linear
list in which insertion and deletions are allowed only at one end, called top. A stack is an
abstract data type (ADT), can be implemented in most of the programming
languages. It is named as stack because it behaves like a real-world stack, for
example: - piles of plates or deck of cards etc.
Queue: Queue is a linear
list in which elements can be inserted only at one end called rear and deleted
only at the other end called front.
It is an abstract data structure, similar to stack. Queue is opened at both end
therefore it follows First-In-First-Out (FIFO) methodology for storing the data
items.
Non-Linear
Data Structures: This data structure does not form a sequence i.e. each
item or element is connected with two or more other items in a non-linear
arrangement. The data elements are not arranged in sequential structure. Types
of Non-Linear Data Structures are given below:
Trees: Trees are
multilevel data structures with a hierarchical relationship among its elements
known as nodes. The bottom most nodes in the herierchy are called leaf node while
the topmost node is called root
node. Each node contains pointers to point adjacent nodes. Tree
data structure is based on the parent-child relationship among the nodes. Each
node in the tree can have more than one children except the leaf nodes whereas
each node can have atmost one parent except the root node. Trees can be
classfied into many categories.
Graphs: Graphs can be
defined as the pictorial representation of the set of elements (represented by
vertices) connected by the links known as edges. A graph is different from tree
in the sense that a graph can have cycle while the tree cannot have the one.
Pointer
Pointer is used to points the address of the value stored
anywhere in the computer memory. To obtain the value stored at the location is
known as dereferencing the pointer. Pointer improves the performance for
repetitive process such as:
- Traversing
String
- Lookup
Tables
- Control
Tables
- Tree
Structures
Pointer
Details
- Pointer arithmetic: There are
four arithmetic operators that can be used in pointers: ++, --, +, -
- Array of pointers: You can
define arrays to hold a number of pointers.
- Pointer to pointer: C allows
you to have pointer on a pointer and so on.
- Passing pointers to functions in C: Passing
an argument by reference or by address enable the passed argument to be
changed in the calling function by the called function.
- Return pointer from functions in C: C allows
a function to return a pointer to the local variable, static variable and
dynamically allocated memory as well.
Structure
A structure is a composite data type that defines a grouped list
of variables that are to be placed under one name in a block of memory. It
allows different variables to be accessed by using a single pointer to the
structure.
Syntax
1.
struct structure_name
- {
3.
data_type member1;
- data_type member2;
5.
.
- .
7.
data_type memeber;
- };
Advantages
- It can hold variables of different data
types.
- We can create objects containing
different types of attributes.
- It allows us to re-use the data layout
across programs.
- It is used to implement other data
structures like linked lists, stacks, queues, trees, graphs etc.
Array in Data Structure
Arrays are defined as the
collection of similar types of data items stored at contiguous memory
locations. It is one of the simplest data structures where each data element
can be randomly accessed by using its index number.
In C programming, they are the derived data types that can store
the primitive type of data such as int, char, double, float, etc. For example,
if we want to store the marks of a student in 6 subjects, then we don't need to
define a different variable for the marks in different subjects. Instead, we
can define an array that can store the marks in each subject at the contiguous
memory locations.
Properties of array
There are some of the properties of an array that are listed as
follows -
Each
element in an array is of the same data type and carries the same size that is
4 bytes. Elements in the array are stored at contiguous memory locations from
which the first element is stored at the smallest memory location. Elements of
the array can be randomly accessed since we can calculate the address of each
element of the array with the given base address and the size of the data
element.
Representation of an array
We can represent an array in various ways in different programming
languages. As an illustration, let's see the declaration of array in C language
-
As per the above illustration, there are some of the following
important points -
- Index
starts with 0.
- The
array's length is 10, which means we can store 10 elements.
- Each
element in the array can be accessed via its index.
Why are arrays required?
Arrays are useful because -
- Sorting
and searching a value in an array are easier.
- Arrays
are best to process multiple values quickly and easily.
- Arrays are good for storing multiple values in a
single variable - In
computer programming, most cases require storing a large number of data of
a similar type. To store such an amount of data, we need to define a large
number of variables. It would be very difficult to remember the names of
all the variables while writing the programs. Instead of naming all the
variables with a different name, it is better to define an array and store
all the elements into it.
Memory allocation of an array
All the data elements of an array are stored at contiguous
locations in the main memory. The name of the array represents the base address
or the address of the first element in the main memory. Each element of the
array is represented by proper indexing.
We can define the indexing of an array in the below ways -
- 0 (zero-based indexing): The first
element of the array will be arr[0].
- 1 (one-based indexing): The first
element of the array will be arr[1].
- n (n - based indexing): The first
element of the array can reside at any random index number.
How to access an element from the array?
We required the information given below to access any random
element from the array -
- Base Address of the array.
- Size of an element in bytes.
- Type of indexing, array follows.
Basic
operations
Now, let's discuss the basic operations supported in the array -
- Traversal - This operation is used to
print the elements of the array.
- Insertion - It is used to add an
element at a particular index.
- Deletion - It is used to delete an
element from a particular index.
- Search - It is used to search an
element using the given index or by the value.
- Update - It updates an element at a
particular index.
Complexity
of Array operations
Time and space complexity of various array operations are
described in the following table.
Time Complexity
Operation |
Average Case |
Worst Case |
Access |
O(1) |
O(1) |
Search |
O(n) |
O(n) |
Insertion |
O(n) |
O(n) |
Deletion |
O(n) |
O(n) |
Space Complexity
In array, space complexity for worst case is O(n).
Advantages
of Array
- Array provides the single name for the
group of variables of the same type. Therefore, it is easy to remember the
name of all the elements of an array.
- Traversing an array is a very simple
process; we just need to increment the base address of the array in order
to visit each element one by one.
- Any element in the array can be
directly accessed by using the index.
Disadvantages
of Array
- Array is homogenous. It means that the
elements with similar data type can be stored in it.
- In array, there is static memory
allocation that is size of an array cannot be altered.
- There will be wastage of memory if we
store less number of elements than the declared size.
2D Array
2D array can be defined as an array of arrays. The 2D array is
organized as matrices which can be represented as the collection of rows and
columns. However, 2D arrays are created to implement a relational database look
alike data structure. It provides ease of holding bulk of data at once which
can be passed to any number of functions wherever required.
The syntax of declaring two-dimensional array is very much
similar to that of a one-dimensional array, given as follows.
1.
int arr[max_rows ][max_columns];
however, It produces the data structure which looks like
following.
Linked List:
Linked list is a linear data structure which is used to maintain a list
in the memory. It can be seen as the collection of nodes stored at
non-contiguous memory locations. Each node of the list contains a pointer to
its adjacent node. A linked list is a linear data structure, in which the
elements are not stored at contiguous memory locations. The elements in a
linked list are linked using pointers as shown in the below image:
In simple words, a linked list consists of nodes where
each node contains a data field and a reference(link) to the next node in the
list. Linked list is a
linear data structure that includes a series of connected nodes. Linked list
can be defined as the nodes that are randomly stored in the memory. A node in
the linked list contains two parts, i.e., first is the data part and second is
the address part. The last node of the list contains a pointer to the null.
After array, linked list is the second most used data structure. In a linked
list, every link contains a connection to another link.
Representation of a
Linked list
Linked list can be represented as the connection of nodes in
which each node points to the next node of the list. The representation of the
linked list is shown below -
Why use linked list over array?
- The size of the array must be known in
advance before using it in the program.
- Increasing the size of the array is a
time taking process. It is almost impossible to expand the size of the
array at run time.
- All the elements in the array need to
be contiguously stored in the memory. Inserting an element in the array
needs shifting of all its predecessors.
Linked list is useful because -
- It allocates the memory dynamically.
All the nodes of the linked list are non-contiguously stored in the memory
and linked together with the help of pointers.
- In linked list, size 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.
How to declare a
linked list?
Linked list contains two parts, and both are of different types,
i.e., one is the simple variable, while another is the pointer variable. We can
declare the linked list by using the user-defined data type structure.
The declaration of linked list is given as follows -
- struct node
- {
- int data;
- struct node *next;
- }
In the above declaration, we have defined a structure named
as node that contains two variables, one is data that
is of integer type, and another one is next that is a pointer
which contains the address of next node.
Types of Linked list
Linked list is classified into the following types -
Singly Linked list
The collection of an ordered set of elements. It is the commonly used linked list in programs. If we are
talking about the linked list, it means it is a singly linked list. The singly
linked list is a data structure that contains two parts, i.e., one is the data
part, and the other one is the address part, which contains the address of the
next or the successor node. The address part in a node is also known as a pointer.
Suppose we have three nodes, and the addresses of these three
nodes are 100, 200 and 300 respectively. The representation of three nodes as a
linked list is shown in the below figure:
In above figure three different nodes having address 100, 200
and 300 respectively. The first node contains the address of the next node,
i.e., 200, the second node contains the address of the last node, i.e., 300,
and the third node contains the NULL value in its address part as it does not
point to any node. The pointer that holds the address of the initial node is
known as a head pointer.
Doubly linked list
Doubly linked list is a complex type of linked list in
which a node contains a pointer to the previous as well as the next node in the
sequence. Therefore, in a doubly-linked list, a node consists of three parts:
node data, pointer to the next node in sequence (next pointer), and pointer to
the previous node (previous pointer). The doubly
linked list contains two pointers. We can define the doubly linked list as a
linear data structure with three parts: the data part and the other two address
part. In other words, a doubly linked list is a list that has three parts in a
single node, includes one data part, a pointer to its previous node, and a
pointer to the next node.
Suppose we have three nodes, and the address of these nodes are
100, 200 and 300, respectively. The representation of these nodes in a
doubly-linked list is shown below:
In the above figure, the node in a doubly-linked list has two
address parts; one part stores the address of the next while the other
part of the node stores the previous node's address. The initial node in the doubly linked
list has the NULL value in the address part, which provides the address of
the previous node.
Representation of the node in a doubly linked list
1.
struct node
- {
3.
int data;
- struct node *next;
5.
struct node *prev;
- }
We have defined a user-defined structure named a node with three members,
one is data of integer type, and the other two are the pointers,
i.e., next and prev of the node type. The next pointer variable holds
the address of the next node, and the prev pointer holds the address
of the previous node. The type of both the pointers, i.e., next and prev is struct node as both the
pointers are storing the address of the node of the struct node type.
Circular linked list
A circular linked list is a variation of a singly linked list. The only
difference between the singly linked list and a circular linked list is that the last node does not point to any node in a singly
linked list, so its link part contains a NULL value. On the other hand, the
circular linked list is a list in which the last node connects to the first
node, so the link part of the last node holds the first node's address. The
circular linked list has no starting and ending node. We can traverse in any
direction, i.e., either backward or forward. The diagrammatic representation of
the circular linked list is shown below:
1.
struct node
- {
3.
int data;
- struct node *next;
5.
}
A circular linked list is a sequence of elements in which each
node has a link to the next node, and the last node is having a link to the
first node. The representation of the circular linked list will be similar to
the singly linked list, as shown below:
Doubly Circular linked list
Circular doubly linked list is a more complex
type of data structure in which a node contains pointers to its previous node
as well as the next node. Circular doubly linked list doesn't contain NULL in
any of the nodes. The last node of the list contains the address of the first
node of the list. The first node of the list also contains the address of the
last node in its previous pointer. The doubly circular linked list has the features of both
the circular
linked list and doubly linked list.
The above figure shows the representation of the doubly circular
linked list in which the last node is attached to the first node and thus
creates a circle. It is a doubly linked list also because each node holds the
address of the previous node also. The main difference between the doubly
linked list and doubly circular linked list is that the doubly circular linked
list does not contain the NULL value in the previous field of the node. As the
doubly circular linked contains three parts, i.e., two address parts and one
data part so its representation is similar to the doubly linked list.
1.
struct node
- {
3.
int data;
- struct node *next;
5.
struct node *prev;
}
Advantages of Linked
list
The advantages of using the Linked list are given as follows -
- Dynamic
data structure - The size of the linked
list may vary according to the requirements. Linked list does not have a
fixed size.
- Insertion
and deletion - Unlike arrays, insertion,
and deletion in linked list is easier. Array elements are stored in the
consecutive location, whereas the elements in the linked list are stored
at a random location. To insert or delete an element in an array, we have
to shift the elements for creating the space. Whereas, in linked list,
instead of shifting, we just have to update the address of the pointer of
the node.
- Memory
efficient - The size of a linked list
can grow or shrink according to the requirements, so memory consumption in
linked list is efficient.
- Implementation
- We can implement both
stacks and queues using linked list.
Disadvantages of
Linked list
The limitations of using the Linked list are given as follows -
- Memory
usage - In linked list, node
occupies more memory than array. Each node of the linked list occupies two
types of variables, i.e., one is a simple variable, and another one is the
pointer variable.
- Traversal
- Traversal is not easy in
the linked list. If we have to access an element in the linked list, we
cannot access it randomly, while in case of array we can randomly access
it by index. For example, if we want to access the 3rd node, then we need
to traverse all the nodes before it. So, the time required to access a
particular node is large.
- Reverse
traversing - Backtracking or reverse
traversing is difficult in a linked list. In a doubly-linked list, it is
easier but requires more memory to store the back pointer.
Operations performed
on Linked list
The basic operations that are supported by a list are mentioned
as follows -
- Insertion
- This operation is
performed to add an element into the list.
- Deletion
- It is performed to delete
an operation from the list.
- Display
- It is performed to display
the elements of the list.
- Search
- It is performed to search
an element from the list using the given key.
Complexity of Linked list: Now, let's see the time and space complexity of the linked list
for the operations search, insert, and delete.
1. Time Complexity
Operations |
Average case time complexity |
Worst-case time complexity |
Insertion |
O(1) |
O(1) |
Deletion |
O(1) |
O(1) |
Search |
O(n) |
O(n) |
Where 'n' is the number of nodes in the given tree.
2. Space Complexity
Operations |
Space complexity |
Insertion |
O(n) |
Deletion |
O(n) |
Search |
O(n) |
The space complexity of linked list is O(n)
Stack
A Stack is a linear data structure that
follows the LIFO
(Last-In-First-Out) principle. Stack has one end,
whereas the Queue has two ends (front
and rear). It contains only one pointer top pointer pointing
to the topmost element of the stack. Whenever an element is added in the stack,
it is added on the top of the stack, and the element can be deleted only from
the stack. In other words, a stack can be defined as a container in which
insertion and deletion can be done from the one end known as the top of the stack.
It is called as stack because it behaves like a real-world stack, piles
of books, etc. A Stack is an abstract data type with a pre-defined capacity,
which means that it can store the elements of a limited size. It is a data
structure that follows some order to insert and delete the elements, and that
order can be LIFO or FILO.
Working of Stack : Stack works on the LIFO pattern. As we can observe in the below figure
there are five memory blocks in the stack; therefore, the size of the stack is
5. Suppose we want to store the elements in a stack and let's assume that stack
is empty. We have taken the stack of size 5 as shown below in which we are
pushing the elements one by one until the stack becomes full.
Since our stack is full as the size of the
stack is 5. In the above cases, we can observe that it goes from the top to the
bottom when we were entering the new element in the stack. The stack gets
filled up from the bottom to the top. When we perform the delete operation on
the stack, there is only one way for entry and exit as the other end is closed.
It follows the LIFO pattern, which means that the value entered first will be
removed last. In the above case, the value 5 is entered first, so it will be
removed only after the deletion of all the other elements.
Standard Stack Operations
The following are some common operations
implemented on the stack:
- Push (): When we
insert an element in a stack then the operation is known as a push. If the
stack is full then the overflow condition occurs.
- Pop(): When we
delete an element from the stack, the operation is known as a pop. If the
stack is empty means that no element exists in the stack, this state is
known as an underflow state.
- Is Empty (): It
determines whether the stack is empty or not.
- Is Full (): It
determines whether the stack is full or not.'
- peek (): It
returns the element at the given position.
- count (): It
returns the total number of elements available in a stack.
- change (): It
changes the element at the given position.
- display (): It prints
all the elements available in the stack.
PUSH operation
The steps involved in the PUSH operation
is given below:
- Before inserting an element in a stack,
we check whether the stack is full.
- If we try to insert the element in a
stack, and the stack is full, then the overflow condition occurs.
- When we initialize a stack, we set the
value of top as -1 to check that the stack is empty.
- When the new element is pushed in a
stack, first, the value of the top gets incremented, i.e., top=top+1, and
the element will be placed at the new position of the top.
- The elements will be inserted until we
reach the max size
of the stack.
POP operation
The steps involved in the POP operation is
given below:
- Before deleting the element from the stack,
we check whether the stack is empty.
- If
we try to delete the element from the empty stack, then the underflow condition
occurs.
- If the stack is not empty, we first
access the element which is pointed by the top
- Once
the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Array implementation of Stack
In array implementation, the stack is formed by using the array.
All the operations regarding the stack are performed using arrays. Let’s see
how each operation can be implemented on the stack using array data structure.
Adding an element onto the stack (push operation)
Adding an element into the top of the stack is referred to as
push operation. Push operation involves following two steps.
- Increment
the variable Top so that it can now refere to the next memory location.
- Add
element at the position of incremented top. This is referred to as adding
new element at the top of the stack.
Stack is overflown when we try to insert an element into a
completely filled stack therefore, our main function must always avoid stack
overflow condition.
Algorithm:36History of Java
1.
begin
- if top = n then stack full
3.
top = top + 1
- stack (top) : = item;
5.
end
Time Complexity: o (1)
Deletion of an element from a stack (Pop operation)
Deletion of an element from the top of the stack is called pop
operation. The value of the variable top will be incremented by 1 whenever an
item is deleted from the stack. The top most element of the stack is stored in
another variable and then the top is decremented by 1. the operation returns
the deleted value that was stored in another variable as the result. The
underflow condition occurs when we try to delete an element from an already
empty stack.
Algorithm:
1.
begin
- if top = 0 then stack empty;
3.
item:= stack(top);
- top = top - 1;
5.
end;
Time Complexity: o(1)
Linked list implementation of stack
Instead of using array, we can also use linked list to implement
stack. Linked list allocates the memory dynamically. However, time complexity
in both the scenario is same for all the operations i.e. push, pop and peek. In
linked list implementation of stack, the nodes are maintained non-contiguously
in the memory. Each node contains a pointer to its immediate successor node in
the stack. Stack is said to be overflown if the space left in the memory heap
is not enough to create a node.
The top most node in the stack always contains null in its address field. Let’s
discuss the way in which, each operation is performed in linked list
implementation of stack.
Adding
a node to the stack (Push operation)
Adding a node to the stack is referred to as push operation.
Pushing an element to a stack in linked list implementation is different from
that of an array implementation. In order to push an element onto the stack,
the following steps are involved.
- Create
a node first and allocate memory to it.
- If
the list is empty then the item is to be pushed as the start node of the
list. This includes assigning value to the data part of the node and
assign null to the address part of the node.
- If
there are some nodes in the list already, then we have to add the new
element in the beginning of the list (to not violate the property of the
stack). For this purpose, assign the address of the starting element to
the address field of the new node and make the new node, the starting node
of the list.
Time Complexity: o(1)
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is
referred to as pop operation.
Deleting a node from the linked list implementation of stack is different from
that in the array implementation. In order to pop an element from the stack, we
need to follow the following steps:
- Check for the
underflow condition: The underflow condition occurs
when we try to pop from an already empty stack. The stack will be empty
if the head pointer of the list points to null.
- Adjust the
head pointer accordingly: In stack, the elements are
popped only from one end, therefore, the value stored in the head pointer
must be deleted and the node must be freed. The next node of the head
node now becomes the head node.
Time Complexity: o(n)
Display the nodes (Traversing)
Displaying all the
nodes of a stack needs traversing all the nodes of the linked list organized in
the form of stack. For this purpose, we need to follow the following steps.
- Copy the head pointer into a temporary
pointer.
- Move the temporary pointer through all
the nodes of the list and print the value field attached to every node.
Time Complexity: o(n)
Queue
A queue can be defined as an ordered list which enables insert
operations to be performed at one end called REAR and delete
operations to be performed at another end called FRONT. Queue is
referred to be as First in First Out list. For example, people waiting in line
for a rail ticket form a queue.
Queue is the data structure that is similar to the queue in the
real world. A queue is a data structure in which whatever comes first will go
out first, and it follows the FIFO (First-In-First-Out) policy. Queue can also
be defined as the list or collection in which the insertion is done from one
end known as the rear
end or the tail of
the queue, whereas the deletion is done from another end known as the front end or
the head of
the queue.
The real-world example of a queue is the ticket queue outside a
cinema hall, where the person who enters first in the queue gets the ticket
first, and the last person enters in the queue gets the ticket at last. Similar
approach is followed in the queue in data structure.
The representation of the queue is shown in the below image -
Applications of Queue
Due to the fact that queue performs actions
on first in first out basis which is quite fair for the ordering of actions.
There are various applications of queues.
- Queues are widely used as waiting lists for a single
shared resource like printer, disk, CPU.
- Queues are used in asynchronous transfer of data (where
data is not being transferred at the same rate between two processes) for e.g.
pipes, file IO, sockets.
- Queues are used as buffers in most of the applications
like MP3 media player, CD player, etc.
- Queue are used to maintain the play list in media
players in order to add and remove the songs from the play-list.
- Queues are used in operating systems for handling
interrupts.
Complexity
Data Structure |
Time Complexity |
Space Complexity |
|||||||
Average |
Worst |
Worst |
|||||||
Access |
Search |
Insertion |
Deletion |
Access |
Search |
Insertion |
Deletion |
||
Queue |
θ(n) |
θ(n) |
θ(1) |
θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Types of Queue
There are four different types of queue that are listed as
follows –
- Simple Queue or Linear Queue
- Circular Queue
- Priority Queue
- Double Ended Queue (or Deque)
Simple Queue or Linear Queue
In Linear Queue, an insertion takes place from one end while the
deletion occurs from another end. The end at which the insertion takes place is
known as the rear end, and the end at which the deletion takes place is known
as front end. It strictly follows the FIFO rule.
The major drawback of using a linear Queue is that insertion is
done only from the rear end. If the first three elements are deleted from the
Queue, we cannot insert more elements even though the space is available in a
Linear Queue. In this case, the linear Queue shows the overflow condition as
the rear is pointing to the last element of the Queue.
Circular Queue
In Circular Queue, all the nodes are represented as circular. It
is similar to the linear Queue except that the last element of the queue is
connected to the first element. It is also known as Ring Buffer, as all the
ends are connected to another end. The representation of circular queue is
shown in the below image -
The drawback that occurs in a linear queue is overcome by using
the circular queue. If the empty space is available in a circular queue, the
new element can be added in an empty space by simply incrementing the value of
rear. The main advantage of using the circular queue is better memory
utilization.
Priority Queue
It is a special type of queue in which the elements are arranged
based on the priority. It is a special type of queue data structure in which
every element has a priority associated with it. Suppose some elements occur
with the same priority, they will be arranged according to the FIFO principle.
The representation of priority queue is shown in the below image -
Insertion in priority queue takes place based on the arrival,
while deletion in the priority queue occurs based on the priority. Priority
queue is mainly used to implement the CPU scheduling algorithms.
There are two types of priority queue that are discussed as
follows -
- Ascending priority queue - In ascending
priority queue, elements can be inserted in arbitrary order, but only
smallest can be deleted first. Suppose an array with elements 7, 5, and 3
in the same order, so, insertion can be done with the same sequence, but
the order of deleting the elements is 3, 5, 7.
- Descending priority queue - In
descending priority queue, elements can be inserted in arbitrary order,
but only the largest element can be deleted first. Suppose an array with
elements 7, 3, and 5 in the same order, so, insertion can be done with the
same sequence, but the order of deleting the elements is 7, 5, 3.
Deque
(or, Double Ended Queue)
In Deque or Double Ended Queue, insertion and
deletion can be done from both ends of the queue either from the front or rear.
It means that we can insert and delete elements from both front and rear ends
of the queue. Deque can be used as a palindrome checker means that if we read
the string from both ends, then the string would be the same.
Deque can be used both as stack and queue as
it allows the insertion and deletion operations on both ends. Deque can be
considered as stack because stack follows the LIFO (Last In First Out)
principle in which insertion and deletion both can be performed only from one
end. And in deque, it is possible to perform both insertion and deletion from
one end, and Deque does not follow the FIFO principle.
The representation of the deque is shown in
the below image -
Input
restricted deque - As the name implies,
in input restricted queue, insertion operation can be performed at only one
end, while deletion can be performed from both ends.
v Output restricted deque - As the name implies, in output
restricted queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.
Operations
performed on queue
The fundamental operations that can be performed on queue are
listed as follows -
- Enqueue: The
Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
- Dequeue: It
performs the deletion from the front-end of the queue. It also returns the
element which has been removed from the front-end. It returns an integer
value.
- Peek: This is
the third operation that returns the element, which is pointed by the
front pointer in the queue but does not delete it.
- Queue overflow (is full): It shows
the overflow condition when the queue is completely full.
- Queue underflow (is empty): It shows the
underflow condition when the Queue is empty, i.e., no elements are in the
Queue.
Ways
to implement the queue
There are two ways of implementing the Queue:
- Implementation using array: The sequential
allocation in a Queue can be implemented using an array.
- Implementation
using Linked list: The linked list allocation in a Queue can be implemented
using a linked list.
Tree Data Structure
A tree is also one of the data structures that represent
hierarchical data. Suppose we want to show the employees and their positions in
the hierarchical form then it can be represented as shown below:
The above tree shows the organization hierarchy of
some company. In the above structure, john is the CEO of
the company, and John has two direct reports named as Steve and Rohan.
Steve has three direct reports named Lee, Bob, Ella where Steve is
a manager. Bob has two direct reports named Sal and Emma. Emma has
two direct reports named Tom and Raj.
Tom has one direct report named Bill. This particular
logical structure is known as a Tree. Its structure is
similar to the real tree, so it is named a Tree. In this
structure, the root is at the top, and its branches are
moving in a downward direction. Therefore, we can say that the Tree data
structure is an efficient way of storing the data in a hierarchical way.
Let's understand some key points of the Tree
data structure.
- A
tree data structure is defined as a collection of objects or entities
known as nodes that are linked together to represent or simulate
hierarchy.
- A
tree data structure is a non-linear data structure because it does not
store in a sequential manner. It is a hierarchical structure as elements
in a Tree are arranged in multiple levels.
- In
the Tree data structure, the topmost node is known as a root node. Each
node contains some data, and data can be of any type. In the above tree
structure, the node contains the name of the employee, so the type of data
would be a string.
- Each
node contains some data and the link or reference of other nodes that can
be called children.
Some basic terms used in Tree data structure.
Let's consider the tree structure, which is shown below:
In the above structure, each node is labeled with some number.
Each arrow shown in the above figure is known as a link between
the two nodes.
- Root: The root node is the topmost node in the tree
hierarchy. In other words, the root node is the one that doesn't have any
parent. In the above structure, node numbered 1 is the root node
of the tree. If a node is directly linked to some other node, it
would be called a parent-child relationship.
- Child
node: If the node is a
descendant of any node, then the node is known as a child node.
- Parent: If the node contains any sub-node, then that node
is said to be the parent of that sub-node.
- Sibling: The nodes that have the same parent are known as
siblings.
- Leaf
Node:- The node of the tree,
which doesn't have any child node, is called a leaf node. A leaf node is
the bottom-most node of the tree. There can be any number of leaf nodes
present in a general tree. Leaf nodes can also be called external nodes.
- Internal
nodes: A node has atleast one
child node known as an internal
- Ancestor
node:- An ancestor of a node is
any predecessor node on a path from the root to that node. The root node
doesn't have any ancestors. In the tree shown in the above image, nodes 1,
2, and 5 are the ancestors of node 10.
- Descendant: The immediate successor of the given node is
known as a descendant of a node. In the above figure, 10 is the descendant
of node 5.
Properties of Tree
data structure
o Recursive data
structure: The tree is also
known as a recursive data structure. A tree can be defined
as recursively because the distinguished node in a tree data structure is known
as a root node. The root node of the tree contains a link to
all the roots of its subtrees. The left subtree is shown in the yellow color in
the below figure, and the right subtree is shown in the red color. The left
subtree can be further split into subtrees shown in three different colors.
Recursion means reducing something in a self-similar manner. So, this recursive
property of the tree data structure is implemented in various applications.
- Number
of edges: If there are n nodes,
then there would n-1 edges. Each arrow in the structure represents the
link or path. Each node, except the root node, will have atleast one
incoming link known as an edge. There would be one link for the
parent-child relationship.
- Depth
of node x: The depth of node x can
be defined as the length of the path from the root to the node x. One edge
contributes one-unit length in the path. So, the depth of node x can also
be defined as the number of edges between the root node and the node x.
The root node has 0 depth.
- Height
of node x: The height of node x can
be defined as the longest path from the node x to the leaf node.
Based on the properties of the Tree data structure, trees are
classified into various categories.