LINKED LIST

Introduction
A linked list is a linear data structure, in which the
elements are not stored at contiguous memory locations.
The elements in a linked list are linked using pointers as
shown in the below image.
Linked List can be defined as collection of objects
called nodes that are randomly stored in the memory.
Each node holds its own data and the address of the next
node hence forming a chain like structure.
Advantages of Linked Lists
They are a dynamic in nature which allocates the memory
when required.
The list is not required to be contiguously present in the
memory. The node can reside any where in the memory
and linked together to make a list. This achieves optimized
utilization of space.
List size is limited to the memory size and doesn't need to
be declared in advance.
Insertion and deletion operations can be easily
implemented.
Stacks and queues can be easily implemented.
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.
Not cache friendly. Since array elements are contiguous
locations, there is locality of reference which is not there in
case of linked lists.
Reverse Traversing is difficult in linked list.
Applications of Linked Lists
Linked lists are used to implement stacks, queues, graphs,
etc.
Polynomial representation
Representation of sparse matrices
Symbol table creation
Mailing list
Memory management
Linked lists let you insert elements at the beginning and
end of the list.
In Linked Lists we don't need to know the size in advance.
Basic Operations
Following are the basic operations supported by a list.
Insertion − Adds an element in the list.
Deletion − Deletes an element from the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.

https://visualgo.net/en/list?slide=1
Representation of Linked List
There are two ways to implement a linked list.
Static implementation (Using Array)
Dynamic implantation (Linked list)
Linked List Implementation using Array
Linked List Implementation using Dynamic
memory allocation
A linked list is a collection of nodes. Each node consists of
two part.
Data
Address of next node in the list
The Head will store the address of first node in the list.
Types of Linked Lists
There are 3 different implementations of Linked List
available, they are:
Singly Linked List
Doubly Linked List
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.
A singly linked list is formed when many such nodes are
linked together to form a chain. Each node points to the
next node present in the order. The first node is always used
as a reference to traverse the list and is called HEAD. The
last node points to NULL.
Declaring a Linked list
In C language, a linked list can be implemented using structure and
pointers.
struct LinkedList
{
int data;
struct LinkedList *next;
};
 The above definition is used to create every node in the list. The
data field stores the element and the next is a pointer to store the
address of the next node.
 Noticed something unusual with next?
 In place of a data type, struct LinkedList is written before next.
That's because its a self-referencing pointer. It means a pointer
that points to whatever it is a part of. Here next is a part of a node
and it will point to the next node.
Inserting a node in singly linked list
A node can be added in three ways
1) At the front (beginning) of the linked list
2) After a given node.
3) At the end of the linked list.
Insertion at the beginning of the
list
 In the first case, we make a new node and points its next
to the head of the existing list and then change the head to
the newly added node. It is similar to picture given below.
 Time complexity of this algorithm is O(1) as it does
constant amount of work.
Insertion of a node after a given
node
 Time complexity of this algorithm is O(n) as n can be any
position.
Insertion at the end of the linked list
 Time complexity of this algorithm is O(n) where n is the
number of nodes in linked list. Since there is a loop from
head to end, the function does O(n) work.
This method can also be optimized to work in O(1) by
keeping an extra pointer to tail (end) of the linked list.
ISRO CS 2014
Consider a single linked list where F and L are pointers to
the first and last elements respectively of the linked list.
The time for performing which of the given operations
depends on the length of the linked list?

 Delete the first element of the list

 Interchange the first two elements of the list
 Delete the last element of the list
 Add an element at the end of the list
GATE CS 2020
What is the worst case time complexity of inserting n
elements into an empty linked list, if the linked list needs
to be maintained in sorted order?
Θ(n)
Θ(n log n)
Θ(n2)
Θ(1)
Deleting a node from the singly linked list
A node can be deleted in three ways from a singly linked
list:
1) From the front (beginning) of the linked list
2) After a given node.
3) From the end of the linked list.
Deleting the first node of the linked list
 Time complexity of this algorithm is O(1) as it does
constant amount of work.
Deleting the nth node of the linked list
 To delete a node from linked list, we need to do following
steps.
1) Find previous node of the node to be deleted.
2) Change the next of previous node.
3) Free memory for the node to be deleted.
 Time complexity of this algorithm is O(n) where n is the
number of nodes in linked list. Since there is a loop from
head to end, the function does O(n) work.
Deleting the last node of the linked
list
 Time complexity of this algorithm is O(n) where n is the
