Unit 4: Linked List

A linked list is a linear data structure which can store a collection of "nodes" connected together via links
i.e. pointers. Linked lists nodes are not stored at a contiguous location, rather they are linked using
pointers to the different memory locations. A node consists of the data value and a pointer to the address
of the next node within the linked list.
A linked list is a dynamic linear data structure whose memory size can be allocated or de-allocated at
run time based on the operation insertion or deletion, this helps in using system memory efficiently.
Linked lists can be used to implement various data structures like a stack, queue, graph, hash maps,
etc.

A linked list starts with a head node which points to the first node. Every node consists of data which
holds the actual data (value) associated with the node and a next pointer which holds the memory
address of the next node in the linked list. The last node is called the tail node in the list which points
to null indicating the end of the list.
Representation of Linked List
Let's see how each node of the linked list is represented. Each node consists:
• A data item
• An address of another node
We wrap both the data item and the next node reference in a struct as:
struct node
{
int data;
struct node *next;
};
Understanding the structure of a linked list node is the key to having a grasp on it.
Applications of Linked Lists
Linked lists are widely used in computer science for solving various programming problems and for
building other data structures. Their ability to handle dynamic memory and efficient insertion and
deletion makes them suitable for many applications. Here are the key applications of linked lists:
1. Implementing Other Data Structures- Linked lists serve as the foundation for building several
important data structures, such as
• Stacks (LIFO structure)
• Queues (FIFO structure)
• Graphs (Adjacency List representation)
• Hash Tables (to handle collisions using separate chaining)
2. Dynamic Memory Allocation- Operating systems and memory managers use linked lists to track
free and used memory blocks. A free list is maintained using a linked list to allocate and release memory
dynamically at runtime.
3. Handling Large and Variable Data Sets- When the size of the data is unknown or changes
frequently during program execution, linked lists are preferred over arrays because they don’t require
predefined sizing and can grow or shrink efficiently.
4. Navigation Systems-Doubly linked lists are used in web browsers to manage page history, enabling
back and forward navigation between web pages.
5. Scheduling and Task Management- Operating systems often use circular linked lists to manage
process scheduling, where the scheduler cycles through tasks in a round-robin manner.
6. Undo/Redo Functionality- Applications like text editors and drawing tools use linked lists to
implement undo and redo actions, maintaining a history of previous states.
7. Polynomial Arithmetic- In mathematical computations, linked lists can be used to represent and
manipulate polynomials where each node holds a term with its coefficient and exponent.
Advantages of Linked Lists
• Efficient Insertion and Deletion: Unlike arrays, inserting or deleting elements in a linked list
does not require shifting other elements. Only the pointers need to be updated, making operations
like insertion and deletion faster and more efficient, especially for large datasets.
• Flexibility in Implementation: Linked lists are highly versatile and serve as the foundation for
various advanced data structures such as stacks, queues, graphs, and hash tables (with chaining).
This flexibility makes them essential in many algorithmic and system-level implementations.
• Memory Efficiency: Linked lists utilize memory more effectively by allocating space only as
needed. Since nodes are created dynamically, there is no unused or wasted memory as in the
case of static data structures like arrays.
• Ease of Implementation: Implementing a linked list is relatively straightforward. It requires
defining a simple node structure and a few pointer-based operations, making it a great choice for
beginners learning data structures and memory management.
• Dynamic Size Allocation: Linked lists offer dynamic memory allocation, meaning the list can
grow or shrink at runtime without predefined size limits. This makes them ideal for applications
where the amount of data changes frequently.
Disadvantages of Linked Lists
1. Memory Consumption: The use of pointers is more in linked lists hence, complex and requires
more memory.
2. Traversal: Unlike arrays, linked lists do not allow direct access to individual nodes. Traversing a
linked list requires iterating through all the nodes from the beginning of the list until the desired
node is found. This can be inefficient and slow, especially for large linked lists. Traversing in
reverse order is not possible in singly linked lists.
3. No Random Access: Linked lists do not support random access, i.e., accessing a specific node
directly without traversing the list. This can be a significant disadvantage for some applications
that require fast access to individual elements.
4. Cache Misses: Linked lists can suffer from cache misses, i.e., when the CPU needs to access
data that is not in the cache. This can slow down the execution of programs that frequently access
data from linked lists.
5. Search: Linked lists are not efficient for searching large amounts of data, which can be better
handled by other data structures such as trees or hash tables.
Differences between Arrays and Linked Lists
Array Linked List
It is a collection of elements of a similar data type. It is a group of objects called nodes, which consists
of two fields: data and address to the next node
An array stores elements in a contiguous memory Linked lists store elements randomly at any address
location. in the memory.
In an array, memory size is fixed while declaration and Linked lists utilize dynamic memory, i.e. memory
cannot be altered at run time. size can be altered at run time.
Elements in an array are not dependent on each other. Elements in a linked list are dependent on each
other, as each node stores the address of its next
node.
Operations like insertion, deletion, etc., take more Operations like insertion, deletion, etc., take less
time in an array. time than arrays.
Memory is allocated at compile time. Memory is allocated at run time.
It is easier and faster to access the element in an Accessing an element in a linked list is time-
array with the help of Indices. consuming as we have to start traversing from the
first element.
Memory utilization is ineffective in arrays. E.g. if the In linked lists, memory utilization is effective, as it
array size is 5 and contains only 3 elements, the rest can be allocated or deallocated at the run time
of the space will be wasted. according to our requirements.
Arrays support multi-dimensional structures. Linked lists are typically used for one-dimensional
structures.
Arrays are commonly used in low-level programming Linked lists are often used for specific data
and for implementing data structures. management needs like task scheduling and
memory allocation.

