Unit – 3
Linked List
Q1) Describe Memory representation?
A1) Each node in the singly linked list points to the next node and it appears to move in one direction. Thus, SLL is unidirectional. Fig. Shows a schematic diagram of singly linked list with 4 nodes.
Fig.: Singly Linked List
Implementation in C:
Typedef struct node
{
Int data;
Struct node *next;
} node;
A node is defined by structures in C. This structure is called as self-referential structure. This node stores integer value in data field of node. Next stores address of next node and hence declared as a pointer variable.
Creation of First Node:
Step 1: node *P;
Step 2: P = (node*) malloc(sizeof(node));
Step 3: P->data = 10;
Step 4: P->next=NULL;
Step 1 declares P as a node.
Step 2 allocates memory to node P with c standard function malloc. The malloc function returns void pointer and hence type casted before assigning to P.
Step 3 stores value 10 in data field of node P. This is done with the help of arrow operator → .It is also called as structure member operator.
Step 4 stores NULL value in address field of node P.
Q2) Write a program to create a Linked List?
A2) Program to create a linked list
#include <stdio.h>
#include<conio.h>
Typedef struct node
{
Int data;
Struct node *next;
}node;
Void main()
{
Node *HEAD, *P ;
Int n,i;
Printf(“Enter no of nodes to be inserted ”)
Scanf(“%d”, &n);
HEAD = (node*)malloc(sizeof(node));//get the first node
Scanf(“%d”, &(HEAD->data));// get data in first node
HEAD->next= NULL;
P=HEAD;// currently HEAD and P points to same node
For(i=1;i<n;i++)// for n nodes
{
P->next= (node*)malloc(sizeof(node));
P=P->next;
P->next= NULL;
Scanf(“%d”, &(P->data));
}
}
Explanation:
Declare node with self-referential structure.
Create HEAD node which is first node in Linked List.
HEAD = (node*) malloc(sizeof(node));
Store data in First node.
Scanf (“%d”, &(HEAD->data)) ;//
Currently there is only one node in Linked List. So *next contains Null value and HEAD and P points to same node.
HEAD → next=NULL;
P=HEAD;
Now create remaining nodes with the help of following code.
For (i=1; i<n; i++)// for n nodes
{
P->next= (node*) malloc(sizeof(node));
P=P->next;
P->next= NULL;
Scanf (“%d”, &(P->data));
}
Q3) Program to create and display the Linked List using function. This program also count the total number of nodes in the Linked List?
A3) Program to create and display the linked list
#include <stdio.h>
#include<conio.h>
Typedef struct node
{
Int data;
Struct node *next;
}node;
Node *create(int);
Void display(node*);
Int count(node *);
Void main()
{
Node *HEAD;
Int n, x;
Printf(“Enter number of nodes”);
Scanf(“%d”, &n);
HEAD = create(n) ;
Display(HEAD);
x= count(HEAD);
Printf(“Total number of nodes =”+x);
Getch();
}
Node *create(int n)
{
Node *start, *P;
Int i;
HEAD= (node*)malloc(sizeof(node));
Start-> next = NULL;
Scanf(“%d”, &(start->data));
P= start;
For(i=1;i<n;i++)
{
P->next = (node*)malloc(sizeof(node));
P=P->next;
Scanf(“%d”, &(P->data));
P->next= NULL;
}
Return(start);
}
Void display(node *P)
{
Printf(“Nodes are”)
While(P!=NULL)
{
Printf(“ %d ”P->data);
P=P->next;
}
}
Int count(node *P)
{
Int i=0;
While(P!=NULL)
{
P=P->next;
i++;
}
Return(i)
}
Output:
Enter number of nodes: 3
10 20 30
Nodes are
10 20 30
Total number of nodes: 3
Q4) Define Traversing in several operations?
A4) Traversing is the most common operation that is performed in almost every scenario of singly linked list. Traversing means visiting each node of the list once in order to perform some operation on that. This will be done by using the following statements.
Ptr = head;
While (ptr! =NULL)
{
Ptr = ptr -> next;
}
Algorithm
STEP 1: SET PTR = HEAD
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 7
END OF IF
STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR! = NULL
STEP 5: PRINT PTR→ DATA
STEP 6: PTR = PTR → NEXT
[END OF LOOP]
STEP 7: EXIT
C function
#include<stdio.h>
#include<stdlib.h>
Void create(int);
Void traverse();
Struct node
{
Int data;
Struct node *next;
};
Struct node *head;
Void main ()
{
Int choice,item;
Do
{
Printf("\n1.Append List\n2.Traverse\n3.Exit\n4.Enter your choice?");
Scanf("%d",&choice);
Switch(choice)
{
Case 1:
Printf("\nEnter the item\n");
Scanf("%d",&item);
Create(item);
Break;
Case 2:
Traverse();
Break;
Case 3:
Exit(0);
Break;
Default:
Printf("\nPlease enter valid choice\n");
}
}while(choice != 3);
}
Void create(int item)
{
Struct node *ptr = (struct node *)malloc(sizeof(struct node *));
If(ptr == NULL)
{
Printf("\nOVERFLOW\n");
}
Else
{
Ptr->data = item;
Ptr->next = head;
Head = ptr;
Printf("\nNode inserted\n");
}
}
Void traverse()
{
Struct node *ptr;
Ptr = head;
If(ptr == NULL)
{
Printf("Empty list..");
}
Else
{
Printf("printing values . . . . .\n");
While (ptr!=NULL)
{
Printf("\n%d",ptr->data);
Ptr = ptr -> next;
}
}
}
Output
1.Append List
2.Traverse
3.Exit
4.Enter your choice?1
Enter the item
23
Node inserted
1.Append List
2.Traverse
3.Exit
4.Enter your choice?1
Enter the item
233
Node inserted
1.Append List
2.Traverse
3.Exit
4.Enter your choice?2
Printing values . . . .
233
23
Q5) What do you mean by Searching?
A5) Searching an element (Iterative approach)
1) Initialize a node pointer, temp = head
2) Do following while temp is not NULL
Temp->data is equal to the data being searched, return true.
Temp = temp->next
3) Return false
Now, let us see a program to search element in a linked list using the iterative approach.
Iterative C Program to search for an element in the Linked List
#include <stdio.h>
#include <stdlib.h>
// Creating node with data and a pointer
Struct node {
Int data;
Struct node *next;
}*head;
Void createList(int n);
Void search_element(int data);
Void displayList();
Int main()
{
Int n, data, element;
Printf("\nEnter the total number of nodes: ");
Scanf("%d", &n);
CreateList(n);
Printf("\nThe List is \n");
DisplayList();
Printf("\nEnter the element to be searched in the list : "); // value of the element to be searched in the list
Scanf("%d",&element);
Search_element(element);
Return 0;
}
Void createList(int n)
{
Struct node *newNode, *temp;
Int data, i;
Head = (struct node *)malloc(sizeof(struct node));
// When the list is empty
If(head == NULL)
{
Printf("Unable to allocate memory.");
}
Else
{
Printf("\nEnter the data of node 1: ");
Scanf("%d", &data);
Head->data = data;
Head->next = NULL;
Temp = head;
For(i=2; i<=n; i++)
{
NewNode = (struct node *)malloc(sizeof(struct node));
If(newNode == NULL)
{
Printf("Unable to allocate memory.");
Break;
}
Else
{
Printf("\nEnter the data of node %d: ", i);
Scanf("%d", &data);
NewNode->data = data;
NewNode->next = NULL;
Temp->next = newNode;
Temp = temp->next;
}}}}
Void search_element(int data)
{
Int count = 0;
Struct node* temp;
Temp = head;
While(temp != NULL) // Start traversing from head node
{
If(temp -> data == data)
{
Printf("\nElement found at position %d",count);
Break;
}
Else
{
Count = count + 1;
Temp = temp -> next;
}}
Printf("\n Element %d is not found in the list\n",data);
}
Void displayList()
{
Struct node *temp;
If(head == NULL)
{
Printf("List is empty.");
}
Else
{
Temp = head;
While(temp != NULL)
{
Printf("%d\t", temp->data);
Temp = temp->next;
}
Printf("\n");
}}
OUTPUT
Enter the total number of nodes: 4
Enter the data of node 1: 5
Enter the data of node 2: 10
Enter the data of node 3: 15
Enter the data of node 4: 20
The List is
5 10 15 20
Enter the element to be searched in the list: 10
Element found at position 1
Q6) What do you mean by Insertion?
A6) Insertion is a three- step process −
- Create a new Link with provided data.
- Point New Link to old First Link.
- Point First Link to this New Link.
//insert link at the first location
Void insertFirst(int key, int data){
//create a link
Struct node *link = (struct node*) malloc (sizeof (struct node));
Link->key = key;
Link->data = data;
//point it to old first node
Link->next = head;
//point first to new first node
Head = link;
}
Q7) What is the process of Deletion from linked list?
A7) Deletion is a two-step process −
- Get the Link pointed by First Link as Temp Link.
- Point First Link to Temp Link's Next Link.
//delete first item
Struct node* deleteFirst () {
//save reference to first link
Struct node *tempLink = head;
//mark next to first link as first
Head = head->next;
//return the deleted link
Return tempLink;
}
Q8) Describe linked representation of Stack and Queue?
A8) A Double ended queue is a queue in which elements can be inserted or deleted from either front or rear. New elements can be added at either the front or the rear. Likewise, existing items can be removed from either end. This abstract data structures often abbreviated as deque and is also known as head-tail linked list. Deques are useful when we need both random access, and ability to delete/insert at both the ends. This hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Dequeue can be categorized in two types
1) Input restricted Dequeue: It allows insertions at only one end.
2) Output restricted Dequeue: It allows deletions from only one end.
Q9) Define Header nodes?
A9) A header node is a special node that is found at the beginning of the list. A list that contains this type of node, is called the header-linked list. This type of list is useful when information other than that found in each node is needed.
For example, suppose there is an application in which the number of items in a list is often calculated. Usually, a list is always traversed to find the length of the list. However, if the current length is maintained in an additional header node that information can be easily obtained.
Types of Headers Linked List
Grounded Header Linked List
It is a list whose last node contains the NULL pointer. In the header linked list the start pointer always points to the header node. start -> next = NULL indicates that the grounded header linked list is empty. The operations that are possible on this type of linked list are Insertion, Deletion, and Traversing.
Q10) Describe Doubly linked list?
A10) Construction of doubly linked list:
Fig.: Doubly Linked List
Fig. Shows an example of a doubly linked list. Assume Our Doubly Linked List contains 3 nodes and let us denote it by A, B, and C.
Node A starts at memory address 1000.It does not have any predecessor node so left link points to NULL. Data field contains integer value ‘10’. Right Link of node in doubly linked list always stores memory address of its successor node. Hence right link of node A contains 2000 i.e., memory address of node B.
Left Link of node in doubly linked list contains memory address of predecessor node. A is predecessor node of B so left link of B contains 1000 i.e., memory address of A. Data field contains value’20’ and right link contains 3000 i.e., memory address of node C.
Same strategy is applied for all nodes in doubly linked list.
Node in doubly linked list is defined as
Typedef struct node
{
Int data;
Struct node *next, *prev;
} node;
Node is defined as self-referential structure which contains one data field denoted as ‘data’ and two pointers ‘*next’, ‘*prev’. *next points to successor node and *prev points to predecessor node.
Q11) Write a Program to create and display doubly linked lists?
A11) Program to create and display doubly linked list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
Typedef struct node
{
Int data;
Struct node *next,*prev;
}node;
Node *create();
Void display(node*);
Void main()
{
Node *head;
Head= NULL;
Head=create();
Printf(“Elements of Doubly Linked List”);
Display(head);
}
Node *create()
{
Node *p, *q, *r;
Int i,n,x;
p=NULL;
Printf(“Enter number of elements”);
Scanf(“%d”,&n);
For(i=0;i<n;i++)
{
Printf(“Enter data”);
Scanf(“%d”,&x);
r= (node*)malloc(sizeof(node));
r->data=x;
r->prev=q->next=NULL;
If(p==NULL)
q=p=r;
Else
q->next=r;
r->prev=q;
q=r;
}
Return(p);
}
Void display()
{
While(p!=NULL)
{
printf(“ %d ”, p->data);
p=p->next;
}
}
Q12) Explain operations on the Doubly Linked list in Node of Insertion?
A12) Insertion of Node
Node can be inserted in doubly linked list at 3 positions.
(A) At the beginning
(B) In the middle
(C) At the end
Algorithms:
Assume node to be inserted is pointed by P.
(A) Insertion of node at the beginning of Doubly Linked List
Suppose our DLL consists of 3 nodes.
Insertion can be done in following steps
1. Allocate memory to node pointed by P
P= (node*) malloc(sizeof(node))
2. Update the next pointer of the node P to the Head node and make prev pointer as
NULL
P->next=Head
P->prev= NULL
3. Now update Head node’s prev pointer to point to node P and make node P as head node.
Head->prev=P
P = Head
Insertion of node in the middle of Doubly Linked List
To insert a node in the middle of DLL we must know the data value of node after which node is to be inserted. Once we get the data value of node, traverse to that node.
Let us represent data value in a node by variable ‘data’ and value of node after which new node is to be inserted is ‘val’. Suppose we want to insert new node after 2nd node.
2. Initially Q points to first node.
Traverse to the node after which node is to be inserted.
While (Q! =NULL)
{
If(Q->data==val)
Break;
Q=Q->next
}
Now Q points to 2nd node.
P
Make the next pointer of node P to point to node next to Q. Also make the prev point of node P to point to node 2nd node.
P->next=Q->next
P->prev=Q
Now point Q’s next to P
Q->next=P
Insertion of node at the last of Doubly Linked List
1. Traverse the list to end.
Q=Head
While(Q->next! =Null)
Q=Q->next
2. Update next pointer of Q to point to P.
Q->next=P
3. Make next pointer of P to point to NULL and prev pointer to point to Q
P->prev=Q
P->next=NULL
Q13) Explain operations on the Doubly Linked list in Node of Deletion?
A13) Deletion of Node from DLL
Node can be deleted from doubly linked list at 3 positions
(A) At the beginning
(B) In the middle
(C) At the end
Algorithms:
(A) Deletion of node from the beginning of Doubly Linked List
Assume P points to node to be deleted.
1. P and Head points to the first node in DLL.
2. Now move the Head pointer to point to the next node. Also change the Head’s prev and P’s next to NULL. Then dispose the node pointed by P.
(B) Deletion of node from the middle of Doubly Linked List
To delete a node in the middle of DLL we must know the data value of node after which node is to be deleted. Once we get the data value of node, traverse to that node.
Let us represent data value in a node by variable ‘data’ and value of node after which new node is to be inserted is ‘val’. Suppose we want to delete 3rd node
1. Initially P and Head points to first node.
2. Traverse to the node after which node is to be deleted.
While (P! =NULL)
{
If(P->data==val)
Break;
Q=P;
P=P->next
}
Now Q points to 2nd node and P points to 3rd node i.e., node to be deleted.
3. Set next of Q to next of P and prev of next of P to Q.
P->next=Q->next
P->next->prev=Q
Dispose P.
Free(P)
(c) Deletion of node from the end of Doubly Linked List
1. Position pointer Q to the node previous to P. In order to find this position, list should be traversed first, beginning from the head.
Q=Head
While(Q->next->next! =NuLL)
Q=Q->next
P=Q->next
2. Set next link of the Q and prev link of P to NULL.
Q->next=NuLL
3. Dispose of the Last Node.
Free(P)
Q14) Describe the reverse of Doubly linked List?
A14) C Function to reverse a doubly linked list:
Void reverse (node *head)
{
Node *p;
If (head! =NULL)
{
For (p=head; p->next! =NULL; p=p->next)
{
For (; p! =NULL; p=p->prev)
Printf (“%c”, p->data);
}
}
}
Analysis is the theoretical way to study performance of computer program. Analysis of an algorithm is helpful to decide the complexity of an algorithm.
Q15) Describe the Circular Linked List?
A15)
A circular linked list is a linked list in which last node points to first node i.e., next pointer of last node points to first node. Circular linked list does not contain NULL pointers.
Here A is the first node and C is the last node. C points to A and hence C stores address of A.
Operations On Circular Linked List
1. Insertion of a node
2. Deletion of a node
3. Traversing
Insertion of a node
Node can be inserted at 3 positions i.e., at the beginning, in the middle and at the end of circular linked list.
Insertion at the beginning:
Assume node to be inserted is pointed by P. Insertion can be done in following steps.
1. Position pointer Q to the last node of CLL. For this traverse the list to the end of list.
Q=Head
While(Q->next! =NULL)
Q=Q->next
2. Set next link of Q to P and next link of P to Head of CLL.
Q->next=P
P->next=Head
3. Make P as Head of CLL
Head=P
Insertion in the middle
Insertion of node in the middle of CLL is same as that of Singly linked List.
Insertion at the end
1. Position pointer Q to the last node of CLL. For this traverse the list to the end of list.
Q= Head
While(Q->next! =Head)
Q=Q->next
2. Set next link of Q to P and next link of P to Head.
P= Q->next
Head= P->next
Deletion Of Node from Cll
Node can be deleted at the beginning, from the middle and end of CLL.
Deletion at the beginning
Assume node to be deleted is pointed by P. Deletion can be done in following steps.
1. Position pointer P to point to Head Node and Q to the last node.
P=Q= Head
While(Q->next! =Head)
Q=Q->next
2. Position pointer Head to the next of P. Set next link of Q to point to new Head.
Head=Head->next
Head= Q->next
3. Dispose P.
Free(P)
Deletion in the middle of CLL
Deletion of node in middle of CLL is same as that of Singly linked list.
Deletion at the end of CLL
1. Position pointer Q to last but one node of CLL.
Q=Head
While(Q->next->next! =Head)
Q=Q->next
2. Set next link of Q to Head and P to NULL. Dispose P.
Q->next=Head
Free(P)
3. Set next link of Q to Head and P to NULL. Dispose P.
Q->next=Head
Free(P)
Q16) Write a Program to create add remove & display element from circular linked list?
A16) Program to create, add, remove and display element from circular linked list
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
Struct node
{
Int data;
Struct node *next;
};
Struct node *head=NULL;
Struct node *tail=NULL;
Void main()
{
Void addrecord();
Void deleterecord();
Void disrecord();
Int ch;
Clrscr();
Do
{
Printf("\n 1. To add records\n");
Printf("\n 2. To delete a records\n");
Printf("\n 3. To view the records\n");
Printf("\n 4. To exit\n");
Printf("\n Enter your choice\n");
Scanf("%d",&ch);
Fflush(stdin);
switch(ch)
{
Case 1:addrecord();
Break;
Case 2:deleterecord();
Break;
Case 3: disrecord();
Break;
Case 4:exit(0);
}
} while (ch!=4);
}
Void addrecord()
{
Int new_data;
Char ans='y';
Struct node *ptr,*prev,*temp;
Clrscr();
While (ans=='y')
{
Temp=(struct node*)malloc(sizeof(struct node));
Printf("\n Enter the new element:\n");
Scanf("%d",&new_data);
Fflush(stdin);
Temp->data=new_data;
Temp->next=NULL;
If (head==NULL)
{
Head=tail=temp;
Temp->next=head;
}
Else
{
Tail->next=temp;
Tail=temp;
}
Printf("\n Would you like to enter another data(y\\n): \n");
Ans = getchar();
Fflush(stdin);
}
}
Void deleterecord()
{
Struct node *ptr,*prev,*delnode;
Int elt;
Printf("\n Enter the enrollment number to be deleted \n");
Scanf("%d",&elt);
Fflush(stdin);
If (head==NULL)
{
Printf("\n No elements in the list \n");
Return;
}
Else
{
If (head->data==elt)
{
Delnode=head;
If (head==tail)
Head=tail=NULL;
Else
{
Head=head->next;
Tail->next=head;
}
}
Else if (tail->data==elt)
{
For(ptr=head;(ptr!=tail);prev=ptr,ptr=ptr->next);
Delnode=tail;
Tail=prev;
Tail->next=head;
}
Else
{
For(prev=ptr=head;(ptr->data!=elt)&&(ptr!=tail);
Prev=ptr,ptr=ptr->next);
If(ptr->data==elt)
{
Delnode=ptr;
Prev->next=ptr->next;
Printf("yes...");
}
Else
{
Printf("Given element not found in the list");
Getch();
Return;
}
}
}
Free(delnode);
}
Void disrecord()
{
Struct node *ptr,*prev=NULL;
If (head==NULL)
{
Printf("\n No records to view\n");
Return;
}
Printf("\n The elements in the circular list are\n");
For (ptr=head;prev!=tail;prev=ptr,ptr=ptr->next)
Printf("\n\n %d",ptr->data);
Printf(" NULL\n\n ");
Getch();
}
Q17) Write the application of linked list?
A17) The following are some of the applications of the linked list:
● Polynomials can be represented and operations on polynomials can be performed with the help of a linked list.
● The sparse matrix can be represented using a linked list.
● The linked list can be used to implement many processes such as student details, employee details, or product details since it employs the structural data type, which can carry a variety of data types.
● Stack, queue, tree, and other data structures can all be implemented using linked lists.
● The graph is made up of edges and vertices, and it can be represented as an adjacency matrix or a list of adjacencies. The graph can be implemented as an array if we want to express it as an adjacency matrix. The graph can be represented as a linked list if we want to express it as an adjacency list.
● To implement dynamic memory allocation, a linked list can be utilised. The memory allocation done at run-time is known as dynamic memory allocation.
Q18) Write the advantages of linked lists?
A18) The following are some of the benefits of using a linked list:
● Dynamic data structure - The linked list's size can change depending on the requirements. The size of a linked list is not fixed.
● Insertion and deletion are more easier in linked lists than they are in arrays. The items of an array are stored in a sequential order, whereas the elements of a linked list are stored in a random order. To add or remove an element from an array, we must first shift the elements to make room. Instead of shifting, we only need to update the address of the node's pointer in a linked list.
● Memory efficient - Because the size of a linked list can increase or shrink depending on the requirements, linked list memory usage is low.
● Implementation - Linked lists can be used to implement both stacks and queues.
Q19) Write the disadvantages of linked lists?
A19) The following are some of the drawbacks of utilising a linked list:
● Memory use - In a linked list, the node takes up more space than the array. Each node in the linked list has two sorts of variables, one of which is a simple variable and the other of which is a pointer variable.
● Traversal - In a linked list, traversal is difficult. If we need to access an element in a linked list, we can't do so randomly, but an array can be accessed randomly by index. For example, if we want to go to the third node, we must first go through all of the nodes that come before it. As a result, accessing a certain node takes a long time.
● Reverse traversing - In a linked list, backtracking or reverse traversing is difficult. The back pointer is easier to keep in a doubly-linked list, but it takes up more memory.
