MODULE IIi

LINKED LIST

A list can be defined as the collection of number of data items. List is the most commonly used non-
primitive data structure. An element of list must contain two fields, one for storing data or information and
other for storing address of next element. Pointers are used to store address of next element (node). So list can
be defined as a collection of nodes. In linked list memory is allocated at run time for program execution. That
is linked list is a dynamic memory allocation data structure.

Advantages

• It is a dynamic data structure that is , they can grow or shrink during the execution of a program.
• Effective memory utilization.
• Insertion and deletion are easier and efficient.

Disadvantage

• More memory: If the number of fields is more, then more memoryspace is needed.
• Access to an arbitrary data item is difficult.

KEY TERMS

Node: A linked list is a non-sequential collection of data items called nodes. Each node in a linked list
basically two fields.

Data field: It contains an actual value to be stored and processed.

Link field: It contains the address of next data item in the linked list.

Null pointer: The link field of the last node contains NULL rather than a valid address. It is a null pointer and
indicates the end of the list.

External pointer: It is a pointer to the very first node in the linked list, it enables us to access the entire linked
list.

Empty list: If the nodes are not present in the linked list then it is called empty linked list or NULL linked
list. i.e START= NULL

Notations

Let P be a pointer to node in a linked list. Then, we can form the following notations. To do
Node(P) : a node pointed to by the pointer P.

Data (P): Data of the node pointed to by P.

Link (P) : Address of the next node that follows the node pointed to by the pointer P.

Suppose , if the value P = 2000, then

Node (P) = Node(2000)

And

Data (P) = Data (2000) =20

Link (P) = Link(2000) = 3000

Example

REPRESENTATION OF LINEAR LINKED LIST

Suppose we want to store list of integer’s numbers, then the linear linked list can be represented in
memory with the following declaration.

class LinkedList {

Node head; // head of list

/* Linked list Node*/

class Node
{
int data;
Node next;
}
}

OPERATIONS ON LINKED LIST

The basic operations to be performed on the linked list are as follows:

1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
6. Concatenation
7. Display

Creation: this operation is used to create a linked list.

Insertion: this operation is used to new node in the linked list at the specified position. A node may be
inserted

• At the beginning
• At the end of a linked list
• At the specified position in a linked list
• If the list is empty, then the new node is inserted as a first node.

Deletion: this operation is used to delete an item (a node) from the linked list. A node may be deleted from the

• Beginning of the linked list

• End of a linked list
• Specified position in the list.

Traversing: It is a process of going through all the nodes of a linked list from one end to other end.

Concatenation: it is the process of appending (joining) the second list to the end of the first list.

Display: this operation used to print each and every node’s information.
 TYPES OF LINKED LIST

• Singly linked list

• Doubly linked list
• Circular linked list
• Circular doubly linked list

Singly linked list

It is one which all nodes are linked together in some sequential manner. Hence, it is also called linear
linked list. Clearly it has the beginning and the end. The problem with this list is that we cannot access the
predecessor of node from the current node. This can be overcome in doubly linked lists.

Doubly linked list

It is one which all nodes are linked together by multiple links which help in accessing both the
successor node (next node) and predecessor node (previous node) for any arbitrary node within the list. This
help to traverse the list in the forward direction and backward direction.

Circular linked list

It is one which has no beginning and no end. Like a singly linked list, in which the link field of the last
node contains the address of the first node of the list.
Circular doubly linked list

It is one which has both the successor pointer and predecessor pointer in circular manner.

Singly linked list

A singly linked list is a dynamic data structure. It may grow or shrink. Growing or shrinking depends
on the operations made. A linked list is created using structures and pointers. We consider head as an external
pointer. This helps in creating and accessing other nodes in the linked list.

