Unit-4

“Linked List”
 UNIT – 4 SYLLABUS
Linked List: Introductionof Linked Lists, Realization of
linked list using dynamic memory management,
operations, Linked List as ADT, Introduction to Static and
Dynamic Memory Allocation,
Types of Linked List: singly linked, linear and Circular
Linked Lists, Doubly Linked List, Doubly Circular Linked
List, Primitive Operations on Linked List-
Create, Traverse, Search, Insert, Delete, Sort, Concatenate.
Polynomial Manipulations-Polynomial
addition. Generalized Linked List (GLL) concept,
Representation of Polynomial using GLL.
 INTRODUCTION OF LINKED LIST
“ Linked List is a very commonly used linear data structure
which consists of group of nodes in a sequence.
Each node holds its own data and the address of the next
node hence forming a chain like structure.”
Linked Lists are used to create trees and graphs.

3
Fig: 1 Data
Organization

4
Fig: 2 (a): A linked list of nelements

Fig: 2 (b) : A linked list ofweekdays

5
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.
6
Applications of Linked Lists
1. Linked lists are used to implement stacks,
queues, graphs, etc.

Linked lists let you insertelements atthe

beginning and end of the list.

In Linked Lists we don't need to know the size in

advance. 7
 TERMINOLOGIES OF LINKED LIST
Node an item in a linked list. Each node contains a piece of list data
and the location of the next node (item).

Link (of a node) the location of the next node.

head node first node in a linked list

head pointer points to the head node.

Null pointer there is no need in it (linked list is empty)

8
DIFFERENCE BETWEEN SEQUENTIAL AND
LINKED ORGANIZATION

PROF. ANAND GHARU9

 LINKED LIST PRIMITIVE OPERATION
Basic Operations
Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Display − Displays the complete list.

Search − Searches an element using the given key.

Delete − Deletes an element using the given key.

10
 DYNAMIC MEMORY MANAGEMENT

“ Dynamic Memory Allocation means memory which can

be allocated or deallocated as per requirement at run time”

Importance of memory allocation :

no need to initially occupy large amount of memory.

Memory can be allocated or deallocated as per need.

It avoid wastage of memory.

We can free the memory by de-allocating it using free( ).11

 FUNCTION DYNAMIC
MEMORY ALLOCATION

12
COMPARE Malloc( ) AND
Calloc( ) MEMORY

Syntax: Syntax:
malloc(size) calloc(number, size)

Ex:
malloc(size of (int))
 Representation of Linked list
Realization stands for Representation of Linked List

A linked list can be represented in two ways :

1. Dynamic representation of linked list
2. Static representation of linked list

14
 Representation of Linked list
Dynamic Representation of linked list :

15
 Representation of Linked list
Static Representation of linked list :

16
 TYPES OF LINKED LIST
1. Linear/Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Doubly Circular Linked List

17
LINEAR/SINGLY LINKED LIST
“ A linked list in which every node has one link field, to
provide information about where the next node of list is, is
called as singly linked list ”

18
LINEAR/SINGLY LINKED LIST
Singly linked list is a basic linked list type. Singly
linked list is a collection of nodes linked together in a
sequential way where each node of singly linked list
contains a data field and an address field which
contains the reference of the next node. Singly linked
list can contain multiple data fields but should contain
at least single address field pointing to its connected
next node.
19
 ADVANTAGES OF SINGLY
LINKED LIST
1. Singly linked list is probably the most easiest data structure to
implement.
2. Insertion and deletion of element can be done easily.
3. Insertion and deletion of elements doesn't requires
movement of all elements when compared to an array.
4. Requires less memory when comparedto doubly,circular
or doubly
5. Can allocatecircular linked list.
or deallocate memory easily when required
during its execution.
6. It is one of mostefficient data structure to implement when
traversing in one direction is required.
20
 DISADVANTAGES OF SINGLY
LINKED LIST
1. It uses more memory when compared to an array.
2. Since elements are not stored sequentially hence
requires more time to access each elements of list.
3. Traversing in reverse is not possible in case of Singly
linked list when compared to Doubly linked list.
4. Requires O(n) time on appending a new node to end.
Which is relatively very high when compared to array or
other linked list.

21
 SINGLY LINKED LIST
OPERATION
1. Creation

2. Insertion

