DATA STRUCTURES AND

ALGORITHMS
Unit2- Linear Data Structures
CONTENTS
WHAT IS DATA STRUCTURE?
 Data Structure is a way of collecting and
organising data in such a way that we can
perform operations on these data in an effective
way.
 Data Structures is about rendering data
elements in terms of some relationship, for better
organization and storage.
 The way in which the data is organized affects
the performance of a program for different tasks.
WHY TO LEARN DATA STRUCTURES?
 As applications are getting complex and data
rich, there are three common problems that
applications face now-a-days-
1. Data Search
2. Processor Speed
3. Multiple Requests
To solve the above-mentioned problems, data
structures come to rescue.
CHARACTERISTICS OF A DATA STRUCTURE
 Correctness − Data structure implementation
should implement its interface correctly.

 Time Complexity − Running time or the

execution time of operations of data structure
must be as small as possible.

 Space Complexity − Memory usage of a data

structure operation should be as little as possible.
CLASSIFICATION OF DATA STRUCTURES
BUILT IN DATA STRUCTURES
 Those data structures for which a language has
built-in support are known as Built-in Data
structures. For example, most of the languages
provide the following built-in data types.
 Integers

 Boolean (true, false)

 Floating (Decimal numbers)

 Character and Strings

These are also referred to as Primitive Data

structures.
USER DEFINED DATA STRUCTURES
 Those data structures which are implemented
independently as they can be implemented in one or
the other way are known as derived data types.
 These data types are normally built by the
combination of primary or built-in data types and
associated operations on them. For example −
 List

 Array

 Stack

 Queue

These are also referred to as Non Primitive Data

Structures.
CLASSIFICATION OF DATA STRUCTURES
BASIC OPERATIONS ON DATA STRUCTURES
 The data in the data structures are processed by
certain operations. The particular data structure
chosen largely depends on the frequency of the
operation that needs to be performed on the data
structure.
 Design of efficient data structure must take
operations to be performed on data structures
into account.
BASIC OPERATIONS ON DATA STRUCTURES
 The most commonly used operations on data
structures are broadly categorized into following
types:
BASIC OPERATIONS ON DATA STRUCTURES
ARRAYS
DATA STRUCTURE - ARRAY
 An array is defined as an ordered set of similar
data items.
 All the data items of an array are stored in
consecutive memory locations in RAM.
 The elements of an array are of same data type
and each item can be accessed using the same
name.
 Array is a foundation of other data structures.
For example other data structures such as
Linked List, Stack, Queue etc. are implemented
using array.
DECLARATION OF ARRAY
 During declaration, the size of the array has to be
specified.
 The size used during declaration of the array
informs the compiler to allocate and reserve the
specified memory locations.
HOW DO YOU INITIALIZE AN ARRAY?
 You can initialize an array in four different ways:
2-DIMENSIONAL ARRAYS
 An array consisting of two subscripts is known as
two-dimensional array.
 In two dimensional arrays the array is divided
into rows and columns.
INITIALIZING TWO-DIMENSIONAL ARRAYS:
 Like the one-dimensional arrays, two
dimensional arrays may be initialized by
following their declaration with a list of initial
values enclosed in braces.
Ex: int a[2][3]={0,0,0,1,1,1};
 initializes the elements of the first row to zero
and the second row to one. The initialization is
done row by row.
REPRESENTATION OF 1D ARRAYS IN
MEMORY

 The following diagram represents an integer

array that has 12 elements. The index of the
array starts with 0, so the array having 12
elements has indexes from 0 to 11.
REPRESENTATION OF 2D ARRAYS IN
MEMORY

These are stored in the memory as given below.

 Row-Major order Implementation

 Column-Major order Implementation

In Row-Major Implementation of the arrays,

the arrays are stored in the memory in terms of the
row design, i.e. first the first row of the array is
stored in the memory then second and so on.
REPRESENTATION OF 2D ARRAYS IN
MEMORY

 Example: Suppose we have an array named arr

having 3 rows and 3 columns then it can be
stored in the memory in the following manner :
REPRESENTATION OF 2D ARRAYS IN
MEMORY
REPRESENTATION OF 2D ARRAYS IN
MEMORY
 In Column-Major Implementation of the arrays, the
arrays are stored in the memory in the term of the column
design, i.e. the first column of the array is stored in the
memory then the second and so on. By taking above eg. we
can show it as follows :
ARRAYS OF STRUCTURE
 An array of structures in C can be defined as the
