I B.
Tech II Semester DATA STRUCTURES R23
LINKED LIST
UNIT II
.
Introduction
A linked list is a collection of data elements called nodes in which the linear representation is given
by links from one node to the next node. A linked list does not store its elements in consecutive memory
locations and the user can add any number of elements to it.
The elements in a linked list can be accessed only in a sequential manner. But like an array, insertions and
deletions can be done at any point in the list in a constant time.
A linked list, in simple terms, is a linear collection of data elements. These data elements are called nodes.
Linked list is a data structure which in turn can be used to implement other data structures.
Thus, it acts as a building block to implement data structures such as stacks, queues, and theirvariations.
Basic Terminology:
A linked list can be perceived as a train or a sequence of nodes in which each node contains one or more
data fields and a pointer to the next node.
We can see a linked list in which every node contains two parts, an integer and a pointer to the next node.
The last node will have no next node connected to it, so it will store a special value called NULL.
Since in a linked list, every node contains a pointer to another node which is of the same type, it is also
called a self-referential data type.
Let us see how a linked list is maintained in the memory. When we traverse DATA and NEXT in this
manner, we finally see that the linked list in the above example stores characters that when put together
form the word HELLO.
Page 1
I B.Tech II Semester DATA STRUCTURES R23
Linked Lists versus Arrays:
Both arrays and linked lists are a linear collection of data elements. But unlike an array, a linked list
does not store its nodes in consecutive memory locations. Another point of difference between an array
and a linked list is that a linked list does not allow random access of data. Nodes in a linked list can be
accessed only in a sequential manner.
Another advantage of a linked list over an array is that we can add any number of elements in the list.
This is not possible in case of an array.
Memory Allocation and De-allocation for a Linked List:
If we want to add a node to an already existing linked list in the memory, we first find free space in the
memory and then use it to store the information.
Now, the question is which part of the memory is available and which part is occupied? When we delete
a node from a linked list, then who changes the status of the memory occupied by it from occupied to
available? The answer is the operating system.
The operating system scans through all the memory cells and marks those cells that are being used by
some program. Then it collects all the cells which are not being used and adds their address to the free
pool, so that these cells can be reused by other programs. This process is called garbage collection.
Single Linked Lists:
A singly linked list is the simplest type of linked list in which every node contains some data and a pointer
to the next node of the same data type.
Traversing a linked list means accessing the nodes of the list in order to perform some processing on them.
Remember a linked list always contains a pointer variable START which stores the address of thefirst
Page 2
I B.Tech II Semester DATA STRUCTURES R23
node of the list. End of the list is marked by storing NULL or –1 in the NEXT field of the last node.
Operations
Traversing a Linked List:
For traversing the linked list, we also make use of another pointer variable PTR which points to the
node that is currently being accessed. Algorithm for traversing a linked list
Searching for a Value in a Linked List:
Searching a linked list means to find a particular element in the linked list. So searching means finding
whether a given value is present in the information part of the node or not. If it is present, the algorithm
returns the address of the node that contains the value. However, if the search is unsuccessful, POS is set
to NULL which indicates that VAL is not present in the linked list.
Consider the linked list shown in below. If we have VAL = 4, then the flow of the algorithm can be
explained as shown in the figure.
Page 3
II B.Tech ISemester DATA STRUCTURES R20
Inserting a New Node in a Linked List:
we will see how a new node is added into an already existing linked list. We will take four cases and then
see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.Case
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.
Let us first discuss an important term called OVERFLOW. Overflow is a condition that occurs when
AVAIL = NULL or no free memory cell is present in the system. When this condition occurs, the program
must give an appropriate message.
Case 1: Inserting a Node at the Beginning of a Linked List
Inserting a Node at the Beginning of a Linked List. Consider the linked list shown in below figure.
Suppose we want to add a new node with data 9 and add it as the first node of the list.
Page 4
II B.Tech ISemester DATA STRUCTURES R20
Case 2: Inserting a Node at the End of a Linked List
VVIT Page 5
II B.Tech ISemester DATA STRUCTURES R20
Case 3: Inserting a Node After a Given Node in a Linked List
Consider the linked list shown in below figure. Suppose we want to add a new node with value 9 afterthe
node containing 3.
VVIT Page 6
II B.Tech ISemester DATA STRUCTURES R20
Case 4: Inserting a Node Before a Given Node in a Linked List
Consider the linked list shown in below figure. Suppose we want to add a new node with value 9
before the node containing 3.
VVIT Page 7
II B.Tech ISemester DATA STRUCTURES R20
Deleting a Node from a Linked List:
We will discuss how a node is deleted from an already existing linked list. We will consider three cases
and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
Case 1: Deleting a First Node from a Linked List
Case 2: Deleting the Last Node from a Linked List
VVIT Page 8
II B.Tech ISemester DATA STRUCTURES R20
Case 3: Deleting After a Given Node in a Linked List
Consider the linked list shown in below figure. Suppose we want to delete the node that succeeds thenode
which contains data value 4.
VVIT Page 9
II B.Tech ISemester DATA STRUCTURES R20
Reversing Single Linked list:
struct node *prevNode, *curNode; while(head != NULL)
if(head != NULL) { head = head->next;
{ prevNode = head; curNode->next = prevNode;
curNode = head->next; prevNode = curNode;
head = head->next; curNode = head;
prevNode->next = } head = prevNode;
NULL; // Make last node as head
// Make first node as last node }
2. 4 Applications on Single Linked list
✓ Implementation of stacks and queues.
✓ Implementation of graphs: Adjacency list representation of graphs is most popular which uses
linked list to store adjacent vertices.
VVIT Page 10
II B.Tech ISemester DATA STRUCTURES R20
✓ 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
Polynomial Expression Representation:
A polynomial is composed of different terms where each of them holds a coefficient and an exponent.
An essential characteristic of the polynomial is that each term in the polynomial expression consists of
two parts: one is the coefficient and other is the exponent
Example:
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential values.
Addition of two polynomials:
VVIT Page 11
II B.Tech ISemester DATA STRUCTURES R20
Multiplication of two polynomials:
Sparse Matrix Representation using Linked List:
A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n
values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.
Example: 00304
00570
00000
02600
Sparse Matrix Representation using arrays:
Method 1: Using Arrays
2D array is used to represent a sparse matrix in which there are three rows named asRow:
Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index – (row, column)
VVIT Page 12
II B.Tech ISemester DATA STRUCTURES R20
Sparse Matrix Representation using Linked List:
Method 2: Using Linked Lists
In linked list, each node has four fields. These four fields are defined as:
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index – (row, column)Next
node: Address of the next node
Advantages of Single Linked list:
• Insertions and Deletions can be done easily.
• It does not need movement of elements for insertion and deletion.
• Space is not wasted as we can get space according to our requirements.
• Its size is not fixed. It can be extended or reduced according to requirements.
• Elements may or may not be stored in consecutive memory available, even then we can store
the data in computer.
• It is less expensive.
Disadvantages of Single Linked list:
• It requires more space as pointers are also stored with information.
• Different amount of time is required to access each element.
• If we have to go to a particular element then we have to go through all those elements that
come before that element.
• We cannot traverse it from last & only from the beginning.
• It is not easy to sort the elements stored in the linear linked list.
VVIT Page 13
II B.Tech ISemester DATA STRUCTURES R20
Doubly linked list
A doubly linked list or a two-way linked list is a more complex type of linked list which contains a
pointer to the next as well as the previous node in the sequence.
Therefore, it consists of three parts—data, a pointer to the next node, and a pointer to the previous
node.
A doubly linked list provides the ease to manipulate the elements of the list as it maintains pointers to
nodes in both the directions (forward and backward).
The main advantage of using a doubly linked list is that it makes searching twice as efficient.
Let us view how a doubly linked list is maintained in the memory.
Inserting a New Node in a Doubly Linked List:
In this section, we will discuss how a new node is added into an already existing doubly linked list. We
will take four cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.Case
2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.
Case 1: Inserting a Node at the Beginning of a Doubly Linked List
VVIT Page 14
II B.Tech ISemester DATA STRUCTURES R20
Case 2: Inserting a Node at the end of a Doubly Linked List
VVIT Page 15
II B.Tech ISemester DATA STRUCTURES R20
Case 3: Inserting a Node After a Given Node in a Doubly Linked List
VVIT Page 16
II B.Tech ISemester DATA STRUCTURES R20
Case 4: Inserting a Node Before a Given Node in a Doubly Linked List
VVIT Page 17
II B.Tech ISemester DATA STRUCTURES R20
Deleting a Node from a Doubly Linked List
In this section, we will see how a node is deleted from an already existing doubly linked list. We will
take four cases and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
Case 4: The node before a given node is deleted.
Case 1: Deleting the First Node from a Doubly Linked List
Case 2: Deleting the Last Node from a Doubly Linked List
VVIT Page 18
II B.Tech ISemester DATA STRUCTURES R20
Case 3: Deleting the Node After a Given Node in a Doubly Linked List
VVIT Page 19
II B.Tech ISemester DATA STRUCTURES R20
Case 4: Deleting the Node Before a Given Node in a Doubly Linked List
VVIT Page 20
II B.Tech ISemester DATA STRUCTURES R20
Circular Linked List
In a circular linked list, the last node contains a pointer to the first node of the list. We can have acircular
singly linked list as well as a circular doubly linked list.
While traversing a circular linked list, we can begin at any node and traverse the list in any direction,
forward or backward, until we reach the same node where we started. Thus, a circular linked list hasno
beginning and no ending.
Note that there are no NULL values in the NEXT part of any of the nodes of list.
Operation:
Inserting a New Node in a Circular Linked List
In this section, we will see how a new node is added into an already existing linked list. We will take
two cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning of the circular linked list.Case
2: The new node is inserted at the end of the circular linked list.
Case 1: Inserting a Node at the Beginning of a Circular Linked List
VVIT Page 21
II B.Tech ISemester DATA STRUCTURES R20
Case 2: Inserting a Node at the End of a Circular Linked List
VVIT Page 22
II B.Tech ISemester DATA STRUCTURES R20
Deleting a Node from a Circular Linked List
In this section, we will discuss how a node is deleted from an already existing circular
linked list.
We will take two cases and then see how deletion is done in each case. Rest of the cases
of deletionare same as that given for singly linked lists.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 1: Deleting the First Node from a Circular Linked List
Page 23
II B.Tech ISemester DATA STRUCTURES R20
Case 2: Deleting the Last Node from a Circular Linked List
Page 24
