.png)
Mobiprep has created last-minute notes for all topics of Linked List to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Linked List.
Data Structure
Linked List
Doubly Linked List
Circular Linked List
Queues
Stacks
Hashing and Searching
Sorting
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
What is Linked Lists? What are different operations on Linked Lists?
Explain Insertion operation at the beginning of singly linked list.
Explain Insertion operation at nth position before a node of singly linked list.
Explain Insertion operation at nth position after a node of singly linked list.
Explain Insertion operation at the end of singly linked list.
Explain deletion operation at the beginning of singly linked list.
Explain deletion operation at nth position after a node of singly linked list.
Code implementation of various operations on singly linked list.
Question 1 - Discuss Linked Lists with its advantages and disadvantages.
Answer - Linked list is a type of linear data structure used to store value. Unlike many other data structures, the data stored in the linked list does not store in continuous memory location which provides linked list an upper hand in efficient working.
Advantages of linked list:
Linked list is a dynamic data structure that grows and shrink as per the allocation of data.
As linked list do not have continuous memory allocation thus inserting elements and deleting elements from the linked list is easier.
As linked-list can shrink during runtime allocation thus there is no memory wastage.
Other data structures like Stack, queue can be easily implemented using linked list.
Disadvantages of linked list
Linked list uses more memory as it has data as well as address of other node present in it
We cannot directly access an element from the linked list. For accessing an element, we have to traverse through the list.
Reversing a linked list is a cumbersome and tedious work.
Question 2 - What is Linked Lists? What are different operations on Linked Lists?
Answer - Linked list is a type of linear data structure used to store value. Unlike many other data structures, the data stored in the linked list does not store in continuous memory location which provides linked list an upper hand in efficient working.
Operations performed in the linked list are as follow:
Add node - We can add nodes at various positions in the linked list like in the beginning or at the end or even before or after a specific node.
Delete node - Similar to addition of nodes, we can also delete nodes from various positions in a linked list like deleting the first node, last node or a node before or after a specific node.
Traverse list - Traversing a list means moving in the list, visiting various nodes and performing various operations.
Length of list - We can calculate the length of the linked list which can be used for various purposes while dealing with the list.
Question 3 - Differentiate between Linked List and Array.
The element allocation in a list takes place during run time whereas in case of array it happens in compile time.
Array has a continuous memory allocation whereas linked lists store the data randomly.
Insertion and deletion are more efficiently done in list then array
Array uses less memory as compared to list.
In array the elements can be accessed directly whereas in linked list it is in sequence
Question 4 - Why do we need pointers in Linked List?
As in list the elements are not stored continuously and every node in a linked list contains the address of the next node. Thus, pointers are required in order to access the next memory location.
In singly linked list we need one pointer to access the next memory allocation but in doubly linked we use two pointers as each node holds the address of next as well as previous mode.
Singly Linked list
Singly linked list is the most basic linked data structure. In this the elements can be placed anywhere in the heap memory unlike arrays which use contiguous locations. Nodes in a linked list are linked together using a next field, which stores the address of the next node in the next field of the previous node i.e. each node of the list refers to its successor and the last node contains the NULL reference. It has a dynamic size, which can be determined only at run time.
Question 5 - Explain Insertion operation at the beginning of singly linked list.
Answer - Pseudo Code:
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET NEW_NODE🡪 DATA = VAL
Step 5: SET NEW_NODE🡪 NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT
Question 6 - Explain Insertion operation at nth position before a node of singly linked list.
Answer - Pseudo code:
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET = AVAIL
Step 3: SET AVAIL = AVAIL 🡪NEXT
Step 4: SET NEW_NODE 🡪DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR 🡪DATA! = NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR🡪 NEXT
[END OF LOOP]
Step 10: PREPTR🡪 NEXT = NEW_NODE
Step 11: SET NEW_NODE 🡪NEXT = PTR
Step 12: EXIT
Question 7 - Explain Insertion operation at nth position after a node of singly linked list.
Answer - Pseudo code:
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET = AVAIL
Step 3: SET AVAIL = AVAIL🡪 NEXT
Step 4: SET NEW_NODE🡪 DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR🡪 != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR🡪 NEXT
[END OF LOOP]
Step 10: PREPTR🡪 NEXT = NEW_NODE
Step 11: SET NEW_NODE🡪 NEXT = PTR
Step 12: EXIT
Question 8 - Explain Insertion operation at the end of singly linked list.
Answer - Pseudo code:
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL🡪 NEXT
Step 4: SET NEW_NODE 🡪DATA = VAL
Step 5: SET NEW_NODE🡪NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR 🡪NEXT! = NULL
Step 8: SET PTR = PTR🡪 NEXT
[END OF LOOP]
Step 9: SET PTR🡪 NEXT = NEW_NODE
Step 10: EXIT
Question 9 - Explain deletion operation at the beginning of singly linked list.
Answer - Pseudo code:
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START🡪 NEXT
Step 4: FREE PTR
Step 5: EXIT
Question 10 - Explain deletion operation at nth position after a node of singly linked list.
Answer - Pseudo code:
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 1
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR🡪 DATA! = NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR 🡪NEXT
[END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR 🡪NEXT = PTR🡪 NEXT
Step 9: FREE TEMP
Step 10: EXIT
Question 11 - Deletion operation at the last of the list.
Answer - Pseudo code:
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR NEXT! = NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR🡪 NEXT
[END OF LOOP]
Step 6: SET PREPTR🡪 NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT
Question 12 - Code implementation of various operations on singly linked list.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *create_ll(struct node *);
struct node *display(struct node *);
struct node *insert_beg(struct node *);
struct node *insert_end(struct node *);
struct node *insert_before(struct node *);
struct node *insert_after(struct node *);
struct node *delete_beg(struct node *);
struct node *delete_end(struct node *);
struct node *delete_node(struct node *);
struct node *delete_after(struct node *);
struct node *delete_list(struct node *);
struct node *sort_list(struct node *);
int main(int argc, char *argv[]) {
int option;
do
{
printf("\n \n *****Main Menu ****");
printf("\n 1: Create a list");
printf("\n 2: Display the list");
printf("\n 3: Add a node at the beginning");
printf("\n 4: Add a node at the end");
printf("\n 5: Add a node before a given node");
printf("\n 6: Add a node after a given node");
printf("\n 7: Delete a node from the beginning");
printf("\n 8: Delete a node from the end");
printf("\n 9: Delete a given node");
printf("\n 10: Delete a node after a given node");
printf("\n 11: Delete the entire list");
printf("\n 12: Sort the list");
printf("\n 13: EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1: start = create_ll(start);
printf("\n LINKED LIST CREATED");
break;
case 2: start = display(start);
break;
case 3: start = insert_beg(start);
break;
case 4: start = insert_end(start);
break;
case 5: start = insert_before(start);
break;
case 6: start = insert_after(start);
break;
case 7: start = delete_beg(start);
break;
case 8: start = delete_end(start);
break;
case 9: start = delete_node(start);
break;
case 10: start = delete_after(start);
break;
case 11: start = delete_list(start);
printf("\n LINKED LIST DELETED");
break;
case 12: start = sort_list(start);
break;
}
}while(option !=13);
getch();
return 0;
}
struct node *create_ll(struct node *start)
{
struct node *new_node, *ptr;
int num;
printf("\n Enter -1 to end");
printf("\n Enter the data : ");
scanf("%d", &num);
while(num!=-1)
{
new_node = (struct node*)malloc(sizeof(struct node));
new_node -> data=num;
if(start==NULL)
{
new_node -> next = NULL;
start = new_node;
}
else
{
ptr=start;
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next = new_node;
new_node->next=NULL;
}
printf("\n Enter the data : ");
scanf("%d", &num);
}
return start;
}
struct node *display(struct node *start)
{
struct node *ptr;
ptr = start;
while(ptr != NULL)
{
printf("\t %d", ptr -> data);
ptr = ptr -> next;
}
return start;
}
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = start;
start = new_node;
return start;
}
struct node *insert_end(struct node *start)
{
struct node *ptr, *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = NULL;
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
return start;
}
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr, *preptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value before which the data has to be inserted : ");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = new_node;
new_node -> next = ptr;
return start;
}
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr, *preptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value after which the data has to be inserted : ");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
preptr = ptr;
while(preptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next=new_node;
new_node -> next = ptr;
return start;
}
struct node *delete_beg(struct node *start)
{
struct node *ptr;
ptr = start;
start = start -> next;
free(ptr);
return start;
}
struct node *delete_end(struct node *start)
{
struct node *ptr, *preptr;
ptr = start;
while(ptr -> next != NULL)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
return start;
}
struct node *delete_node(struct node *start)
{
struct node *ptr, *preptr;
int val;
printf("\n Enter the value of the node which has to be deleted : ");
scanf("%d", &val);
ptr = start;
if(ptr -> data == val)
{
start = delete_beg(start);
return start;
}
else
{
while(ptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = ptr -> next;
free(ptr);
return start;
}
}
struct node *delete_after(struct node *start)
{
struct node *ptr, *preptr;
int val;
printf("\n Enter the value after which the node has to deleted : ");
scanf("%d", &val);
ptr = start;
preptr = ptr;
while(preptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next=ptr -> next;
free(ptr);
return start;
}
struct node *delete_list(struct node *start)
{
struct node *ptr; // Lines 252-254 were modified from original code to fix
if(start!=NULL){
ptr=start;
while(ptr != NULL)
{
printf("\n %d is to be deleted next", ptr -> data);
start = delete_beg(ptr);
ptr = start;
}
}
return start;
}
struct node *sort_list(struct node *start)
{
struct node *ptr1, *ptr2;
int temp;
ptr1 = start;
while(ptr1 -> next != NULL)
{
ptr2 = ptr1 -> next;
while(ptr2 != NULL)
{
if(ptr1 -> data > ptr2 -> data)
{
temp = ptr1 -> data;
ptr1 -> data = ptr2 -> data;
ptr2 -> data = temp;
}
ptr2 = ptr2 -> next;
}
ptr1 = ptr1 -> next;
}
return start; // Had to be added
}
댓글