collection of multiple structures variables where
each variable contains information about
different entities.
 The array of structures in C are used to store
information about multiple entities of different
data types.
 The array of structures is also known as the
collection of structures.
 Declaring an array of structure is same as
declaring an array of fundamental types.
ARRAYS OF STRUCTURE
DECLARATION OF ARRAYS OF STRUCTURE
 Declaring an array of structure is same as
declaring an array of fundamental types. Since
an array is a collection of elements of the same
type. In an array of structures, each element of
an array is of the structure type.
 Let’s take an example:
DECLARATION OF ARRAYS OF STRUCTURE
 Here is how we can declare an array of structure
car:
ADVANTAGES OF ARRAYS IN DATA
STRUCTURES
 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 ARRAYS IN DATA
STRUCTURES
 The number of elements in an array should be
predefined
 An array is static. It cannot alter its size after
declaration.
 Insertion and deletion operation in an array is
quite tricky as the array stores elements in
continuous form.
 Allocating excess memory than required may
lead to memory wastage.
BASIC OPERATIONS ON ARRAYS
 Following are the basic operations supported by
an array.
 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index
or by the value.
 Update − Updates an element at the given index.
TRAVERSING THE ARRAY
 Traversal in an array is a process of visiting each
element once.
INSERTION OPERATION
 Insert operation is to insert one or more data
elements into an array. Based on the requirement,
a new element can be added at the beginning, end,
or any given index of array.

 Insertion of an element can be done:

 At the beginning
 At the end and
 At any given index of an array.
 n index of array.
DELETION OPERATION
 Deletion refers to removing an existing element from the
array and re-organizing all elements of an array.

 Deletion of an element is the process of removing the

desired element and re-organizing it.
 You can also do deletion in different ways:
 At the beginning
 At the end
STACKS
WHAT IS A 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.
WHAT IS A STACK?
 Stack is a linear data structure in which the
insertion and deletion operations are performed
at only one end.
 In a stack, adding and removing of elements are
performed at a single position which is known as
"top".
 That means, a new element is added at top of
the stack and an element is removed from the top
of the stack. In stack, the insertion and deletion
operations are performed based on LIFO (Last In
First Out) principle.
FIGURE: STACK AND ITS OPERATIONS
BASIC FEATURES OF STACK
 Stack is an ordered list of similar data type.
 Stack is a LIFO(Last in First out) structure or we
can say FILO(First in Last out).
 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.
 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.
STACK REPRESENTATION AS AN ARRAY
 A stack data structure can be implemented using
a one-dimensional array.
 But stack implemented using array stores only a
fixed number of data values.
 This implementation is very simple.

 Just define a one dimensional array of specific

size and insert or delete the values into that
array by using LIFO principle with the help of a
variable called 'top'.
 Initially, the top is set to -1.
STACK OPERATIONS USING ARRAY
Before implementing actual operations, first follow the
below steps to create an empty stack.
 Step 1 - Include all the header files which are used in
the program and define a constant 'SIZE' with specific
value.
 Step 2 - Declare all the functions used in stack
implementation.
 Step 3 - Create a one dimensional array with fixed
size (int stack[SIZE])
 Step 4 - Define a integer variable 'top' and initialize
with '-1'. (int top = -1)
 Step 5 - In main method, display menu with list of
operations and make suitable function calls to
perform operation selected by the user on the stack.
BASIC OPERATIONS

Stack operations may involve initializing the stack,

using it and then de-initializing it. Apart from
these basic stuffs, a stack is used for the following
two primary operations −

 push() − Pushing (storing) an element on the

stack.

 pop() − Removing (accessing) an element from

the stack.
BASIC OPERATIONS
To use a stack efficiently, we need to check the
status of stack as well. For the same purpose, the
following functionality is added to stacks −
 peek() − get the top data element of the stack,
without removing it.
 isFull() − check if stack is full.

 isEmpty() − check if stack is empty.

At all times, we maintain a pointer to the last

PUSHed data on the stack. As this pointer always
represents the top of the stack, hence named top.
The top pointer provides top value of the stack
without actually removing it.
APPLICATIONS OF STACK
Following are the applications of stack:
 Expression Evaluation

 Expression Conversion
 Infix to Postfix
 Infix to Prefix
 Postfix to Infix
 Prefix to Infix

 Backtracking
 Memory Management
INFIX NOTATION
 We write expression in infix notation, e.g. a - b +