3. Deletion

4. Searching

5. Display

22
 C++ Program to Implement Singly Linked
List

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

/* Node Declaration */
struct node
{
int data;
struct node *next;
}node;
Operations on Linked Lists
Insert a new item
At the head of the list, or
At the tail of the list, or
Inside the list, in some designated position
Search for an item in the list
The item can be specified by position, or by some value
Delete an item from the list
Search for and locate the item, then remove the item,
and finally adjust the surrounding pointers
24

size( );
isEmpty( )
17-10-2024
FOP-DSA-Unit-III
 Insert a node

Insert– At the Head

•The link value in the new item = old head_ptr
•The new value of head_ptr = newPtr
Insert – At the Tail 25

•The link value in the new item = NULL

•The link value of the old last item = newPtr
Insert – inside the List
•The link-value in the new item = link-value of prev item
•The new link-value of prev item = newPtr
Delete a node
Delete – the Head Item
•The new value of head_ptr = link-value of the old head item
•The old head item is deleted and its memory returned
Delete – the Tail Item
rd
•New value of tail_ptr = link-value of the 3 last item
•New link-value of new last item = NULL.
Delete – an inside Item
•New link-value of the item located before the deleted one =
the link-value of the deleted item
17-10-2024 FOP-DSA-Unit-III 26
 Delete a node from singly linked list
Pseudo code: else
node *delete( node *head, char d) { {
node *p, *q; q next = p next;
q= haed; delete(p);
p= head next; }
if (q data==d) }
{ return head;
head=p; }
delete(q);
}
else
{
while (p data!=d)
{
p= p next;
q=q next;
}
if (p next==Null)
{
q next=Null;
delete(p);
}
Time of the Operations
• Time to search() is O(L) where L is the relative
location of the desired item in the List.
• In the worst case. The time is O(n).
• In the average case it is O(N/2)=O(n).
• Time for remove() is dominated by the time for search
and is thus O(n).
• Time for insert at head or at tail is O(1)(if tail pointer
is maintained).
• Time for insert at other positions is dominated by
search time and thus O(n).
• Time for size() is O(n), and time for isEmpty() is O(1)
28
size() and isEmpty()
• We need to scan the items in the list from the head_ptr to
the last item marked by its link-value being NULL
• Count the number of items in the scan, and return the
count. This is the size().
• Alternatively, keep a counter of the number of item, which
gets updated after each insert/delete. The function size( )
returns that counter
• If head_ptr is NULL, isEmpty() returns true; else, it returns
false.

29
 DOUBLY LINKED LIST
❖ In doubly linked list, each node has two link fields to
store information about who is the next and also about
who is ahead of the node
❖ Hence each node has knowledge of its successor and
also its predecessor.
❖ In doubly linked list, from every node the list can be
traversed in both the directions.

30
 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.

Link − Each link of a linked list can store a data called an element.
Next − Eachlink of a linked list contains a link to the next
link called Next.
Prev − Eachlink of a linked list contains a link to the
previous link called Prev.
LinkedList − A Linked List contains the connection link to the
first link called First and to the last link called Last. 31
 BASIC OPERATION OF DLL
Following are the basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Insert Last − Adds an element at the end of the list.

Delete Last − Deletes an element from the end of the list.

Insert After − Adds an element after an item of the list.

Delete − Deletes an element from the list using the key.

Display forward − Displays the complete list in a forward manner.

Display backward − Displays the complete list in a backward manner.

27
 ADVANTAGES OF DOUBLY
LINKED
)A DLL can be traversed in both forwardLIST
and backward
direction.
)The delete operation in DLL is more efficient if pointer to the
node to be deleted is given.

3) We can quickly insert a new node before a given node.

In singly linked list, to delete a node, pointer to the previous node
is needed. To get this previous node, sometimes the list is
traversed. In DLL, we can get the previous node using previous
pointer.
33
 DISADVANTAGES OF DOUBLY
LINKED LIST
)Every node of DLL Require extra space for an previous pointer. It
is possible to implement DLL with single pointer though

)All operations require an extra pointer previous to be maintained.

For example, in insertion, we need to modify previous pointers
together with next pointers. For example in following functions for
insertions at different positions, we need 1 or 2 extra steps to set
previous pointer.