class LinkedList {

Node head; // head of list

/* Linked list Node*/

class Node
{
int data;
Node next;
}
}
public static LinkedList insert(LinkedList list, int data)
{
Node new_node = new Node(data);
list.head = new_node;
When this statement is executed, a block of memory sufficient to store the NODE is allocated and assigns
head as the starting address of the NODE. It can be pictorially shown as follows:

Now we can assign values to the respective fields of NODE

Head.number=30

Head.ptr= ‘\0’
NODE would be like this:

Inserting nodes

To insert an element into the following three things should be done.

1. Allocating a node
2. Assigning the data
3. Adjusting the pointers

And inserting a new node into the linked list has the following three instances.

1. Insertion at the beginning

2. Insertion at the end of the list.
3. Insertion at the specified position within the list.

In order to insert a new node at one of the above three situations, we have to search for the location of
insertion.

The steps involved in deciding the position of insertion are as follows:

1. If the linked list is empty or the node to be inserted appears before the starting node then insert that
node at the beginning of the linked list
2. If the node to be inserted appears after the last node in the linked list then insert that node at the end of
the linked list.
3. If the above two conditions do not hold true then insert the new at the specified position within the
linked list.

Inserting a node at the beginning

An algorithm for inserting the new node at the beginning of the linked list given below:

1. Allocate memory for the new node.

2. Assign the value to the data field of the new node.
3. Make the link field of the new node to point to the starting node of the linked list.
4. Then, set external pointer to point to the new node.
After insertion

The code for the above algorithm is as follows:

Void insertatbegin(int item)

NODE *ptr;

Ptr = New NODE;

Ptr→info = item;

If( start == NULL)

Ptr→next = NULL;

Else

Ptr→next =start;

Start = ptr;

Inserting a node at the end

An algorithm for inserting the new node at the end of the linked list is given below:

1. If the list is empty, then create the new node.

2. If the list is not empty, then go to the last node and then insert the new node after the last node.
3. Make the link field of the new node to point to NULL.
 After insertion

voidinsert_at_end(int item)

NODE *ptr,*loc;

ptr= New NODE;

ptr→info =item;

ptr→next =NULL;

if(start == NULL)

start= ptr;

else

loc=start;

while(loc→next != NULl)

loc= loc→next;

loc→next =ptr;
 }

Inserting a new node at the specified position

An algorithm for inserting the new node at the specified within the linked list is as follows. Assume that the
new node is to be inserted between node A and node B.

1. Allocate memory for the new node.

2. Assign value to the data field of the new node
3. Make the link field of the new node to point to node B
4. Make the link field of Node A to point to new node.

The code for the above algorithm is as follows:

voidinsert_spe(int item, intloc)

NODE *ptr,*temp;

intk;

for(k= 0, temp =start;, k<loc; k++)

temp=temp→next;

if(temp==NULL)

cout<<”node in the list at less than one”;

return;

ptr= New NODE;

ptr→info =item;
 ptr→next =loc→next;

loc→next =ptr;

Deleting nodes

Deleting a node from the linked list has the following three instances

1. Deleting the first node of the linked list.

2. Deleting the last node of the linked list.
3. Deleting the specified node within the linked list.

The steps involved in deleting the node from the linked list are as follows:

1. If the linked list is empty then display the message “deletion is not possible”.
2. If the node to be deleted is the first node then set the pointer head to point to the second node in the
linked list.
3. If the node to be deleted is the last node, then go on locating the last but one node and set its link field
to point to null pointer.
4. If the situation is other than the above three, then delete the node from the specified position within the
linked list.

Deleting the first node

An algorithm for deleting the first node from the linked list is given below:

1. If the list is not empty then check whether the element belongs to the first node of the list.
2. Move the start pointer to the second node.
3. Free the first node.

After deletion
The code of the above algorithm is ,

voiddele_beg(void)

NODE *ptr;

if(start == NULL)

return;

else

ptr= start;

start= start→next

deleteptr;

Deleting the last node

An algorithm for deleting the last node from the linked list is given below:

1. If the linked list not empty, go on traversing the list till the last node.
2. Set link field of the last but one node to NULL.
3. Free the last node.

After deletion
The code for deleting from end position is:

voiddele_end(void)
{
NODE *ptr, *loc;
if(start == NULL)
{
return;
}
elseif(start.next==NULL)
{
ptr=start;
start=NULL;
}
else
{
loc=start;
ptr=start.next;
while(ptr.next!=NULL) {
loc=ptr;
ptr=ptr.next;
}
Loc.next=NULL;
Delete ptr;
}
}
Deleting the node from specified position
An algorithm for deleting the node in between two nodes Node A and Node B is given below:
1. If the linked list is not empty, then make the link field of Node A to point to Node B.
2. Free the node between Node A and Node B.
After deletion

The code for deleting from the specified position is:

voiddele_spe( )
{
NODE *ptr, *loc;
Int temp=300
ptr= start;
if(start== NULL)
{
System.out.println(“empty list”);
return;
}
else
{
loc = ptr;
while(ptr!= NULL)
{
if(ptr.info == temp)
{
 Loc.next= ptr. next;
Delete ptr;
return;
}
loc = ptr;
ptr= ptr.next;
}
}
}
Advantages
1. Accessibility of anode in the forward direction is easier.
2. Insertion and deletion of nodes are easier.
Disadvantages
1. Accessing of preceding node of a current node is not possible as there is no backward traversal.
2. Accessing a node is time consuming.

CIRCULAR LINKED LIST

It is just a singly linked list in which the link field of the last node contains the address of the first node
of the list. That is, the link field of the last does not point to NULL rather it points back to the beginning of the
linked list.