c, where operators are used in-between operands.
 It is easy for us humans to read, write, and speak
in infix notation but the same does not go well
with computing devices.
 An algorithm to process infix notation could be
difficult and costly in terms of time and space
consumption.
PREFIX NOTATION

 In this notation, operator is prefixed to operands,

i.e. operator is written ahead of operands. For
example, +ab.

 This is equivalent to its infix notation a + b.

Prefix notation is also known as Polish Notation.
POSTFIX NOTATION

 This notation style is known as Reversed Polish

Notation.

 In this notation style, the operator is postfixed to

the operands i.e., the operator is written after the
operands.

 For example, ab+. This is equivalent to its infix

notation a + b.
PARSING EXPRESSIONS
To parse any arithmetic expression, we need to
take care of operator precedence and associativity
also.
 Precedence- When an operand is in between
two different operators, which operator will take
the operand first, is decided by the precedence of
an operator over others. For example −

As multiplication operation has precedence over

addition, b * c will be evaluated first. A table of
operator precedence is provided later.
PARSING EXPRESSIONS
 Associativity- Associativity describes the rule
where operators with the same precedence
appear in an expression.
For example, in expression a + b − c, both +
and – have the same precedence, then which part
of the expression will be evaluated first, is
determined by associativity of those operators.
Here, both + and − are left associative, so the
expression will be evaluated as (a + b) − c.
PARSING EXPRESSIONS
 Following is an operator precedence and associativity
table (highest to lowest) −

 The above table shows the default behavior of

operators. At any point of time in expression
evaluation, the order can be altered by using
parenthesis.
 For example − In a + b*c, the expression part b*c
will be evaluated first, with multiplication as
precedence over addition. We here use parenthesis for
a + b to be evaluated first, like (a + b)*c.
QUEUE
INTRODUCTION
 Queue is also an abstract data type or a linear
data structure, just like stack data structure, in
which the first element is inserted from one end
called the REAR(also called tail), and the
removal of existing element takes place from the
other end called as FRONT(also called head).
 This makes queue as FIFO(First in First Out)
data structure, which means that element
inserted first will be removed first.
 The process to add an element into queue is
called Enqueue and the process of removal of an
element from queue is called Dequeue.
INTRODUCTION
BASIC FEATURES OF QUEUE
 Like stack, queue is also an ordered list of
elements of similar data types.
 Queue is a FIFO( First in First Out ) structure.

 Once a new element is inserted into the Queue,

all the elements inserted before the new element
in the queue must be removed, to remove the new
element.
 peek( ) function is oftenly used to return the
value of first element without dequeuing it.
APPLICATIONS OF QUEUE
 Serving requests on a single shared resource, like
a printer, CPU task scheduling etc.
 In real life scenario, Call Center phone systems
uses Queues to hold people calling them in an
order, until a service representative is free.
 Handling of interrupts in real-time systems. The
interrupts are handled in the same order as they
arrive i.e First come first served.
For Delete Operation
Delete-Queue(Queue, Front, Rear, Item)
Here, Queue is the place where data are stored. Rear represents the location in which the
data element is to be inserted and Front represents the location from which the data
element is to be removed. Front element is assigned to Item.

