Data Structures and Applications (CS204) Module 3
Module 3
Linked Lists: Definition, Representation of linked lists in Memory, Linked list operations: Traversing,
Searching, Insertion, and Deletion, Doubly Linked lists Circular linked lists and header linked
operations: Traversing, Searching, Insertion, and Deletion, polynomial using header linked list.
Text book 1: 4.1, 4.2, 4.3, 4.4, 4.5, 4.8
Why use linked list over array?
Till now, we were using array data structure to organize the group of elements that are to be stored
individually in the memory. However, Array has several advantages and disadvantages which must be
known in order to decide the data structure.
Array contains following limitations:
1. The size of array must be known in advance before using it in the program.
2. All the elements in the array need to be contiguously stored in the memory.
3. Inserting any element in the array needs shifting of all its predecessors. Also, delete operations is
tedious.
4. Expanding or shrinking the size of the array is difficult.
Linked list is the data structure which can overcome all the limitations of an array. Using linked list is
useful because,
1. It allocates the memory dynamically.
2. All the nodes of linked list are non-contiguously stored in the memory and linked together with
the help of pointers.
3. Sizing is no longer a problem since we do not need to define its size at the time of declaration.
4. List grows as per the program's demand and limited to the available memory space.
Note: No particular data structure is the best. The choice of the data structure depends on the kind of
application that needs to be implemented. While for some applications linked lists may be useful, for
others, arrays may be useful.
Use Arrays when we need quick access to elements, better memory efficiency, and when the data size
is static.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1
,Data Structures and Applications (CS204) Module 3
Use Linked Lists when the data size is dynamic, frequent insertions and deletions are needed, or when
implementing certain complex data structures.
3.1 Definition : Linked List
Linked list is a linear data structure that consists of a sequence of elements where each element (usually
called a node) comprises of two items - the data and a reference (link) to the next node. The last node
has a reference to null.
The linked list contains a list variable called START or FIRST or HEAD, which contains the address of the first
node in the list. We need only this address in START to trace through the list.
The entry point into a linked list is called the head (start or first) of the list. It should be noted that
head is not a separate node, but the reference to the first node. If the list is empty then the start is a
null reference. The list with no nodes –empty list or null list.
Types of Linked List
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Header Linked List
3.2 Representation of linked lists in Memory
We need the following capabilities to make linked representations possible:
1) A mechanism for defining a node’s structure, that is, the fields it contains. We use self-referential
structure for this.
struct node
{
int data;
struct node *next;
};
struct node *head;
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2
,Data Structures and Applications (CS204) Module 3
2) A way to create new nodes when we need them. We use malloc() function for this.
3) A way to remove nodes that we no longer need. We use free() function for this.
head
8
3.3 Linked list operations: Traversing, Searching, Insertion, and Deletion
Singly linked list or One way chain
Singly linked list can be defined as the collection of ordered set of elements. The number of elements
may vary according to need of the program. A node in the singly linked list consist of two parts: data part
and link part. Data part of the node stores actual information that is to be represented by the node while
the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we can say
that each node contains only next pointer, therefore we cannot traverse the list in the reverse direction.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 3
, Data Structures and Applications (CS204) Module 3
Consider an example where the marks obtained by the student in three subjects are stored in a linked list
as shown in the figure.
In the above figure, the arrow represents the links. The data part of every node contains the marks
obtained by the student in the different subject. The last node in the list is identified by the null pointer
which is present in the address part of the last node.
Operations on Singly Linked List
There are various operations which can be performed on singly linked list. A list of all such operations is
given below.
Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
SN Operation Description
Insertion at beginning
It involves inserting any
element at the front of the list.
1 We just need to a few link
adjustments to make the new
node as the head of the list.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 4
Module 3
Linked Lists: Definition, Representation of linked lists in Memory, Linked list operations: Traversing,
Searching, Insertion, and Deletion, Doubly Linked lists Circular linked lists and header linked
operations: Traversing, Searching, Insertion, and Deletion, polynomial using header linked list.
Text book 1: 4.1, 4.2, 4.3, 4.4, 4.5, 4.8
Why use linked list over array?
Till now, we were using array data structure to organize the group of elements that are to be stored
individually in the memory. However, Array has several advantages and disadvantages which must be
known in order to decide the data structure.
Array contains following limitations:
1. The size of array must be known in advance before using it in the program.
2. All the elements in the array need to be contiguously stored in the memory.
3. Inserting any element in the array needs shifting of all its predecessors. Also, delete operations is
tedious.
4. Expanding or shrinking the size of the array is difficult.
Linked list is the data structure which can overcome all the limitations of an array. Using linked list is
useful because,
1. It allocates the memory dynamically.
2. All the nodes of linked list are non-contiguously stored in the memory and linked together with
the help of pointers.
3. Sizing is no longer a problem since we do not need to define its size at the time of declaration.
4. List grows as per the program's demand and limited to the available memory space.
Note: No particular data structure is the best. The choice of the data structure depends on the kind of
application that needs to be implemented. While for some applications linked lists may be useful, for
others, arrays may be useful.
Use Arrays when we need quick access to elements, better memory efficiency, and when the data size
is static.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1
,Data Structures and Applications (CS204) Module 3
Use Linked Lists when the data size is dynamic, frequent insertions and deletions are needed, or when
implementing certain complex data structures.
3.1 Definition : Linked List
Linked list is a linear data structure that consists of a sequence of elements where each element (usually
called a node) comprises of two items - the data and a reference (link) to the next node. The last node
has a reference to null.
The linked list contains a list variable called START or FIRST or HEAD, which contains the address of the first
node in the list. We need only this address in START to trace through the list.
The entry point into a linked list is called the head (start or first) of the list. It should be noted that
head is not a separate node, but the reference to the first node. If the list is empty then the start is a
null reference. The list with no nodes –empty list or null list.
Types of Linked List
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Header Linked List
3.2 Representation of linked lists in Memory
We need the following capabilities to make linked representations possible:
1) A mechanism for defining a node’s structure, that is, the fields it contains. We use self-referential
structure for this.
struct node
{
int data;
struct node *next;
};
struct node *head;
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2
,Data Structures and Applications (CS204) Module 3
2) A way to create new nodes when we need them. We use malloc() function for this.
3) A way to remove nodes that we no longer need. We use free() function for this.
head
8
3.3 Linked list operations: Traversing, Searching, Insertion, and Deletion
Singly linked list or One way chain
Singly linked list can be defined as the collection of ordered set of elements. The number of elements
may vary according to need of the program. A node in the singly linked list consist of two parts: data part
and link part. Data part of the node stores actual information that is to be represented by the node while
the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we can say
that each node contains only next pointer, therefore we cannot traverse the list in the reverse direction.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 3
, Data Structures and Applications (CS204) Module 3
Consider an example where the marks obtained by the student in three subjects are stored in a linked list
as shown in the figure.
In the above figure, the arrow represents the links. The data part of every node contains the marks
obtained by the student in the different subject. The last node in the list is identified by the null pointer
which is present in the address part of the last node.
Operations on Singly Linked List
There are various operations which can be performed on singly linked list. A list of all such operations is
given below.
Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
SN Operation Description
Insertion at beginning
It involves inserting any
element at the front of the list.
1 We just need to a few link
adjustments to make the new
node as the head of the list.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 4
