DATA STRUCTURE USING C++ BCA313 UNIT III
DATA STRUCTURE USING C++
BCA313
Unit III Syllabus
Linked list: Representation and Implementation of Singly Linked Lists, Traversing and
Searching of Linked List, Overflow and Underflow, Insertion and deletion to/from Linked
Lists, Insertion and deletion Algorithms, Doubly linked list, Linked List v/s Array.
LINKED LIST
A linked list, or one-way list, is a linear collection of data elements, called nodes, where the
linear order is given by means of pointers. That is, each node is divided into two parts: the
first part contains the information of the element, and the second part, called the link field or
next pointer field, contains the address of the next node in the list. The list starts traversing
from the head, while the tail ends the list by pointing at NULL.
Advantages of Linked Lists
They are a dynamic in nature which allocates the memory when required.
Insertion and deletion operations can be easily implemented.
Stacks and queues can be easily executed.
Linked List reduces the access time.
Disadvantages of Linked Lists
The memory is wasted as pointers require extra memory for storage.
No element can be accessed randomly; it has to access each node sequentially.
Reverse Traversing is difficult in linked list.
Applications of Linked Lists
Linked lists are used to implement stacks, queues, graphs, etc.
In Linked Lists we don't need to know the size in advance.
1|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Types of Linked Lists
There are 3 different implementations of Linked List available, they are:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
Let's know more about them and how they are different from each other.
Singly 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.
Doubly Linked List
In a doubly linked list, each node contains a data part and two addresses, one for the
previous node and one for the next node.
Circular Linked List
In circular linked list the last node of the list holds the address of the first node hence forming
a circular chain.
2|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Difference between Array and Linked List
Both Linked List and Array are used to store linear data of similar type, but an array
consumes contiguous memory locations allocated at compile time, i.e. at the time of
declaration of array, while for a linked list, memory is assigned as and when data is added to
it, which means at runtime.
This is the basic and the most important difference between a linked list and an array. In the
section below, we will discuss this in details along with highlighting other differences.
Linked List vs. Array
Array is a datatype which is widely implemented as a default type, in almost all the modern
programming languages, and is used to store data of similar type.
But there are many use cases, like the one where we don't know the quantity of data to be
stored, for which advanced data structures are required, and one such data structure is linked
list.
Let's understand how array is different from Linked list.
ARRAY LINKED LIST
Array is a collection of elements of similar Linked List is an ordered collection of elements
data type. of same type, which are connected to each other
using pointers.
Array supports Random Access, which Linked List supports Sequential Access, which
means elements can be accessed directly means to access any element/node in a linked list,
using their index, like arr[0] for 1st we have to sequentially traverse the complete
element, arr[6] for 7th element etc. linked list, up to that element.
Hence, accessing elements in an array is To access nth element of a linked list, time
fast with a constant time complexity of complexity is O(n).
O(1).
In an array, elements are stored in In a linked list, new elements can be stored
contiguous memory location or anywhere in the memory.
consecutive manner in the memory. Address of the memory location allocated to the
new element is stored in the previous node of
linked list, hence forming a link between the two
nodes/elements.
3|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
In array, Insertion and Deletion In case of linked list, a new element is stored at
operation takes more time, as the memory the first free and available memory location, with
locations are consecutive and fixed. only a single overhead step of storing the address
of memory location in the previous node of
linked list.
Insertion and Deletion operations are fast in
linked list.
Memory is allocated as soon as the array Memory is allocated at runtime, as and when a
is declared, at compile time. It's also new node is added. It's also known as Dynamic
known as Static Memory Allocation. Memory Allocation.
In array, each element is independent and In case of a linked list, each node/element points
can be accessed using it's index value. to the next, previous, or maybe both nodes.
Array can single dimensional, two Linked list can be Linear(Singly), Doubly or
dimensional or multidimensional Circular linked list.
Size of the array must be specified at time Size of a Linked list is variable. It grows at
of array decalaration. runtime, as more nodes are added to it.
Below we have a pictorial representation showing how consecutive memory locations are
allocated for array, while in case of linked list random memory locations are assigned to
nodes, but each node is connected to its next node using pointer.
On the left, we have Array and on the right, we have Linked List.
4|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
What is a Node?
A Node in a linked list holds the data value and the pointer which points to the location of the
next node in the linked list.
In the picture above we have a linked list, containing 4 nodes, each node has some data(A, B,
C and D) and a pointer which stores the location of the next node.
You must be wondering why we need to store the location of the next node. Well, because
the memory locations allocated to these nodes are not contiguous hence each node should
know where the next node is stored.
Basic Operations
Following are the basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.
Insertion − Adds an element at the last of the list.
Insertion − Adds an element at given location of the list.
Deletion − Deletes an element at the beginning of the list.
Deletion − Deletes an element at last of the list.
Deletion − Deletes an element at given location of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this with
diagrams here. First, create a node using the same structure and find the location where it has
to be inserted.
5|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C
(RightNode). Then point [Link] to C −
[Link] −> RightNode;
It should look like this −
Now, the next node at the left should point to the new node.
[Link] −> NewNode;
This will put the new node in the middle of the two. The new list should look like this −
6|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Similar steps should be taken if the node is being inserted at the beginning of the list. While
inserting it at the end, the second last node of the list should point to the new node and the
new node will point to NULL.
Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial representation.
First, locate the target node to be removed, by using searching algorithms.
The left (previous) node of the target node now should point to the next node of the target
node −
[Link] −> [Link];
This will remove the link that was pointing to the target node. Now, using the following code,
we will remove what the target node is pointing at.
[Link] −> NULL;
We need to use the deleted node. We can keep that in memory otherwise we can simply
deallocate memory and wipe off the target node completely.
Algorithm for Singly Linked List
7|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Insert at first position in Singly Linked List
Algorithm: INSERTATFIRST(INFO, HEAD, NEWNODE, NEXT, ITEM)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set NEWNODE ->NEXT=HEAD
Step 5 : Set HEAD= NEWNODE.
Step 6 : Stop
Insert at Last Position in Singly Linked List
Algorithm: INSERTATLAST(INFO, HEAD, NEWNODE, NEXT, ITEM, PTR)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set NEWNODE ->NEXT=NULL
Step 5 : Set PTR=HEAD
Step 6 : Repeat Step 7 While(PTR->NEXT!=NULL)
Step 7 : PTR=PTR->NEXT
Step 8 : Set PTR->NEXT= NEWNODE
Step 9 : Stop
Insert at given Location in Singly Linked List
Algorithm: INSERTATGIVENLOCATION(INFO, HEAD, NEWNODE, NEXT, ITEM,
PTR, LOC, COUNT, PTR1)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set COUNT=0
Step 5 : Set PTR=HEAD
Step 6 : Repeat Step 7 to 9 While(COUNT!=LOC)
Step 7 : PTR1=PTR
Step 8 : PTR=PTR->NEXT
Step 9 : COUNT++
Step 9 : NEWNODE->NEXT=PTR
Step 10 : Set PTR1->NEXT= NEWNODE
Step 11 : Stop
Delete at First position in Singly Linked List
Algorithm: DELETEATFIRST(INFO, HEAD, PTR, NEXT)
Step 1 : if (HEAD ==NULL) then Print UNDERFLOW and Return
Step 2 : PTR=HEAD
Step 3 : Set HEAD=HEAD->NEXT
Step 4 : Print PTR->INFO
Step 5 :.Stop
8|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Delete at last position in Singly Linked List
Algorithm: DELETEATLAST(INFO, HEAD, PTR, NEXT, PTR1)
Step 1 : if (HEAD==NULL) then Print UNDERFLOW and Return
Step 2 : PTR=HEAD
Step 3 : Repeat Step 4 and 5 while(PTR->NEXT!=NULL)
Step 4 : PTR1=PTR
Step 5 :. PTR=PTR->NEXT
Step 6 : PTR1->NEXT=NULL
Step 7 : Print PTR->INFO
Step 5 :.Stop
Delete at given position in Singly Linked List
Algorithm: DELETEATGIVENLOCATION(INFO, HEAD, NEXT, ITEM, PTR, LOC,
COUNT, PTR1)
Step 1 : if (HEAD==NULL) then Print UNDERFLOW and Return
Step 2 : Set COUNT=0
Step 3 : Set PTR=HEAD
Step 4 : Repeat Step 7 to 9 While(COUNT!=LOC)
Step 5 : PTR1=PTR
Step 6 : PTR=PTR->NEXT
Step 7 : COUNT++
Step 8 : PTR1->NEXT=PTR->NEXT
Step 9 : Print PTR->INFO
Step 10 : Stop
Traverse Singly Linked List
Algorithm: TRAVERSESLL(INFO, HEAD, PTR, NEXT)
Step 1 : if (HEAD ==NULL) then Print Linked List is Empty and Return
Step 2 : PTR=HEAD
Step 3 : Repeat Step 4 and 5 while(PTR!=NULL)
Step 4 : Print PTR->INFO
Step 5 : PTR=PTR->NEXT
Step 6 : Stop
Search in Singly Linked List
Algorithm: SEARCHSLL(INFO, HEAD, PTR, NEXT, ITEM, POS, FLAG)
Step 1 : if (HEAD ==NULL) then Print Linked List is Empty and Return
Step 2 : PTR=HEAD, POS=0, FLAG=FALSE
Step 3 : Repeat Step 4 to 6 while(PTR!=NULL)
Step 4 : POS++
Step 5 : if( PTR->INFO==ITEM)
FLAG=TRUE
Break;
Step 6 : PTR=PTR
Step 7 : if(FLAG==TRUE)
9|Pa ge
DATA STRUCTURE USING C++ BCA313 UNIT III
Print ITEM found at POS
Else
Print ITEM not Found
Step 8 : Stop
Doubly Linked List
Doubly Linked List is a variation of Linked list in which navigation is possible in both ways,
either forward and backward easily as compared to Single Linked List. Following are the
important terms to understand the concept of doubly linked list.
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.
Algorithm for Doubly Linked List
Insert at first position in Doubly Linked List
Algorithm: INSERTATFIRST(INFO, HEAD, NEWNODE, NEXT, PREV, ITEM)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 3 : Set NEWNODE ->PREV=NULL
Step 4 : Set HEAD->PREV=NEWNODE
Step 4 : Set NEWNODE->NEXT=HEAD
Step 5 : Set HEAD= NEWNODE.
Step 6 : Stop
Insert at Last Position in Doubly Linked List
Algorithm: INSERTATLAST(INFO, HEAD, NEWNODE, NEXT, PREV, ITEM, PTR,
LAST)
Step 1 : NODE *NEWNODE = new NODE
10 | P a g e
DATA STRUCTURE USING C++ BCA313 UNIT III
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set NEWNODE ->NEXT=NULL
Step 5 : Set NEWNODE->PREV=LAST
Step 6 : Set LAST->NEXT=NEWNODE
Step 7 : Set LAST =NEWNODE
Step 8 : Stop
Insert at given Location in Doubly Linked List
Algorithm: INSERTATGIVENLOCATION(INFO, HEAD, NEWNODE, NEXT,
PREV, ITEM, PTR, PTR1,LOC, COUNT)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set COUNT=0
Step 5 : Set PTR=HEAD
Step 6 : Repeat Step 7 to 9 While(COUNT!=LOC)
Step 7 : PTR1=PTR
Step 8 : PTR=PTR->NEXT
Step 9 : COUNT++
Step 9 : NEWNODE->NEXT=PTR
Step 9 : NEWNODE->PREV=PTR1
Step 10 : Set PTR->PREV= NEWNODE
Step 11 : Set PTR1->NEXT= NEWNODE
Step 11 : Stop
Delete at First position in Doubly Linked List
Algorithm: DELETEATFIRST(INFO, HEAD, PTR, NEXT, PREV)
Step 1 : if (HEAD ==NULL) then Print UNDERFLOW and Return
Step 2 : PTR=HEAD
Step 3 : HEAD->NEXT->PREV=NULL
Step 4 : Set HEAD=HEAD->NEXT
Step 5 : Print PTR->INFO
Step 5 : Stop
Delete at last position in Doubly Linked List
Algorithm: DELETEATLAST(INFO, HEAD, PTR, NEXT, PREV, LAST)
Step 1 : if (HEAD==NULL) then Print UNDERFLOW and Return
Step 2 : PTR=LAST
Step 3 : LAST=LAST->PREV
Step 4 : LAST->NEXT=NULL
Step 5: Print PTR->INFO
Step 6 : Stop
Delete at given position in Doubly Linked List
11 | P a g e
DATA STRUCTURE USING C++ BCA313 UNIT III
Algorithm: DELETEATGIVENLOCATION(INFO, HEAD, NEXT, PREV, ITEM,
PTR, LOC, COUNT, PREV)
Step 1 : if (HEAD==NULL) then Print UNDERFLOW and Return
Step 2 : Set COUNT=0
Step 3 : Set PTR=HEAD
Step 4 : Repeat Step 7 to 9 While(COUNT!=LOC)
Step 5 : PTR1=PTR
Step 6 : PTR=PTR->NEXT
Step 7 : COUNT++
Step 8 : PTR1->NEXT=PTR->NEXT
Step 9 : PTR->NEXT->PREV=PTR1
Step 9 : Print PTR->INFO
Step 10 : Stop
Traverse Doubly Linked List
In Forward Direction
Algorithm: TRAVERSEDLLFORWARD(INFO, HEAD, PTR, NEXT)
Step 1 : if (HEAD ==NULL) then Print - Linked List is Empty and Return
Step 2 : PTR=HEAD
Step 3 : Repeat Step 4 and 5 while(PTR!=NULL)
Step 4 : Print PTR->INFO
Step 5 : PTR=PTR->NEXT
Step 6 : Stop
In Backward Direction
Algorithm: TRAVERSEDLLBACKWARD(INFO, HEAD, PTR, NEXT, PREV)
Step 1 : if (HEAD ==NULL) then Print - Linked List is Empty and Return
Step 2 : PTR=LAST
Step 3 : Repeat Step 4 and 5 while(PTR!=NULL)
Step 4 : Print PTR->INFO
Step 5 : PTR=PTR->PREV
Step 6 : Stop
Search in Doubly Linked List
Algorithm: SEARCHDLL(INFO, HEAD, PTR, NEXT, PREV ITEM, POS, FLAG)
Step 1 : if (HEAD ==NULL) then Print - Linked List is Empty and Return
Step 2 : PTR=HEAD, POS=0, FLAG=FALSE
Step 3 : Repeat Step 4 to 6 while(PTR!=NULL)
Step 4 : POS++
Step 5 : if( PTR->INFO==ITEM)
FLAG=TRUE
Break;
Step 6 : PTR=PTR
Step 7 : if(FLAG==TRUE)
Print ITEM found at POS
12 | P a g e
DATA STRUCTURE USING C++ BCA313 UNIT III
Else
Print ITEM not Found
Step 8 : Stop
Circular Linked List
In single linked list, every node points to its next node in the sequence and the last node
points NULL. But in circular linked list, every node points to its next node in the sequence
but the last node points to the first node in the 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.
Example
Algorithms for Circular Singly Linked List
Insert at first position in Circular Singly Linked List
Algorithm: INSERTATFIRST(INFO, HEAD, NEWNODE, NEXT, ITEM, LAST)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set NEWNODE ->NEXT=HEAD
Step 5 : Set LAST->NEXT= NEWNODE.
Step 6 : Set HEAD= NEWNODE.
Step 7 : Stop
Insert at Last Position in Circular Singly Linked List
Algorithm: INSERTATLAST(INFO, HEAD, NEWNODE, NEXT, ITEM, PTR, LAST)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE->INFO=ITEM
Step 4 : Set NEWNODE->NEXT=HEAD
13 | P a g e
DATA STRUCTURE USING C++ BCA313 UNIT III
Step 5 : LAST->NEXT=NEWNODE
Step 6 : LAST = NEWNODE
Step 7 : Stop
Insert at given Location in Circular Singly Linked List
Algorithm: INSERTATGIVENLOCATION(INFO, HEAD, NEWNODE, NEXT, ITEM,
PTR, LOC, COUNT, PTR1, LAST)
Step 1 : NODE *NEWNODE = new NODE
Step 2 : if (NEWNODE ==NULL) then print OVERFLOW and Return
Step 3 : Set NEWNODE ->INFO=ITEM
Step 4 : Set COUNT=0
Step 5 : Set PTR=HEAD
Step 6 : Repeat Step 7 to 9 While(COUNT!=LOC)
Step 7 : PTR1=PTR
Step 8 : PTR=PTR->NEXT
Step 9 : COUNT++
Step 9 : NEWNODE->NEXT=PTR
Step 10 : Set PTR1->NEXT= NEWNODE
Step 11 : Stop
Delete at First position in Circular Singly Linked List
Algorithm: DELETEATFIRST(INFO, HEAD, PTR, NEXT)
Step 1 : if (HEAD ==NULL) then Print UNDERFLOW and Return
Step 2 : PTR=HEAD
Step 3 : Set HEAD=HEAD->NEXT
Step 3 : Set LAST->NEXT=HEAD
Step 4 : Print PTR->INFO
Step 5 :.Stop
Delete at last position in Circular Singly Linked List
Algorithm: DELETEATLAST(INFO, HEAD, PTR, NEXT, PTR1)
Step 1 : if (HEAD==NULL) then Print UNDERFLOW and Return
Step 2 : PTR=HEAD
Step 3 : Repeat Step 4 and 5 while(PTR->NEXT!=NULL)
Step 4 : PTR1=PTR
Step 5 :. PTR=PTR->NEXT
Step 6 : PTR1->NEXT=HEAD
Step 6 : LAST=PTR1
Step 7 : Print PTR->INFO
Step 5 :.Stop
Delete at given position in Circular Singly Linked List
Algorithm: DELETEATGIVENLOCATION(INFO, HEAD, NEXT, ITEM, PTR, LOC,
COUNT, PTR1)
Step 1 : if (HEAD==NULL) then Print UNDERFLOW and Return
14 | P a g e
DATA STRUCTURE USING C++ BCA313 UNIT III
Step 2 : Set COUNT=0
Step 3 : Set PTR=HEAD
Step 4 : Repeat Step 7 to 9 While(COUNT!=LOC)
Step 5 : PTR1=PTR
Step 6 : PTR=PTR->NEXT
Step 7 : COUNT++
Step 8 : PTR1->NEXT=PTR->NEXT
Step 9 : Print PTR->INFO
Step 10 : Stop
Traverse Circular Singly Linked List
Algorithm: TRAVERSESLL(INFO, HEAD, PTR, NEXT)
Step 1 : if (HEAD ==NULL) then Print Linked List is Empty and Return
Step 2 : PTR=HEAD
Step 3 : Repeat Step 4 and 5 while(PTR->NEXT!=HEAD)
Step 4 : Print PTR->INFO
Step 5 : PTR=PTR->NEXT
Step 6 : Print PTR->INFO
Step 7 : Stop
Search in Circular Singly Linked List
Algorithm: SEARCHSLL(INFO, HEAD, PTR, NEXT, ITEM, POS, FLAG)
Step 1 : if (HEAD ==NULL) then Print Linked List is Empty and Return
Step 2 : PTR=HEAD, POS=0, FLAG=FALSE
Step 3 : Repeat Step 4 to 6 while(PTR->NEXT!=NULL)
Step 4 : POS++
Step 5 : if( PTR->INFO==ITEM)
FLAG=TRUE
Break;
Step 6 : PTR=PTR
Step 7 : if(FLAG==TRUE)
Print ITEM found at POS
Else
Print ITEM not Found
Step 8 : Stop
15 | P a g e