34
SINGLY CIRCULAR LINKED LIST
“Circular Linked List is a variation of Linked list in which
the first element points to the last element and the last
element points to the first element. Both Singly Linked List
and Doubly Linked List can be made into a circular linked
list”.

35
 CIRCULAR LINKED LIST
Circular linked list are mostly used in task
maintenance in operating systems. There are many
examples where circular linked list are being used in
computer science including browser surfing where a
record of pages visited in the past by the user, is
maintained in the form of circular linked lists and can
be accessed again on clicking the previous button.

36
 BASIC OPERATION OF CLL
Following are the important operations supported by a circular list.
insert − Inserts an element at the start of the list.

delete − Deletes an element from the start of the list.

display − Displays the list.

37
 ADVANTAGES OF CIRCULAR
LINKED LIST
1. Some problems are circular and a circular data structure would be

more natural when used to represent it.

2. The entire list can be traversed starting from any node (traverse means

visit every node just once)

3. fewer special cases when coding(all nodes have a node before and after

it)

38
 DISADVANTAGES OF
CIRCULAR LINKED LIST
1. Circular list are complex as compared to singly linked
lists.

2. Reversing of circular list is a complex as compared

to singly or doubly lists.

3. If not traversed carefully, then we could end up in an

infinite loop.

39
DOUBLY CIRCULAR LINKED LIST
“Circular Doubly Linked List has properties of both doubly linked
list and circular linked list in which two consecutive elements are
linked or connected by previous and next pointer and the last node
points to first node by next pointer and also the first node points to
last node by previous pointer”.

40
BASIC OPERATION OF
DOUBLY CIRCULAR LL

41
 ADVANTAGES OF CIRCULAR
LINKED LIST
1. List can be traversed from both the directions i.e. from head to

tail or from tail to head.

2. Jumping from head to tail or from tail to head is done in

constant time O(1).

3. Circular Doubly Linked Lists are used for implementation of

advanced data structures like Fibonacci Heap.

42
 DISADVANTAGES OF
CIRCULAR LINKED LIST
1. It takes slightly extra memory in each node to
accommodate previous pointer.

2. Lots of pointers involved while implementing or doing

operations on a list. So, pointers should be handled
carefully otherwise data of the list may get lost.
Applications of Circular doubly linked list
Managing songs playlist in media player applications.
Managing shopping cart in online shopping
43
44
 Primitive operations on linked list
1. Create
2. Insert
3. Delete
4. Search
5. Traverse
6. Concatenate
7. Count
8. Reverse

45
#include <iostream>
public:
#include <string.h>
dnode()
using namespace std;
{
class SLL;
next = NULL;
class dnode
div = prn = 0;
{
}
int div;
dnode(int d, int p, char Name[])
int prn;
{
char name[20];
div = d;
dnode *next;
prn = p;
next = NULL;
friend SLL;
strcpy(name, Name);
}
};
46
class SLL
{ SLL()
public: {
dnode *head; head = NULL;
dnode *insert; insert = NULL;
dnode *end; end = NULL;
void create(); }
void print(); } list1;
void insertMember();
void deleteMember();
void count();
void mergeList();
void recursionPrint(dnode *temp);

47
void SLL::create()
{ head = new dnode(d, p, Name);
int n, d, p; end = head;
char Name[20];
cout << "\nEnter the name, division
cout << "Enter the number of students: "; and PRN of members: \n";
cin >> n; for (int i = 1; i < n - 1; i++)
{
cout << "\nEnter the name, division and cin >> Name >> d >> p;
PRN of President: \n"; end->next = new dnode(d, p,
cin >> Name >> d >> p; Name);
end = end->next;
}
insert = end;
48
cout << "\nEnter the name, division and PRN of
void SLL::deleteMember()
SECRETARY: \n";
cin >> Name >> d >> p;
{

end->next = new dnode(d, p, Name); int searchPRN;

end = end->next; dnode *remove;
end->next = NULL; cout << "Enter the PRN of
}
member to delete: ";
void SLL::insertMember()
cin >> searchPRN;
{
if (searchPRN == head->prn)
int d, p;
char Name[20]; {
cout << "\nEnter the name, division and PRN of remove = head;
member to INSERT: \n"; head = head->next;
cin >> Name >> d >> p;
delete remove;
insert->next = new dnode(d, p, Name);
}
insert = insert->next;
insert->next = end; 49
 else
{ if (searchPRN == end->prn)
for (dnode *temp = head; temp != {
insert; temp = temp->next) remove = end;
{ insert->next = NULL;
if(temp->next->prn == searchPRN) end = insert;
{ delete remove;
if (temp->next == insert) }
insert = temp; }
remove = temp->next;
temp->next = temp->next->next; void SLL::count()
delete remove; {
int count = 0;
if (temp == insert) for (dnode *temp = head; temp
break; != NULL; temp = temp->next)
} count++;
} cout << "\nTotal no. of students :
} " << count;
}