4.1 Implementation of List – Dynamic representation

A list is a linear data structure that holds a collection of elements. A dynamic list (also called a dynamic
array) is one where the size of the list can change during runtime—elements can be added or removed
without needing to define a fixed size at the beginning.

A dynamic representation of a list, often implemented as a linked list, allows the list's size to change
during program execution. Unlike static arrays, which have a fixed size determined at compilation,
dynamic lists allocate and deallocate memory as needed, providing flexibility in managing data.
Key aspects of dynamic list implementation (using a singly linked list as an example):
Unlike arrays, where elements are stored in contiguous memory locations, linked lists
allocate memory dynamically for each node. This means that each node can be located anywhere
in the memory and they are connected via pointers.
Before looking at the memory representation of singly linked list. Let's first create a linked list
having four nodes. Each node has two parts: one part holds a value (data) and the other part holds
the address of the next node. The first node is called the head node and it points to the first element
in the list. The last node in the list points to NULL, which means there are no more nodes after it.

In the above singly linked list, each node is connected by pointers. These pointers show the address of
the next node, which allowing us to move through the list in forward direction. This connection is shown
with arrows in the diagram, making it clear how each node links to the next one.
Each node in the linked list created dynamically whenever it is
required
• Memory space will be allocated for each node as neede while the
program is running
• Nodes has two files such as data and next.
• The dynamic representation of nodes as follows
struck list
{
int data
struck list *next
};
typedef struck list node
Linked List - 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.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point
B.next to C −
NewNode.next -> RightNode;
It should look like this −

Now, the next node at the left should point to the new node.
LeftNode.next -> NewNode;
This will put the new node in the middle of the two. The new list should look like this −

Insertion in linked list can be done in three different ways. They are explained as follows −
Insertion at Beginning
In this operation, we are adding an element at the beginning of the list
1. START
2. Create a node to store the data
3. Check if the list is empty
4. If the list is empty, add the data to the node and
assign the head pointer to it.
5. If the list is not empty, add the data to a node and link to the
current head. Assign the head to the newly added node.
6. END
Linked List Implementations example // Linked list implementation in C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Creating a node
class Node {
public:
int value;
Node* next;
};
int main() {
Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// print the linked list value
head = one;
while (head != NULL) {
cout << head->value;
head = head->next;
}
}
4.3 Types of Linked List
1. Singly-linked list: Here, each node has data and a pointer that contains a reference to the next
node in the list. This means that we can traverse in only one direction, from the head to the tail.
It is the most common linked list.
2. Doubly linked list: In this type of linked list, each interconnected node contains three fields that
contain references to both the next and previous nodes in the list along with the data. This allows
traversal in both directions, making it easier to insert or delete nodes at any point in the list.
3. Circular linked list: Here, the last node in the list contains a reference to the first node instead
of NULL, creating a loop. This means that traversal can continue indefinitely, until the program
crashes.

Singly Linked
Singly linked lists contain two "buckets" in one node; one bucket holds the data and the other bucket
holds the address of the next node of the list. Traversals can be done in one direction only as there is
only a single link between two nodes of the same list.

Node is represented as:

