MODULE 2: LINKED LISTS
1. Disadvantages of Arrays:
a. The size is fixed.
It is not possible to predict the exact size of the memory required in the program.
b. The elements are stored continuously next to each other.
There may come a situation where there is availability of a number of chunks of
contiguous memory locations whose size my not be sufficient to store the items
and hence leads to the wastage of storage space.
c. Insertion and deletion operatios is a tedious task.
If insertion needs to be done in the ith position, then all the elements from (i+1)th
position have to be moved to the next subsequent locations.
Similarly, when deletion needs to be done from the ith position, all elements from
(I +1)th position should be moved to their corresponding previous locations.
This results in extensive manipulation of stored data and more time is spent in just
moving this data.
This can be overcome using linked lists.
2. Definition: Linked list is a non-sequential collection of nodes. Each node has 2 fields
namely,
i. Info field, which stores the data or information to be manipulated.
ii. Next/ link field, contains the address of the next node.
Info link
Address of next node
3. Classification of linked lists:
It can be classified into 4 types namely,
i. Singly linked list
ii. Doubly linked list
iii. Circular singly linked list
iv. Circular doubly linked list
4. Representation of Linked lists:
• List is represented in two linear arrays namely, INFO and LINK where INFO
contains the information part and LINK contains the address of the next node.
• Also, it contains a variable name START, which contains the location of the
beginning of the list.
• The nodes of the list need not occupy adjacent elements in the arrays INFO and
LINK.
• Linear arrays INFO and LINK may contain more than one list, where each list
have a pointer variable giving the location of its first node.
A) Singly Linked List(SLL):
Operations performed on SLL:
1. Create a node(How to define a node?)
Struct node // structure definition of a node
{
Int INFO;
Struct node *link;
}
Struct node // structure definition of node along with declaration of a variable
{
Int INFO;
Struct node *link;
};
Typedef struct node *NODE;
//Creating an empty list
First = NULL;
// Creating a new node
MALLOC(first, 1, struct node);
// store the data
First->info = 10;
First->link = NULL;
First->info first->link
10 NULL
First
2. Insertion at the beginning
Steps:
i. Allocate memory for the new node temp
ii. Copy the item into ‘info’ field of temp.
iii. Copy the address of the first node of the list in the ‘link’ field of temp.
iv. Return the address of the first node temp.
Code:
Insert_front()
{
NODE temp;
MALLOC(temp, 1, struct node); //obtain a node from the available list
Temp->info = item; // insert an item into new node
Temp->link = first; // insert new node at the front of the list
Return temp; // return the new first node
}
3. Insertion at the end
Steps:
a) Create a new node temp.
b) If the list is empty, the new node temp is returned as the first node.
c) If the list is not empty, then the new node is inserted at end of the list.(For
this, we need to obtain the address of the last node. So, we have to start from
the first node using a variable ‘cur’ which initially points to the first node.)
d) Obtain the address of the last node.
e) The new node temp is linked to the link field of the cur.
NODE insert_rear(int item, NODE first)
{
NODE temp; // points to newly created node.
NODE cur; // to hold the address of the last node.
MALLOC(temp, 1, struct node); //obtain the new node and copy the item
Temp->info = item;
Temp->link = NULL; // step 1
If(first == NULL) return temp; // step 2
cur = first; // steps 3 and 4
While(cur->link!= NULL);
{
cur =cur->link;
}
Cur->link = temp; // step 5
Return temp; // step 6
}
4. Display
Steps:
a) Check if the list is empty. If empty, display List is empty.
b) If list is existing, make temp contain the address of the first node and display
temp and continue with the rest nodes using their corresponding links.
Void display()
{
NODE temp;
If(first = = NULL) // step a
{
Printf(“List is empty\n”);
Return;
}
Printf(“\n The contents of singly linked list”); // step b
temp = first;
While(temp ! = NULL)
{
Printf(“%d”, temp->info);
temp = temp->link;
}
Print(“\n”);