A circular linked list has no end. Therefore it is necessary to establish the FIRST and LAST nodes in
such linked list.

Inserting a node at the beginning

An algorithm to insert a new node at the beginning of the list is as follows:
 1. Allocate memory for the new node.
2. Assign the value to the data field of the new node.
3. If the list is empty then set,
FIRST= LAST = PTR
4. Otherwise, make the link field of the last node to point to the new node and finally set first to the new
node.

After insertion

The code is:

voidinsert_at_begin(int item)
{
NODE *ptr;
ptr=New NODE;
ptr.info =item
if(first == NULL)
ptr.next = ptr;
else
ptr.next = first;
first=ptr;
last.next=ptr;
}
Inserting a new node at the end
An algorithm to insert a node at the end of the circular list is given below:
1. Allocate memory for the new node.
2. Assign the value to the data field of the new node.
3. If the list is empty then set,
FIRST= LAST = PTR
4. Otherwise, make the link field of the last node to point to the new node. Also make the link field of the
new node to point to the FIRST node. And finally set LAST to the new node.

After insertion

The code is:

voidinsert_at_end(int item)
{
NODE *ptr, *loc;
ptr=New NODE;
ptr. info =item
if(first == NULL)
{
first=last= ptr;
 ptr.next = ptr;
}
else
{
Last.next=ptr;
Ptr.next = first;
last =ptr
}
}
Deleting a node from the beginning
An algorithm to delete a node from the beginning of the list is given below:
1. If the list is empty then display the message “ list is empty and no deletion”

2. If FIRST = LAST then free the FIRST node and set FIRST= LAST =NULL.

3. Otherwise, make the temporary pointer to point to the FIRST node and make the FIRST to point to the
next node in the list. Then set the link field of the last node to point to wherever the FIRST is pointing
to. Finally, free the node pointed to by TEMP.

After deletion

The code is:

voiddele_beg(void)
{
NODE *ptr;
if( first== NULL)
{
return;
}
else if( first==last)
{
ptr=first;
first=last=NULL;
delete ptr;
}
else
{
ptr= first;
first= first.next;
last.next= first;
delete ptr;
}
}
Deleting a node from the end
An algorithm to delete a node from the end in the circular linked list is given below:
1. If the list is empty then display the message “ list is empty and no deletion”
2. If FIRST = LAST then free the FIRST node and set FIRST= LAST =NULL.
3. Otherwise, go on traversing till the LAST but one node and set its link field to point back to te FIRST
node. Then free the LAST node.
 After deletion

The code is:

voiddele_end(void)
{
NODE *ptr, *loc;
if( first == null)
{
return;
}
else if( first== last)
{
ptr= first;
first = last=null;
delete ptr;
}
else
{
loc= first;
ptr=first .next;
while(ptr.next!=first) {
 loc=ptr;
ptr=ptr.next;
}
Loc.next=first;
last=loc;
delete ptr;
}
}

Doubly linked list

One of the most disadvantages of previous lists is that the inability to traverse the list in the backward
direction. In most of the real world applications it is necessary to traverse the list both in forward and
backward direction. The most appropriate data structure for such an application is a doubly linked list.
A doubly linked list is one in which all nodes are linked together by multiple number of links which
help in accessing both the successor node and predecessor node from the given node position. It provides
bidirectional traversing.

The LEFT link points to the predecessor node and the right link points to the successor node. The structure
definition for the above node is:
class LinkedList {

Node head; // head of list

/* Linked list Node*/

class Node
{
int data;
Node next;
Node previous;
}
}
Insertion a node at the beginning
An algorithm to insert a new node at the beginning of a doubly linked list is given below:
1. Allocate memory for the new node.
 2. Assign value to the data field of the new node.
3. Assign LEFT and RIGHT links to NULL.
4. Make the RIGHT link of the new node to point to the head node of the list. And make LEFT link of
the head node to point to the new node.
5. Finally reset the head pointer. That is, make it to the new node which has inserted at the beginning.

The code part is:

voidinsert_at_beginning(int item)

node *ptr;

ptr=new node;

ptr.info=item;

if (head ==null)

Ptr.prev =ptr.next =null;

head =tail =ptr;

else

Ptr.next=head;

Head.prev=ptr;

Ptr.prev=null;

head=ptr;

}
}

Inserting a node at the end

An algorithm to insert a node at the end of a doubly linked list is given below:

1. Allocate memory for the new node.

2. Assign value to the data field of the new node.
3. Set the LEFT and RIGHT links to the new node.
4. If the list is not empty then traverse the list till the last and make the right link of the last node to point
to the new node and LEFT link of the new node to point to the last node.