number of nodes in linked list. Since there is a loop from
head to end, the function does O(n) work.
Traversing the singly linked list
1. Create a temporary variable for traversing. Assign reference
of head node to it, say temp = head.
2. Repeat below step till temp!= NULL.
3. temp->data contains the current node data. You can print it or
can perform some calculation on it.
4. Once done, move to next node using temp = temp->next;.
5. Go back to 2nd step.
Time complexity of this algorithm is O(n) where n is the
number of nodes in linked list. Since there is a loop from head
to end, the function does O(n) work.
GATE-IT-2004
What does the following function do for a given Linked List
with first node as head?
void fun1(struct node* head) {
if(head == NULL) return;
fun1(head->next);
printf("%d ", head->data);
}
Prints all nodes of linked lists
Prints all nodes of linked list in reverse order
Prints alternate nodes of Linked List
Prints alternate nodes in reverse order
Searches an element using the given
key
Search an element in linked list is fairly similar to how you search an element in
arrays. Here we will learn to perform linear search on singly linked list.
1. Input element to search from user. Store it in some variable say
keyToSearch.
2. Declare two variable one to store index of found element and other to
iterate through list. Say index = 0; and struct node *curNode = head;
3. If curNode is not NULL and its data is not equal to keyToSearch. Then,
increment index and move curNode to its next node.
4. Repeat step 3 till curNode != NULL and element is not found, otherwise
move to 5th step.
5. If curNode is not NULL, then element is found hence return index
otherwise -1.
 Time complexity of this algorithm is O(n) where n is the number of nodes in
linked list. Since there is a loop from head to end, the function does O(n)
work.
GATE CS 2020
Let P be a singly linked list. Let Q be the pointer to an
intermediate node x in the list. What is the worst-case time
complexity of the best known algorithm to delete the node
Q from the list?
O(n)
O(log2 n)
O(logn)
O(1)

Fast solution is to copy the data from the next node to the node
to be deleted and delete the next node.
UGC NET CS 2016 Aug – II
Consider an implementation of unsorted single linked list.
Suppose it has its representation with a head and a tail
pointer (i.e. pointers to the first and last nodes of the
linked list). Given the representation, which of the
following operation can not be implemented in O(1)
time ?

Insertion at the front of the linked list.

Insertion at the end of the linked list.
Deletion of the front node of the linked list.
Deletion of the last node of the linked list.
Doubly Linked List
Doubly linked list is a type of linked list in which each node
apart from storing its data has two links. The first link
points to the previous node in the list and the second link
points to the next node in the list. The first node of the list
has its previous link pointing to NULL similarly the last
node of the list has its next node pointing to NULL.
XOR List Representation
 A memory-efficient version of Doubly Linked List that can be created
using only one space for the address field with every node.
 The List uses bitwise XOR operation to save space for one address. In the
XOR linked list, instead of storing actual memory addresses, every node
stores the XOR of addresses of previous and next nodes.

 Node A: npx = 0 XOR add(B) //bitwise XOR of zero and address of B

 Node B: npx = add(A) XOR add(C) // bitwise XOR of address of A and address of
C
 Node C: npx = add(B) XOR add(D) // bitwise XOR of address of B and address of
D
 Node D: npx = add(C) XOR 0 // bitwise XOR of address of C and 0
 next = XOR(prev, curr -> npx);
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.
 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
Advantages over singly linked list
1) A DLL can be traversed in both forward and backward
direction.
2) 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.
Disadvantages over singly linked
list
1) Every node of DLL Require extra space for an previous
pointer. It is possible to implement DLL with single pointer
though.
2) 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.
Add a node at the front
Algorithm
Step 1 - Create a newNode with given value and newNode → prev 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 the end of the list
Algorithm
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.
ISRO CS 2017 - May
In a doubly linked list, the number of pointers affected for
an insertion operation will be:
4
0
2
1

ISRO CS 2008
Which of the following operations is performed more efficiently
by doubly linked list than by linear linked list?
 Deleting a node whose location is given
 Searching an unsorted list for a given item
 Inserting a node after the node with a given location
 Traversing the list to process each node
Deletion Operations in Doubly Linked
List
In a double linked list, the deletion operation can be
performed in three ways as follows...
Deleting from Beginning of the list
Deleting from End of the list
Deleting a Specific Node
Deletion 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 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.
Deletion 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.
Displaying a Double Linked List
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty, then display 'List is Empty!!!' and
terminate the function.
Step 3 - If it is not Empty, then define a Node
pointer 'temp' and initialize with head.
Step 4 - Display 'NULL <--- '.
Step 5 - Keep displaying temp → data with an arrow
(<===>) until temp reaches to the last node
Step 6 - Finally, display temp → data with arrow pointing
to NULL (temp → data ---> NULL).
ISRO CS 2018
A doubly linked list is declared as
struct Node {
int Value;
struct Node *Fwd;
struct Node *Bwd;
};
Which of the following segments of code deletes the node
pointed to by X from the doubly linked list, if it is assumed
that X points to neither the first nor the last node of the list?
X->Bwd->Fwd = X->Fwd; X->Fwd->Bwd = X->Bwd ;
X->Bwd.Fwd = X->Fwd ; X.Fwd->Bwd = X->Bwd ;
X.Bwd->Fwd = X.Bwd ; X->Fwd.Bwd = X.Bwd ;
X->Bwd->Fwd = X->Bwd ; X->Fwd->Bwd = X->Fwd;
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.
 That means circular linked list is similar to the single linked