struct node {
int data;
struct node *next;
}
Example
// C++ program to illustrate creation
// and traversal of Singly Linked List
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}};
void printList(Node* curr) {
// Iterate till n reaches NULL
while ( curr != nullptr) {
cout << curr->data << " ";
curr = curr->next;
 }
}
int main() {

//Linked List 1 -> 2 -> 3

Node* head = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
head->next = second;
second->next = third;
printList(head);
return 0;
}
Doubly Linked List
We add a pointer to the previous node in a doubly-linked list. Thus, we can go in either direction: forward
or backward. A Doubly Linked List contains an extra memory to store the address of the previous node,
together with the address of the next node and data which are there in the singly linked list. So, here
we are storing the address of the next as well as the previous nodes.
The following is the structure of the node in the Doubly Linked List(DLL):

A node is represented as
struct node {
int data;
struct node *next;
struct node *prev;
}
Example :-
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode ;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The doubly linked list is: ";
display();
return 0;
}
Circular Linked List
A circular linked list is either a singly or doubly linked list in which there are no NULL values. Here, we
can implement the Circular Linked List by making the use of Singly or Doubly Linked List. In the case of
a singly linked list, the next of the last node contains the address of the first node and in case of a
doubly-linked list, the next of last node contains the address of the first node and prev of the first node
contains the address of the last node. A circular singly linked list is a type of data structure that is
made up of nodes that are created using self-referential structures. Each node contains two components,
namely the data element and the reference to the next node in the list.
Only the reference to the head node is required to access the whole linked list. The last node of the list
points to the head node, which makes it a circular linked list. Let's see a diagram of circular linked list.

Advantages of a Circular linked list

• The list can be traversed from any node.
• Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
• We can easily traverse to its previous node in a circular linked list, which is not possible in a singly
linked list. ( Think!)
Disadvantages of Circular linked list
• If not traversed carefully, then we could end up in an infinite loop because here we don't have
any NULL value to stop the traversal.
• Operations in a circular linked list are complex as compared to a singly linked list and doubly
linked list like reversing a circular linked list, etc.
Example
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node * next;
};
struct Node * head = NULL;
void insert(int newdata) {
 struct Node * newnode = (struct Node * ) malloc(sizeof(struct Node));
struct Node * ptr = head;
newnode -> data = newdata;
newnode -> next = head;
if (head != NULL) {
while (ptr -> next != head)
ptr = ptr -> next;
ptr -> next = newnode;
} else
newnode -> next = newnode;
head = newnode;
}
void display() {
struct Node * ptr;
ptr = head;
do {
cout << ptr -> data << " ";
ptr = ptr -> next;
} while (ptr != head);
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout << "The circular linked list is: ";
display();
return 0;
}
4.4 Applications of linked list – polynomial manipulation
Applications of linked list in the real world:
1. Image viewer - Previous and next images are linked and can be accessed by the next and
previous buttons.
2. Previous and next page in a web browser - We can access the previous and next URL
searched in a web browser by pressing the back and next buttons since they are linked as a linked
list.
3. Music Player - Songs in the music player are linked to the previous and next songs. So you can
play songs either from starting or ending of the list.
4. GPS navigation systems- Linked lists can be used to store and manage a list of locations and
routes, allowing users to easily navigate to their desired destination.
 5. Robotics- Linked lists can be used to implement control systems for robots, allowing them to
navigate and interact with their environment.
6. Task Scheduling- Operating systems use linked lists to manage task scheduling, where each
process waiting to be executed is represented as a node in the list.
7. Image Processing- Linked lists can be used to represent images, where each pixel is
represented as a node in the list.
8. File Systems- File systems use linked lists to represent the hierarchical structure of directories,
where each directory or file is represented as a node in the list.
9. Symbol Table- Compilers use linked lists to build a symbol table, which is a data structure that
stores information about identifiers used in a program.
10. Undo/Redo Functionality- Many software applications implement undo/redo functionality using
linked lists, where each action that can be undone is represented as a node in a doubly linked
list.
11. Speech Recognition- Speech recognition software uses linked lists to represent the possible
phonetic pronunciations of a word, where each possible pronunciation is represented as a node
in the list.
12. Polynomial Representation- Polynomials can be represented using linked lists, where each
term in the polynomial is represented as a node in the list.
13. Simulation of Physical Systems- Linked lists can be used to simulate physical systems, where
each element in the list represents a discrete point in time and the state of the system at that
time.

Question
What is link list ? How many Types
How implementation of link list ?
Explain the singular link list with example ?
Explain circular link list with example
Explain Doubly link list