Memory Allocation

Whenever a new node is created, memory is allocated by the system. This memory is taken from list of
those memory locations which are free i.e. not allocated. This list is called AVAIL List. Similarly, whenever a
node is deleted, the deleted space becomes reusable and is added to the list of unused space i.e. to AVAIL
List. This unused space can be used in future for memory allocation.

Memory allocation is of two types

1. Static memory allocation

2. Dynamic memory allocation

Static Memory Allocation

When memory is allocated during compilation time, it is called ‘Static Memory Allocation’. This
memory is fixed and cannot be increased or decreased after allocation. If more memory is allocated than
requirement, then memory is wasted. If less memory is allocated than requirement, then program will not run
successfully. So exact memory requirements must be known in advance.

Dynamic Memory Allocation

When memory is allocated during run/execution time, it is called ‘Dynamic Memory Allocation’. This
memory is not fixed and is allocated according to our requirements. Thus in it there is no wastage of memory.
So there is no need to know exact memory requirements in advance.

Reasons and Advantage of allocating memory dynamically:

1. When we do not know how much amount of memory would be needed for the program beforehand.
2. When we want data structures without any upper limit of memory space.
3. When you want to use your memory space more efficiently.Example: If you have allocated memory
space for a 1D array as array[20] and you end up using only 10 memory spaces then the remaining 10
memory spaces would be wasted and this wasted memory cannot even be utilized by other program
variables.
4. Dynamically created lists insertions and deletions can be done very easily just by the manipulation of
addresses whereas in case of statically allocated memory insertions and deletions lead to more
movements and wastage of memory.
5. When you want you to use the concept of structures and linked list in programming, dynamic memory
allocation is a must.
Boundary Tag Method to free Memory is described below

To remove the arbitrary block from the free list (to combine it with the newly made free block) without
traversing the whole list, the free list should be doubly linked. Thus each and every free block must
contain 2 pointers, next and prev to the next and previous free block on the free block. (This is required
when combining a newly freed block with a free block which immediately proceeds in the memory). Thus
the front of the free block should be accessible from its rear. One way to do this is to introduce
a bsize field at the given offset from the last location or address of each free block. This field exhibits the
same value as the size filed at the front of the block. This field have the some value as the size field at the
front of the block. The figure below shows the structure of free and allocated blocks under this method
which is called the boundary tag method.

free block allocated block

Each of the contract fields fflag, prev, size, next, bsize next and bflag is shown as occupying a complete
word, although in practice they can be packed together, several fields to a word. We assume that fflag or
bflag are logically flags and that true signifies an allocated block and false indicates a free block. Using
the information in the free block and the newly freed block, the system merges the two blocks into a
bigger hole.
Garbage Collection

Whenever a node is deleted, some memory space becomes reusable. This memory space should be
available for future use. One way to do this is to immediately insert the free space into availability list. But
this method may be time consuming for the operating system. So another method is used which is called
‘Garbage Collection’. This method is described below: In this method the OS collects the deleted space time
to time onto the availability list. This process happens in two steps. In first step, the OS goes through all the
lists and tags all those cells which are currently being used. In the second step, the OS goes through all the
lists again and collects untagged space and adds this collected space to availability list. The garbage collection
may occur when small amount of free space is left in the system or no free space is left in the system or when
CPU is idle and has time to do the garbage collection.

Compaction

Compaction is a technique to collect all the free memory present in form of fragments into one large chunk
of free memory, which can be used to run other processes.

It does that by moving all the processes towards one end of the memory and all the available free space
towards the other end of the memory so that it becomes contiguous.

It is not always easy to do compaction. Compaction can be done only when the relocation is dynamic and
done at execution time. Compaction can not be done when relocation is static and is performed at load time
or assembly time.

Before Compaction
Before compaction, the main memory has some free space between occupied space. This condition is
known as external fragmentation. Due to less free space between occupied spaces, large processes cannot be
loaded into them.

Main Memory

Occupied space

Free space

Occupied space

Occupied space

Free space

After Compaction
After compaction, all the occupied space has been moved up and the free space at the bottom. This makes
the space contiguous and removes external fragmentation. Processes with large memory requirements can
be now loaded into the main memory.

Main Memory

Occupied space

Occupied space

Occupied space

Free space

Free space

Purpose of Compaction in Operating System

While allocating memory to process, the operating system often faces a problem when there’s a sufficient
amount of free space within the memory to satisfy the memory demand of a process. however the process’s
memory request can’t be fulfilled because the free memory available is in a non-contiguous manner, this
problem is referred to as external fragmentation. To solve such kinds of problems compaction technique is
used.