50
void SLL::print()
{
cout << "\n\nNAME\tDIV\tPRN\n";
for (dnode *temp = head; temp != NULL; temp = temp->next)
cout << temp->name << "\t" << temp->div << "\t" << temp->prn << "\n";
cout << "\nPresident is: " << head->name;
cout << "\nSecretary is: " << end->name << "\n";
}

51
void SLL::mergeList() void SLL::recursionPrint(dnode *temp)
{ {
SLL list2; if (temp == NULL)
cout << "\nEnter the contents for second return;
list: \n"; else
list2.create(); recursionPrint(temp->next);
list1.end->next = list2.head; cout << temp->name << "\t" << temp->div
list1.end = list2.end; << "\t" << temp->prn << "\n";
} }
int main()
{
int choice;
do
{
cout << "\n1. Create List. \n2. Insert Member \n3. Delete Member \n4. Print List \n5. Merge List
\n6. Reverse List \n7. Count \n8. Exit";
cout << "\n\nEnter your choice: ";
cin >> choice;
switch (choice)
{
case 1: list1.create();
break;
case 2:list1.insertMember();
break;
case 3: list1.deleteMember();
break; 53
case 4: list1.print();
break;
case 5: list1.mergeList();
break;
case 6:cout << "\n\nNAME\tDIV\tPRN\n";
list1.recursionPrint(list1.head);
break;
case 7: list1.count();
break;
case 8: return 0;
default: cout << "Invalid Choice !";
break;
}
} while (choice != 0);
return 0;
}
 POLYNOMIAL
MANIPULATIONS

❖A node will have 3 fields, which represent the coefficient and

exponent of a term and a pointer to the next term

55
POLYNOMIAL MANIPULATIONS
❖ E.x. For instance, the polynomial, say A = 6x7 + 3x5 + 4x3 +
12 would be stored as :

56
Operation on Polynomial
❖ Polynomial evaluation
❖ Polynomial addition
❖ Multiplication of two polynomials sparse
of matrix using Representation linked
list
❖ Linked list implementation of the stack
❖ Generalized linked list

57
ADDITION OF
POLYNOMIAL

58
MULTIPLICATION OF
POLYNOMIAL

59
 GENERALIZED LINKED LIST
• “A generalized list, A, is a finite sequence of n >= 0 elements,
a1, a2, a3, …an, such that ai are either atoms or list of atoms.
Thus A=(a1, a2, a3, …an) n is total no. of nodes

are 1 in n, which are not atoms are said to be the sublists

of A.”

60
GENERALIZED LINKED LIST

61
GENERALIZED LINKED LIST

62
GENERALIZED LINKED LIST

63
Representation of Polynomial using GLL

65
GARBAGE COLLECTION
garbage collection is the process of collecting all unused nodes
and returning them to available space.

This process is carried out in essentially two phases. In the first

phase, known as the marking phase, all nodes in use are marked.
In the second phase all unmarked nodes are returned to the
available space list.

In this case, the second phase requires only the examination of

each node to see whether or not it has been marked.

67
GARBAGE COLLECTION
If there aretotal of n nodes, then the second phase of garbage

collection can be carried out in O(n) steps.

In this situation it is only the first or marking phase that is of any

interest in designing an algorithm. When variable size nodes are in use,

it is desirable to compact memory so that all free nodes form a

contiguous block of memory.

The garbage collection algorithm works in two steps:

1) Mark

2) Sweep

68
ADVANTAGES OF GARBAGE
COLLECTION

69
DISADVANTAGES OF
GARBAGE
COLLECTION

70
THANK YOU !!!!!

52
52