Data Structures and Algorithms
Lecture Slides for
in C and Python
Chapter 5
Linked List
1
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
2 Chapter Outcomes
After going through this chapter learners will be able
to understand the importance of linked list.
to compare array and linked list.
to implement the abstract data type using the nodes as a linked list.
to understand and implement the algorithms of singly, circular and doubly linked
lists for inserting, deleting, searching and reversing, etc.
to understand the concepts of dangling pointers, garbage collection, and de-
referencing the NULL pointer.
to implement the inserting, deleting, and reversing linked list along with the
implementation of the sparse matrix and polynomial addition with C and Python.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
3 Content
5.1 Introduction
5.2 Classification of Linked Lists
5.3 Operations on Singly Linked List
5.4 Operations on Circular Linked List
5.5 Operations on Doubly Linked List
5.6 Traversing in Linked List
5.7 Memory Allocation and Garbage Collection
5.8 Sparse Matrix Representation Using Array and Linked List
5.9 Polynomials Representation Using Linked List
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
5.1 Introduction
4
The data structure linked list has the power to overcome the limitations of
the array data structure. Though both are used to store linear data of
similar types, their memory allocation mechanisms differ. Memory
allocation of linked list takes place during runtime or program executions
when data is added to it in contrast to an array memory location that
occurs at an array declaration. This is why a linked list is called a dynamic
data structure.
Definition
A linear collection of data elements (nodes) stored at non-contiguous
memory locations is called a linked list. Physical placements of
elements in the memory do not take place sequentially or in order here.
The linked list consists of multiple nodes that contain a data field and
an address field (or link) to the next node in the list.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
5 5.2 Classification of Linked Lists
5.2.1 Singly Linked List
A singly linked list is a concrete data structure consisting of a sequence of nodes. It
has a head or start node pointer indicating the first node in the list. It also has a null
pointer reference necessarily at the last node, and that null pointer reference
indicates the last node of the list. Each node stores an element (data) and a link to
the next node as usual.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
6
5.2.2 Circular Linked List
In a singly linked list, each node points to its next node in the
sequence, and the last node points to the null reference. In the
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. Hence, the circular
linked list is similar to the singly linked list except that the last node
points to the first node in the list
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
7 5.2.3 Doubly Linked List
In a singly linked list, every node has a link to its next node in the sequence.
So, we can traverse from one node to another node only in one direction
and we cannot traverse back. We can solve this kind of problem by using
a doubly linked list. Doubly or two-way linked list is a sequence of elements
in which every node has a data part, and two link parts to its previous
element and next element in the sequence. We can traverse forward
using the next address field and traverse backward using the previous
address field. This linked list is also known as a two-way linked list since each
node is linked in two ways. So, each node of the doubly linked list contains
three fields – a data field, and two address fields. Here, the ‘Prev’ field is
used to store the address of the previous node of the linked list, ‘Next’ field
is used to store the address of the next node of the linked list, and ‘Data’
field is used to store the actual value of that node. Elements can be
navigated forward and backward
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
8 5.3 Operations on Singly Linked List
5.3.1 Inserting Node in Singly Linked List
1. Algorithm for inserting a node at the beginning of the singly linked list
❑ Step 1: Create a Newnode with a specific value.
❑ Step 2: Check whether linked list is empty [if (head = = NULL)].
❑ Step 3: If the linked list is empty then, set Newnode → next = NULL and head =
Newnode.
❑ Step 4: If it is not empty then, set Newnode → next = head and head =
Newnode.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
9 Algo for inserting a node at the end of the linked list
Step 1: Create a Newnode with a specific value and Newnode → next as
NULL.
Step 2: Check whether list is empty [if (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 one by one until it reaches the
last node of the list (until temp → next is equal to NULL).
Step 6: Set temp → next = Newnode.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
Algo for inserting a node at a specific location of the linked list
10
Step 1: Create a Newnode with a specific 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 one by one until it reaches the node
after which we want to insert the Newnode (until temp → 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 has reached to the last node or not. If it has
reached the last node then print ‘Node is not found in the list and insertion is not
possible’ and terminate the function. Otherwise, move the temp to the next node.
Step 7: Lastly, ‘Newnode → next = temp → next’ and ‘temp → next = Newnode
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
11 5.3.2 Deleting Node from Singly Linked List
1. Algorithm for deleting a node from the beginning of the singly linked list
Step 1: Check whether list is empty (head = = NULL)
Step 2: If it is empty, then display ‘Linked List is empty and deletion is not possible’ and
exit.
Step 3: If it is not empty, then define a node pointer ‘temp’ and initialize with head.
Step 4: Check whether the list is having only one node (temp → next = NULL)
Step 5: If the condition is TRUE, then set head = NULL and delete temp (Setting empty list
conditions)
Step 6: If the condition is FALSE, then set head = temp → next, and delete temp.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
12 Algo for deleting a node from the end of the singly linked list
Step 1: Check whether list is empty (head = = NULL)
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’ and exit.
Step 3: If it is not empty, then define two node pointers ‘temp1’ and ‘temp2’ and
initialize ‘temp1’ with head.
Step 4: Check whether the list has only one node (temp1 → next == NULL)
Step 5: If the condition is TRUE, then set head = NULL and delete temp1 and terminate
the function. (Setting empty list condition)
Step 6: If the condition is FALSE, then set ‘temp2 = temp1 ‘ and move temp1 to its next
node. Repeat the same process until it reaches the last node in the list. (until temp1 →
next = = NULL)
Step 7: Lastly, Set temp2 → next = NULL and delete temp1.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
Algo for deleting a node from a specific location of the linked list
13 Step 1: Check whether list is empty (head == NULL)
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’ and exit.
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 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 reaches the last node, then print ‘target node is not found in the list and deletion is not possible’
and exit.
Step 6: If it reaches the target node which we want to delete, then check whether the list is having only one
node or not.
Step 7: If the 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 the 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 the first node, then check whether it is the last node in the list (temp1 → next = = NULL).
Step 11: If temp1 is the last node, then set temp2 → next = NULL and delete temp1 (free(temp1)).
Step 12: If temp1 is not the first node and not the last node, then set temp2 → next = temp1 → next and
delete temp1 (free(temp1)).
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
14 5.3.3 Reversing Singly Linked List
Pseudocode for reversing a singly linked list
BEGIN Procedure:
prev = NULL; current = head; save= NULL
WHILE(current != NULL)
save = current → next
current → next = prev
prev = current
current = save
END WHILE
head = prev;
END Procedure
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
15 5.4 Operations on Circular Linked List
5.4.1 Inserting Node in Circular Linked List
1. Algorithm for inserting a node at the beginning of the circular linked list
❑ Step 1: Create a Newnode with a specific value.
❑ Step 2: Check whether list is empty (head = = NULL) or not.
❑ 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 the last
node (until ‘temp → next == head’).
❑ Step 6: Set ‘Newnode → next = head’, ‘head = Newnode’ and ‘temp →
next = head’.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
16 Algo for inserting a node at end of the circular linked list
Step 1: Create a Newnode with a specific value.
Step 2: Check whether the list is empty (head == NULL) or not.
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 the last
node in the list (until temp → next == head).
Step 6: Set temp → next = Newnode and Newnode → next = head.
temp next = newnode se newnode at end then newnode next points to head to complete circle
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
17 Algo for inserting a node at a specific location in the circular linked list
Step 1: Create a Newnode with a given value.
Step 2: Check whether the list is empty (head = = NULL) or not.
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 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 the last node, then display ‘target node is not found and insertion is
not possible!!!’ and exit; otherwise move the temp to the next node.
Step 7: If the temp is reached to the exact node after which we want to insert the
Newnode then check whether it is the last node (temp → next == head).
Step 8: If the temp is the last node then set temp → next = Newnode and
Newnode → next = head.
Step 9: If the temp is not the last node then set Newnode → next = temp → next
and temp → next = Newnode.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
18 5.4.2 Deleting Node from Circular Linked List
Algorithm for deleting a node from the beginning of the circular linked list
Step 1: Check whether the list is empty (head == NULL).
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’
and exit.
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 the list is having only one node (temp1 → next ==
head) or not.
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 the last node. (until temp1
→ next = head).
Step 7: Then set head = temp2 → next, temp1 → next = head and delete
temp2
temp 2 is currently the head acc to step 3, we make the second node the head.... temp1--> next = head points to the new head and then we
delete temp 2
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
19 Algo for deleting the end node of the circular linked list
Step 1: Check whether the list is empty (head = = NULL).
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’
and exit.
Step 3: If it is not empty, then define two node pointers ‘temp1’ and ‘temp2’
and initialize temp1’ with head.
Step 4: Check whether the list has only one Node (temp1 → next = = head) or
not.
Step 5: If it is TRUE, then set head = NULL and delete temp1 and exit. (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 the last node in the list. (Until
temp1 → next = head).
Step 7: Set temp2 → next = head and delete temp1
in step 7 we tell temp 2 to stop pointing ahead of it to temp 1 but instead point to the head directly and we delete temp 1
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
Algo for deleting a node from the specific location in the circular linked list
20 Step 1: Check whether list is empty (head == NULL) or not
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’ and exit.
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 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 reaches to the last node, then display ‘Target node not found in the list and
deletion is not possible!!!’ and exit.
Step 6: If it reaches to the exact node which we want to delete, then check whether the list
has only one node (temp1 → next = = head) or not.
Step 7: If the 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 the 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 the last node. Then set head = head → next, temp2 → next = head,
and delete temp1.
Step 10: If temp1 is not the first node, then check whether it is the last node in the list (temp1 →
next = head).
Step 11: If temp1 is last node, then set temp2 → next = head and delete temp1 (free(temp1)).
Step 12: If temp1 is not the first node and not the last node, then set temp2 → next = temp1 →
next and delete temp1 (free(temp1)).
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
5.5 Operations on Doubly Linked List
21
5.5.1 Inserting Node in Doubly Linked List
1. Algorithm for inserting a node at the beginning of the doubly linked list
▪ Step 1 Create a Newnode with a specific value and Newnode → previous
as NULL.
▪ Step 2 Check whether list is empty (head = = NULL) or not.
▪ 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
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
22 Algo for inserting a node at end of the doubly linked list
Step 1: Create a Newnode with the given value and Newnode →
next as NULL.
Step 2: Check whether the list is empty (head == NULL) or not.
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 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
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
23 Algo for inserting a node at a specific location of the
doubly linked list
Step 1: Create a Newnode with the given value.
Step 2: Check whether list is empty (head == NULL) or not.
Step 3: If it is empty, then assign NULL to both Newnode → Previous and Newnode →
next and set Newnode to head.
Step 4: If it is not empty, then define two node pointers temp1 and temp2 and initialize
temp1 with head.
Step 5: Keep moving the temp1 to its next node until it reaches 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 is not
possible!!!’ and terminate the function. Otherwise, move the temp1 to the 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.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
24 5.4.2 Deleting Node from Doubly Linked List
Algorithm for deleting a node from the beginning of the doubly linked list
Step 1: Check whether the list is empty (head = = NULL) or not.
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’ and exit.
Step 3: If it is not empty, then define a node pointer ‘temp’ and initialize with head.
Step 4: Check whether the list has only one node (temp → Previous is equal to temp
→ next) or not.
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
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
25 Algo for deleting the end node of the doubly linked list
Step 1: Check whether list is empty (head = = NULL) or not.
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’
and exit.
Step 3: If it is not empty, then define a node pointer ‘temp’ and initialize with
head.
Step 4: Check whether the list has only one node (temp → previous and temp
→ next both are NULL) or not.
Step 5: If it is TRUE, then assign NULL to head and delete temp and exit.
(Setting empty list condition).
Step 6: If it is FALSE, then keep moving temp until it reaches the last node in
the list. (Until temp → next is equal to NULL).
Step 7: Assign NULL to temp → previous → next and delete temp.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
Algo for deleting a node from a specific location in the
26 circular linked list
Step 1: Check whether list is empty (head == NULL) or not.
Step 2: If it is empty, then display ‘List is empty and deletion is not possible’ and exit.
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 the exact node to be deleted or to the last node.
Step 5: If it is reached to the last node, then the display ‘target node is not found in the list and
deletion is not possible’ and exit.
Step 6: If it is reached to the exact node which we want to delete, then check whether the list
has only one node or not.
Step 7: If the 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 the 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) or not.
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
the temp of next (temp → previous → next = temp → next), the temp of next of previous to the
temp of previous (temp → next → previous = temp → previous) and delete temp (free(temp)).
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
27
5.6 Traversing in Linked List
Pseudocode for traversing (visiting all nodes) a linked list
Traversing Procedure:
BEGIN
Node ptr; ptr = head; /* Start visiting from the first node */
WHILE(ptr has not reached the end of the list) /* Write or read or modify or display or
search variables inside currently "visiting" ptr */
ptr = ptr -> next; /* ptr will point to the next node ptr */
END WHILE
END Procedure
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
28 5.7 Memory Allocation and Garbage Collection
During program execution, the computer memory is used for storage of
variables, functions, and objects. Programmers often forget to take care of the
memory locations being used.
Garbage collection is a very important task of an operating system.
Garbage collection may take place in two steps. First, the operating system
scans through the memory and tags those cells which are currently being used
by some other programs. Then in the second phase, the operating system scans
the memory again to collect all untagged cells in a free pool or availability stack.
These garbage collection processes remain invisible to the programmers.
Garbage collection is a crucial issue in software development, since it keeps
programs from using too much RAM. Besides helping programs run more
efficiently, it can also prevent serious bugs, such as memory leaks, that can
cause a program to crash.
Garbage Collection (GC) is an automatic memory management process that identifies and reclaimed memory that is no longer being used by
the program. It prevents the "Memory Leaks" where a program forgets to release memory it no longer needs.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
29 5.8 Sparse Matrix Representation Using Array and Linked List
A sparse matrix is a matrix that contains very few non-zero elements.
Approximately two-third elements of the matrix are zeros.
When a sparse matrix is represented with a 2-dimensional array, we waste a lot
of space to represent that matrix. For example, consider a matrix of size 100 ×
100 containing 10000 elements in the matrix. A maximum of 3000 non-zero
elements is there approximately if it is a sparse matrix.
Suppose, in this matrix, only 10 elements are non-zero values, and the remaining
spaces of the matrix are filled with zero. That means, totally we allocate 100 ×
100 × 2 = 20000 bytes of space to store this integer matrix assuming that integers
take 2 bytes each. To access these 10 non-zero elements, we have to scan
10000 times. To make it simple, we use the sparse matrix representation.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
Array Representation
30
We consider only non-zero values along with their row and column index values. In
this representation, the 0-th row stores the total number of rows, the total number of
columns, and the total number of non-zero values in the sparse matrix.
Row: Index of the row, where the non-zero element is located
Column: Index of the column, where the non-zero element is located
Value: Value of the non-zero element located at that index – (row, column). For
example, consider a matrix of size 4 × 5 containing 6 numbers of non-zero values
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
Linked List Representation
31
The linked list data structure can also be used to represent a sparse matrix. Two
different nodes, namely header node and element node, are used in this linked list
representation
In the linked list, each node has five fields. These five fields are defined as:
1. Row: Index of the row, where the non-zero element is located.
2. Column: Index of the column, where the non-zero element is located.
3. Value: Value of the non-zero element located at index – (row, column).
4. Down/up node: Address of the next node of that column.
5. Right: Address of the next node of that row.
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
32 Sparse matrix can be represented using linked representation
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
5.9 Polynomials Representation Using Linked List
33
A polynomial expression can be represented efficiently using a linked list. A node
in the polynomial expression consists of two parts – the coefficient and the
exponent.
Consider the polynomial is 4x7 + 12x2 – 15. This can be represented using a linked
list as shown below:
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
34
END
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python