1. If Front = N+1 then Print: Underflow and Return. /*…Queue Empty

2. Set Item := Queue[Front]

3. Set Front := Front + 1

4. Return.

09/10/08 55
Example: Consider the following queue (linear queue).
Rear = 4 and Front = 1 and N = 7
10 50 30 40
1 2 3 4 5 6 7
(1) Insert 20. Now Rear = 5 and Front = 1

10 50 30 40 20
1 2 3 4 5 6 7
(2) Delete Front Element. Now Rear = 5 and Front = 2
50 30 40 20
1 2 3 4 5 6 7
(3) Delete Front Element. Now Rear = 5 and Front = 3
30 40 20
1 2 3 4 5 6 7
(4) Insert 60. Now Rear = 6 and Front = 3

30 40 20 60
1 2 3 4 5 6 7
09/10/08 56
Drawback of Linear Queue
• Once the queue is full, even though few elements from the front are deleted and
some occupied space is relieved, it is not possible to add anymore new elements,
as the rear has already reached the Queue’s rear most position.

Circular Queue
• This queue is not linear but circular.

• Its structure can be like the following figure:

• In circular queue, once the Queue is full the

"First" element of the Queue becomes the

"Rear" most element, if and only if the "Front" Figure: Circular Queue having
Rear = 5 and Front = 0
has moved forward. otherwise it will again be

a "Queue overflow" state.

09/10/08 57
Algorithms for Insert and Delete Operations in Circular Queue
For Insert Operation
Insert-Circular-Q(CQueue, Rear, Front, N, Item)
Here, CQueue is a circular queue where to store data. Rear represents the
location in which the data element is to be inserted and Front represents the
location from which the data element is to be removed. Here N is the maximum
size of CQueue and finally, Item is the new item to be added. Initailly Rear = 0 and
Front = 0.
1. If Front = 0 and Rear = 0 then Set Front := 1 and go to step 4.
2. If Front =1 and Rear = N or Front = Rear + 1
then Print: “Circular Queue Overflow” and Return.
3. If Rear = N then Set Rear := 1 and go to step 5.
4. Set Rear := Rear + 1
5. Set CQueue [Rear] := Item.
6. Return
09/10/08 58
For Delete Operation
Delete-Circular-Q(CQueue, Front, Rear, Item)
Here, CQueue is the place where data are stored. Rear represents the location in
which the data element is to be inserted and Front represents the location from
which the data element is to be removed. Front element is assigned to Item.
Initially, Front = 1.

1. If Front = 0 then
Print: “Circular Queue Underflow” and Return. /*..Delete without Insertion

2. Set Item := CQueue [Front]

3. If Front = N then Set Front = 1 and Return.
4. If Front = Rear then Set Front = 0 and Rear = 0 and Return.
5. Set Front := Front + 1
6. Return.

09/10/08 59
Example: Consider the following circular queue with N = 5.
1. Initially, Rear = 0, Front = 0. 4. Insert 20, Rear = 3, Front = 0.
Front

Rear

2. Insert 10, Rear = 1, Front = 1. 5. Insert 70, Rear = 4, Front = 1.

Rear Front
Front

Rear
3. Insert 50, Rear = 2, Front = 1. 6. Delete front, Rear = 4, Front = 2.
Front Rear Front

Rear

09/10/08 60
7. Insert 100, Rear = 5, Front = 2. 10. Delete front, Rear = 1, Front = 3.
Rear
Front

Front

Rear

8. Insert 40, Rear = 1, Front = 2. 11. Delete front, Rear = 1, Front = 4.

Rear
Rear Front

Front

9. Insert 140, Rear = 1, Front = 2. 12. Delete front, Rear = 1, Front = 5.

As Front = Rear + 1, so Queue overflow. Rear

Rear Front

Front

09/10/08 61
PRIORITY QUEUE
PRIORITY QUEUE
 Priority Queue is more specialized data structure
than Queue.
 In Priority queue items are ordered by key value
so that item with the lowest value of key is at
front and item with the highest value of key is at
rear or vice versa.
 So we're assigned priority to item based on its
key value.
 A priority queue is a collection in which items can
be added at any time, but the only item that can
be removed is the one with the highest priority.
OPERATIONS IN PRIORITY QUEUE
It supports the following operations:
 add(x): add item x

 remove: remove the highest priority item

 peek: return the highest priority item (without

removing it)
 size: return the number of items in the priority
queue
 isEmpty: return whether the priority queue has
no items
 isFull: return whether the priority queue is full
PRIORITY QUEUE REPRESENTATION
HOW DOES PRIORITY QUEUE DIFFER
FROM A QUEUE?

 In a queue, the first-in-first-out rule is

implemented whereas, in a priority queue, the
values are removed on the basis of priority.
 The element with the highest priority is removed
first.
 If elements with the same priority occur, they are
served according to their order in the queue.
IMPLEMENTATION OF PRIORITY QUEUE
 Priority queue can be implemented using an
array, a linked list, a heap data structure or a
binary search tree.
 Among these data structures, heap data
structure provides an efficient implementation of
priority queues.
A comparative analysis of different implementations of priority queue
is given below.
LINKED LIST
 Consider this example:
In a game of Treasure Hunt, you start by looking
for the first clue. When you find it, instead of
having the treasure, it has the location of the
next clue and so on.
You keep following the clues until you get to the
treasure.!

That is where you can use a LINKED LIST.

 INTRODUCTION TO LINKED LIST
 A linked list is a series of connected "nodes" that
contains the "address" of the next node.
 Each node can store a data point which may be a
number, a string or any other type of data.
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 - REPRESENTATION

Each node is separated into two different parts:

 The first part holds the information of the element or node
 The second piece contains the address of the next node (link /
next-pointer field) in this structure list.

 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.
ADVANTAGES & DISADVANTAGES OF
LINKED LIST
Advantages Disadvantages

 They are a dynamic in  The memory is wasted

nature which allocates as pointers require
the memory when extra memory for
required. storage.
 Insertion and deletion  No element can be
operations can be easily
implemented.
accessed randomly; it
has to access each
 Stacks and queues can node sequentially.
be easily executed.
 Reverse Traversing is
 Linked List reduces the
access time. difficult in linked list.
TYPES OF LINKED LIST
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.
SINGLY/SIMPLE LINKED LIST
SINGLY/SIMPLE LINKED LIST
 Singly linked lists contain nodes which have a data
part as well as an address part i.e. next, which
points to the next node in the sequence of nodes.

 The operations we can perform on singly linked

lists are insertion, deletion and traversal.
OPERATIONS ON SINGLE LINKED LIST
The following operations are performed on a Single
Linked List
 Insertion

 Deletion

 Display
OPERATIONS ON SINGLE LINKED LIST
Before we implement actual operations, first we need to
set up an empty list. First, perform the following steps
before implementing actual operations.
 Step 1 - Include all the header files which are used
in the program.
 Step 2 - Declare all the user defined functions.

 Step 3 - Define a Node structure with two

members data and next
 Step 4 - Define a Node pointer 'head' and set it
to NULL.
 Step 5 - Implement the main method by displaying
operations menu and make suitable function calls in
the main method to perform user selected operation.
INSERTION – SINGLE LINKED
LIST
INSERTION – SINGLE LINKED LIST

In a single linked list, the insertion operation can be

performed in three ways. They are as follows...

• Inserting At Beginning of the list

• Inserting At End of the list
• Inserting At Specific location in the
list
INSERTING AT BEGINNING OF THE LIST
 Step 1 - Create a newNode with given value.
 Step 2 - Check whether list
is Empty (head == NULL)
 Step 3 - If it is Empty then,
set newNode→next = NULL and head = new
Node.
 Step 4 - If it is Not Empty then,
set newNode→next = head and head = newN
ode.
INSERTING AT END OF THE LIST
 Step 1 - Create a newNode with given value
and newNode → next as NULL.
 Step 2 - Check whether list
is Empty (head == NULL).
 Step 3 - If it is Empty then, set head = newNode.
 Step 4 - If it is Not Empty then, define a node
pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node
until it reaches to the last node in the list
(until temp → next is equal to NULL).
 Step 6 - Set temp → next = newNode.
INSERTING AT SPECIFIC LOCATION IN
THE LIST (AFTER A NODE)

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set newNode →
next = NULL and head = newNode.
 Step 4 - If it is Not Empty then, define a node
pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches
to the node after which we want to insert the newNode
(until temp1 → data is equal to location, here location is the
node value after which we want to insert the newNode).
 Step 6 - Every time check whether temp is reached to last node
or not. If it is reached to last node then display 'Given node is
not found in the list!!! Insertion not possible!!!' and
terminate the function. Otherwise move the temp to next node.
 Step 7 - Finally, Set 'newNode → next = temp → next' and
'temp → next = newNode'
DELETION – SINGLE LINKED
LIST
DELETION – SINGLE LINKED LIST
In a single linked list, the deletion operation can be
performed in three ways. They are as follows...

• Deleting from Beginning of the list

• Deleting from End of the list
• Deleting a Specific Node
DELETING FROM BEGINNING OF THE
LIST

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!!
Deletion is not possible' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node
pointer 'temp' and initialize with head.
 Step 4 - Check whether list is having only one node
(temp → next == NULL)
 Step 5 - If it is TRUE then set head = NULL and
delete temp (Setting Empty list conditions)
 Step 6 - If it is FALSE then set head = temp → next,
and delete temp.
DELETING FROM END OF THE LIST

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion
is not possible' and terminate the function.
 Step 3 - If it is Not Empty then, define two Node
pointers 'temp1' and 'temp2' and initialize 'temp1' with head.
 Step 4 - Check whether list has only one Node (temp1 →
next == NULL)
 Step 5 - If it is TRUE. Then, set head = NULL and
delete temp1. And terminate the function. (Setting Empty list
condition)
 Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and
move temp1 to its next node. Repeat the same until it reaches to
the last node in the list. (until temp1 → next == NULL)
 Step 7 - Finally, Set temp2 → next = NULL and delete temp1.
DELETING A SPECIFIC NODE FROM THE
LIST
 Step 1 - Check whether list is Empty (head == NULL)
 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2'
and initialize 'temp1' with head.
 Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or
to the last node. And every time set 'temp2 = temp1' before moving the 'temp1' to
its next node.
 Step 5 - If it is reached to the last node then display 'Given node not found in
the list! Deletion not possible!!!'. And terminate the function.
 Step 6 - If it is reached to the exact node which we want to delete, then check
whether list is having only one node or not
 Step 7 - If list has only one node and that is the node to be deleted, then
set head = NULL and delete temp1 (free(temp1)).
 Step 8 - If list contains multiple nodes, then check whether temp1 is the first
node in the list (temp1 == head).
 Step 9 - If temp1 is the first node then move the head to the next node (head =
head → next) and delete temp1.
 Step 10 - If temp1 is not first node then check whether it is last node in the list
(temp1 → next == NULL).
 Step 11 - If temp1 is last node then set temp2 → next = NULL and
delete temp1 (free(temp1)).
 Step 12 - If temp1 is not first node and not last node then set temp2 →
next = temp1 → next and delete temp1 (free(temp1)).
DOUBLY LINKED LIST
DOUBLY LINKED LIST
 Double linked list is a sequence of elements in
which every element has links to its previous
element and next element in the sequence.
 We can traverse forward by using the next field and
can traverse backward by using the previous field.
 Every node in a double linked list contains three
fields and they are shown in the following figure:
DOUBLY LINKED LIST
Following are the important terms to understand the
concept of doubly 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.
 Prev − Each link of a linked list contains a link to the
previous link called Prev.

Important Points to be Remembered

 In double linked list, the first node must be always pointed by head
 Always the previous field of the first node must be NULL
 Always the next field of the last node must be NULL
DOUBLY LINKED LIST REPRESENTATION

As per the above illustration, following are the

important points to be considered.
 Doubly Linked List contains a link element called first
and last.
 Each link carries a data field(s) and two link fields
called next and prev.
 Each link is linked with its next link using its next link.
 Each link is linked with its previous link using its
previous link.
 The last link carries a link as null to mark the end of
the list.
OPERATIONS ON DOUBLE LINKED LIST
In a double linked list, we perform the following
operations...
 Insertion

 Deletion

 Display
INSERTION – DOUBLY LINKED
LIST
INSERTION – DOUBLY LINKED LIST

In a Doubly linked list, the insertion operation can be

performed in three ways. They are as follows...

• Inserting At Beginning of the list

• Inserting At End of the list
• Inserting At Specific location in the
list
INSERTING AT BEGINNING OF THE LIST
 Step 1 - Create a newNode with given value
and newNode → previous as NULL.
 Step 2 - Check whether list
is Empty (head == NULL)
 Step 3 - If it is Empty then,
assign NULL to newNode →
next and newNode to head.
 Step 4 - If it is not Empty then,
assign head to newNode →
next and newNode to head.
INSERTING AT END OF THE LIST
 Step 1 - Create a newNode with given value
and newNode → next as NULL.
 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty, then assign NULL to newNode
→ previous and newNode to head.
 Step 4 - If it is not Empty, then, define a node
pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it
reaches to the last node in the list (until temp →
next is equal to NULL).
 Step 6 - Assign newNode to temp →
next and temp to newNode → previous.
INSERTING AT SPECIFIC LOCATION IN
THE LIST (AFTER A NODE)

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, assign NULL to both newNode →
previous & newNode → next and set newNode to head.
 Step 4 - If it is not Empty then, define two node
pointers temp1 & temp2 and initialize temp1 with head.
 Step 5 - Keep moving the temp1 to its next node until it reaches to
the node after which we want to insert the newNode (until temp1 →
data is equal to location, here location is the node value after which
we want to insert the newNode).
 Step 6 - Every time check whether temp1 is reached to the last
node. If it is reached to the last node then display 'Given node is
not found in the list!!! Insertion not possible!!!' and terminate
the function. Otherwise move the temp1 to next node.
 Step 7 - Assign temp1 → next to temp2, newNode to temp1 →
next, temp1 to newNode → previous, temp2 to newNode →
next and newNode to temp2 → previous.
DELETION – DOUBLY LINKED
LIST
DELETION – DOUBLY LINKED LIST
In a doubly linked list, the deletion operation can be
performed in three ways. They are as follows...

• Deleting from Beginning of the list

• Deleting from End of the list
• Deleting a Specific Node
DELETING FROM BEGINNING OF THE
LIST

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!!
Deletion is not possible' and terminate the function.
 Step 3 - If it is not Empty then, define a Node
pointer 'temp' and initialize with head.
 Step 4 - Check whether list is having only one node
(temp → previous is equal to temp → next)
 Step 5 - If it is TRUE, then set head to NULL and
delete temp (Setting Empty list conditions)
 Step 6 - If it is FALSE, then assign temp →
next to head, NULL to head → previous and
delete temp.
DELETING FROM END OF THE LIST

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty, then display 'List is Empty!!!
Deletion is not possible' and terminate the function.
 Step 3 - If it is not Empty then, define a Node
pointer 'temp' and initialize with head.
 Step 4 - Check whether list has only one Node (temp →
previous and temp → next both are NULL)
 Step 5 - If it is TRUE, then assign NULL to head and
delete temp. And terminate from the function.
(Setting Empty list condition)
 Step 6 - If it is FALSE, then keep moving temp until it
reaches to the last node in the list. (until temp → next is
equal to NULL)
 Step 7 - Assign NULL to temp → previous → next and
delete temp.
DELETING A SPECIFIC NODE FROM THE
LIST
Step 1 - Check whether list is Empty (head == NULL)
 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is not Empty, then define a Node pointer 'temp' and initialize with head.
 Step 4 - Keep moving the temp until it reaches to the exact node to be deleted or to the last node.
 Step 5 - If it is reached to the last node, then display 'Given node not found in the list!
Deletion not possible!!!' and terminate the fuction.
 Step 6 - If it is reached to the exact node which we want to delete, then check whether list is
having only one node or not
 Step 7 - If list has only one node and that is the node which is to be deleted then
set head to NULL and delete temp (free(temp)).
 Step 8 - If list contains multiple nodes, then check whether temp is the first node in the list (temp
== head).
 Step 9 - If temp is the first node, then move the head to the next node (head = head → next),
set head of previous to NULL (head → previous = NULL) and delete temp.
 Step 10 - If temp is not the first node, then check whether it is the last node in the list (temp →
next == NULL).
 Step 11 - If temp is the last node then set temp of previous of next to NULL (temp → previous
→ next = NULL) and delete temp (free(temp)).
 Step 12 - If temp is not the first node and not the last node, then
set temp of previous of next to temp of next (temp → previous → next = temp →
next), temp of next of previous to temp of previous (temp → next → previous = temp →
previous) and delete temp (free(temp)).
CIRCULAR LINKED LIST
CIRCULAR LINKED LIST
 A circular linked list is a sequence of elements in
which every element has a link to its next element
in the sequence and the last element has a link to
the first element.
 Both Singly Linked List and Doubly Linked List
can be made into a circular linked list.
CIRCULAR LINKED LIST

Singly Linked List as Circular

 In singly linked list, the next pointer of the last
node points to the first node.

Doubly Linked List as Circular

 In doubly linked list, the next pointer of the last
node points to the first node and the previous
pointer of the first node points to the last node
making the circular in both directions.
OPERATIONS ON CIRCULAR LINKED
LIST
In a circular linked list, we perform the
following operations:
 Insertion

 Deletion

 Display
INSERTION – CIRCULAR
LINKED LIST
INSERTION – CIRCULAR LINKED LIST

In a circular linked list, the insertion operation can

be performed in three ways. They are as follows...

• Inserting At Beginning of the list

• Inserting At End of the list
• Inserting At Specific location in the
list
INSERTING AT BEGINNING OF THE LIST
 Step 1 - Create a newNode with given value.
 Step 2 - Check whether list
is Empty (head == NULL)
 Step 3 - If it is Empty then,
set head = newNode and newNode→next = he
ad .
 Step 4 - If it is Not Empty then, define a Node
pointer 'temp' and initialize with 'head'.
 Step 5 - Keep moving the 'temp' to its next node
until it reaches to the last node (until 'temp →
next == head').
 Step 6 - Set 'newNode → next =head',
'head = newNode' and 'temp → next = head'.
INSERTING AT END OF THE LIST
 Step 1 - Create a newNode with given value.
 Step 2 - Check whether list
is Empty (head == NULL).
 Step 3 - If it is Empty then,
set head = newNode and newNode → next = head.
 Step 4 - If it is Not Empty then, define a node
pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it
reaches to the last node in the list (until temp →
next == head).
 Step 6 - Set temp → next = newNode and newNode
→ next = head.
INSERTING AT SPECIFIC LOCATION IN
THE LIST (AFTER A NODE)
 Step 1 - Create a newNode with given value.
 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set head = newNode and newNode → next = head.
 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the node after which
we want to insert the newNode (until temp1 → data is equal to location, here location
is the node value after which we want to insert the newNode).
 Step 6 - Every time check whether temp is reached to the last node or not. If it is
reached to last node then display 'Given node is not found in the list!!! Insertion
not possible!!!' and terminate the function. Otherwise move the temp to next node.
 Step 7 - If temp is reached to the exact node after which we want to insert the
newNode then check whether it is last node (temp → next == head).
 Step 8 - If temp is last node then set temp → next = newNode and newNode →
next = head.
 Step 8 - If temp is not last node then set newNode → next = temp → next and temp
→ next = newNode.
DELETION – CIRCULAR LINKED
LIST
DELETION – CIRCULAR LINKED LIST
In a circular linked list, the deletion operation can be
performed in three ways. They are as follows...

• Deleting from Beginning of the list

• Deleting from End of the list
• Deleting a Specific Node
DELETING FROM BEGINNING OF THE
LIST

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!!
Deletion is not possible' and terminate the function.
 Step 3 - If it is Not Empty then, define two Node
pointers 'temp1' and 'temp2' and initialize both
'temp1' and 'temp2' with head.
 Step 4 - Check whether list is having only one node
(temp1 → next == head)
 Step 5 - If it is TRUE then set head = NULL and
delete temp1 (Setting Empty list conditions)
 Step 6 - If it is FALSE move the temp1 until it reaches
to the last node. (until temp1 → next == head )
 Step 7 - Then set head = temp2 → next, temp1 →
next = head and delete temp2.
DELETING FROM END OF THE LIST

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion
is not possible' and terminate the function.
 Step 3 - If it is Not Empty then, define two Node
pointers 'temp1' and 'temp2' and initialize 'temp1' with head.
 Step 4 - Check whether list has only one Node (temp1 →
next == head)
 Step 5 - If it is TRUE. Then, set head = NULL and
delete temp1. And terminate from the function.
(Setting Empty list condition)
 Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and
move temp1 to its next node. Repeat the same
until temp1 reaches to the last node in the list. (until temp1 →
next == head)
 Step 7 - Set temp2 → next = head and delete temp1.
DELETING A SPECIFIC NODE FROM THE
LIST
Step 1 - Check whether list is Empty (head == NULL)
 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize
'temp1' with head.
 Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to the last node.
And every time set 'temp2 = temp1' before moving the 'temp1' to its next node.
 Step 5 - If it is reached to the last node then display 'Given node not found in the list! Deletion
not possible!!!'. And terminate the function.
 Step 6 - If it is reached to the exact node which we want to delete, then check whether list is
having only one node (temp1 → next == head)
 Step 7 - If list has only one node and that is the node to be deleted then set head = NULL and
delete temp1 (free(temp1)).
 Step 8 - If list contains multiple nodes then check whether temp1 is the first node in the list
(temp1 == head).
 Step 9 - If temp1 is the first node then set temp2 = head and keep moving temp2 to its next node
until temp2 reaches to the last node. Then set head = head → next, temp2 → next = head and
delete temp1.
 Step 10 - If temp1 is not first node then check whether it is last node in the list (temp1 → next ==
head).
 Step 1 1- If temp1 is last node then set temp2 → next = head and delete temp1 (free(temp1)).
 Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1 →
next and delete temp1 (free(temp1)).
APPLICATIONS OF LINKED LIST
APPLICATIONS OF LINKED LIST IN
COMPUTER SCIENCE

 Implementation of stacks and queues

 Implementation of graphs : Adjacency list
representation of graphs is most popular which is uses
linked list to store adjacent vertices.
 Dynamic memory allocation : We use linked list of free
blocks.
 Maintaining directory of names
 Performing arithmetic operations on long integers
 Manipulation of polynomials by storing constants in the
node of linked list
 Representing sparse matrices
APPLICATIONS OF LINKED LIST IN REAL
WORLD

 Image viewer – Previous and next images are

linked, hence can be accessed by next and previous
button.
 Previous and next page in web browser – We can
access previous and next url searched in web
browser by pressing back and next button since,
they are linked as linked list.
 Music Player – Songs in music player are linked to
previous and next song. you can play songs either
from starting or ending of the list.
END..