list except that the last node points to the first node in the
list.
Advantages of Circular Linked Lists
1) Any node can be a starting point. We can traverse the whole list
by starting from any point. We just need to stop when the first
visited node is visited again.
2) Useful for implementation of queue. Unlike this implementation,
we don’t need to maintain two pointers for front and rear if we
use circular linked list. We can maintain a pointer to the last
inserted node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around
the list. For example, when multiple applications are running on a
PC, it is common for the operating system to put the running
applications on a list and then to cycle through them, giving each
of them a slice of time to execute, and then making them wait
while the CPU is given to another application. It is convenient for
the operating system to use a circular list so that when it reaches
the end of the list it can cycle around to the front of the list.
Operations
In a circular linked list, we perform the following
operations...
Insertion
Deletion
Display
Insertion

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 = 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
(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
Deletion Operations
In a circular linked list, the deletion operation can be
performed in three ways those 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
Displaying a circular Linked List
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty, then display 'List is Empty!!!' and
terminate the function.
Step 3 - If it is Not Empty then, define a Node
pointer 'temp' and initialize with head.
Step 4 - Keep displaying temp → data with an arrow (--->)
until temp reaches to the last node
Step 5 - Finally display temp → data with arrow pointing
to head → data.
GATE 2004
A circularly linked list is used to represent a Queue. A
single variable p is used to access the Queue. To which
node should p point such that both the operations enQueue
and deQueue can be performed in constant time?

rear node
front node
not possible with a single pointer
node next to front
Polynomial Representation
A polynomial p(x) is the expression in variable x which is
in the form (axn + bxn-1 + …. + jx+ k), where a, b, c …., k
fall in the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.An
essential characteristic of the polynomial is that each term
in the polynomial expression consists of two parts:
Coefficient
Exponent
Representation of Polynomial
Polynomial can be represented in the various ways.
These are:
By the use of arrays
By the use of Linked List
Representation of Polynomial Using
Arrays
Addition of Two Polynomial
For adding two polynomials using arrays is straightforward
method, since both the arrays may be added up element wise
beginning from 0 to n-1, resulting in addition of two
polynomials.
Addition of two polynomials using linked list requires
comparing the exponents, and wherever the exponents are
found to be same, the coefficients are added up.
For terms with different exponents, the complete term is
simply added to the result thereby making it a part of
addition result.
Multiplication of Two Polynomial
Multiplication of two polynomials however requires
manipulation of each node such that the exponents are
added up and the coefficients are multiplied.
 After each term of first polynomial is operated upon with
each term of the second polynomial, then the result has to
be added up by comparing the exponents and adding the
coefficients for similar exponents and including terms as
such with dissimilar exponents in the result.
Representation of Polynomial Using
Linked List
To understand this concept better let's first brush up all the basic
contents that are required.
 linked list is a data structure that stores each element as an object in
a node of the list. every note contains two parts data han and links to
the next node.
 Polynomial is a mathematical expression that consists of variables
and coefficients. for example x^2 - 4x + 7
 In the Polynomial linked list, the coefficients and exponents of the
polynomial are defined as the data node of the list.
 For adding two polynomials that are stored as a linked list. We need
to add the coefficients of variables with the same power. In a linked
list node contains 3 members, coefficient value link to the next node.
A linked list that is used to store Polynomial looks like − 4x 7 +
12x2 + 45
Addition of two polynomials using
Linked list
Adding two polynomials that are represented by a linked
list. We check values at the exponent value of the node. For
the same values of exponent, we will add the coefficients.
Example,
Input :p1= 13x8 + 7x5 + 32x2 + 54p2= 3x12 + 17x5 + 3x3 + 98
Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152
Multiplication of two polynomials using
Linked list
Two Variables Polynomial
Polynomials in two variables are algebraic expressions
consisting of terms in the form axnym . The degree of each
term in a polynomial in two variables is the sum of the
exponents in each term and the degree of the polynomial is
the largest such sum.
Here are some examples of polynomials in two variables
and their degrees.
x2y−6x3y12+10x2−7y+1 degree : 15
6x4+8y4−xy2 degree : 4
x4y2−x3y3−xy+x4 degree : 6
6x14−10y3+3x−11y degree : 14