DS Unit 5 Notes

Unit –5 linked list
(2 & 4 MARKS Questions)

1) Explain the concept of information, Next, Null Pointer and empty list with respect to link list.(each term 1M)
Ans:
a. Info Field: It is used to store data inside the node.
b. NEXT: It is used to store reference of next element in the list.
c. Null Pointer: It is used to specify end of the list. The last element of list
contains NULL pointer to specify end of list.
d. Empty List: A linked list is said to be empty if head (start) node contains
NULL pointer.
OR
1) Define the term: (Each definition -1 Mark)
i) Node ii) Address iii) Null pointer iv) Next pointer for linked list.
Ans:
i) Node: A node of a tree is an item or information along with the branches to other nodes
ii) Address: Address indicates location of node
iii) Null pointer: A linked field of the last node contains Null rather than a valid address it indicates end of the list
iv) Next Pointer for Linked list: Which Hold the Address of the next node, which intern links the nodes together.

2) Explain the concept of linear list with example. (Explain–3M,Diagram 1M)
Ans:
1. Linked list is a data structure consisting of a group of nodes which together represent a sequence.
2. Each node is composed of a data and a link to the next node in the sequence; more complex variants add additional links.
3. This structure allows for efficient insertion or removal of elements from any position in the sequence.

linkedlist1

2) Explain insertion of new node at start and at end in singly linked list. (Explanation of insertion at start- 2Marks, At end- 2Marks)
Ans: Inserting node at start in the SLL (Steps):
1. Create New Node
2. Fill Data into “Data Field“
3. Make it’s “Pointer” or “Next Field” as NULL
4. Attach This newly Created node to Start
5. Make new node as Starting node
insertsll
Inserting node at last in the SLL (Steps):
1. Create New Node
2. Fill Data into “Data Field“
3. Make it’s “Pointer” or “Next Field” as NULL
4. Node is to be inserted at Last Position so we need to traverse SLL up to Last Node.
5. Make link between last node and new node

insertlastsll

3) Write an algorithm to insert a node in between in a link list. (4 marks)
Ans:
Algorithm to insert an element insert a node in between in a link list.
void add_at_specified(struct node *q, int loc, int no)
{
Step 1: – Begin
Step 2: – Allocate memory for temp node and new node (r);
set r->info = no
Step 3:- Initialize temp to the beginning of the linked list.
Step 4:- Traverse temp till the previous node of the specified location given by loc in the linked list (Previous node = temp node)
Step 5: – Set r->next = temp-next; Set temp->next = r;
Step 6 : – Stop
}

4) Write an algorithm to insert a new node at the beginning of a singly linked list. Give example.(Algorithm – 2 Marks, Example – 2 Marks)
[Note: Appropriate steps describing procedure for inserting shall be considered.]
Ans: In this operation, new node can be created and added at the beginning of a list.
New node points to existing first node and start points to newly added node.
Algorithm:-
Step 1:- Create a new node as temp.
Step 2:- Set temp node’s info field.
Step 3:- set temp node’s link field with address stored in start node.
Step 4: set temp node as start node.

beginingsll

5) Explain with suitable diagram how to delete a node from singly linked list at the start and end of the list.
(NOTE: Examiner should consider the logic behind the algorithm. It may vary according to books, knowledge.)
Ans:
Singly linked list : Each node in this list contains only one pointer which points to the next node of the list.
Deletion of a node: Deletion from a list may be done either position wise or element wise.
For deleting an element, we have to locate the node at that position and free the node after making appropriate links.
Deletion of an element can be done in two ways.

deletesll
Deletion from the beginning:(2 marks)
Temp = list;
List = temp -> next;
Free (temp);
Assign first element as a pointer of the first element.
Release memory by using free function.
Deleting the last element:
Temp1 = temp -> next;
Temp -> next = NULL;
Free(temp1);
Removing a node from the end requires that the preceding node becomes the
new end of the list (i.e., points to nothing after it)

deletelastsll

6) WAP to search an element in a link list.(Program–4M, any relevant program)
Ans: Code for searching an element in a list
void search(struct node *head, int key)
{
while (head != NULL)
{
if (head->a == key)
{
printf(“key found\n”);
return;
}
head = head->next;
}
printf(“Key not found\n”);
}
Where *head gives the first element of list;
Key gives the element to be searched in a list.

7) With suitable diagram, explain ‘searching’ of a node in a linked list. (Explanation -2Marks, example/diagram- 2Marks)
Ans:
Algorithm
Step-1: Initialize the Current pointer with the beginning of the List.
Step-2: Compare the KEY value with the Current node value;
if they match then quit there else go to step-3.
Step-3: Move the Current pointer to point to the next node in the list and
go to step-2, till the list is not over or else quit.
Example:-

sll

8) Describe doubly linked list with its node structure.
(Description- 2Marks, Node structure- 2Marks)
Ans: Description:-
Doubly linked list is also called as two way linked list.
The advantage of doubly linked list is that it allows traversal in both the direction throughout the list.
Each node contains 3 fields:-
• Info field is used to store data.
• A Pointer field next which contains pointer to next node.
• A pointer field previous which contains pointer to previous node
Node structure:-

nodestructure

9) Write an algorithm for ‘search’ operation in an unsorted linked list. (Algorithm – 4 Marks; any other logic shall be considered)
[Note: Appropriate steps describing procedure for searching shall be considered.]
Ans: Algorithm: SEARCH (INFO, NEXT, START, ITEM, LOC)
This algorithm finds ITEM first appears in linked list or sets LOC=NULL
1. Set PTR: =START.
2. Repeat Step 3 while PTR! =NULL
3. If (PTR->INFO == ITEM),
then:
PRINT: SEARCH IS SUCCESSFUL and Exit
Else:
Set PTR: =PTR->NEXT [PTR now points to the next node] [End of If structure] [End of Step 2 loop] 4. [Search is unsuccessful.] set LOC:=NULL.
5. Exit.

10) Describe doubly linked list with an example.(Description-2M,Example-2 M)
Ans:
 In Doubly-linked list each node contains two links- one to the previous node and other to the next node.
 The previous link of the first node and the next link of the last node points to NULL.
 In Doubly linked list, a node comprises of total three fields
1) prev, a pointer holding the address of previous node in the list
2) data, the information part
3) next, a pointer holding the address of next node in the list
A generic doubly linked list node can be designed as:
struct node
{
int data;
struct node* next;
struct node* prev;
};
EXAMPLE:
doublylinkedlist

11) Describe doubly linked list with an example. (Explanation 3m & example 1m)
Ans:
A doubly linked list is a linked list in which each node contains two links- one pointing to the previous node and pointing to the next node.
Each node contains three parts.

doubly
1. Data: contains information. E.g.10, 20, etc.
2. Next pointer: Contains address of the next node
3. Prev pointer: Contains address of the preceding node.
 In doubly linked list, traversal is done in both the directions, storage
requirements is more because every node has two pointers.
 Insertion and deletion can be easily performed.
 Searching an element is faster.
 It is used for applications like dynamic storage management, where extensive traversal and manipulations are required.

The structure defined for doubly linked list is-
Struct node
{
int data;
Struct node *next, * prev;
} ;
Operations performed on doubly linked list are:
1. Creating a doubly linked list.
2. Inserting a node at the beginning
3. Inserting a node in between(specified position)
4. Inserting a node at the end.
5. Deleting the node.

12) Explain how to delete a node in linked list.(Any 1 deletion explanation 4 M)
Ans: There are three cases, which can occur while removing the node.
i) Remove first
In this case, first node (current head node) is removed from the list.

removefirst
ii) Remove last
In this case, last node (current tail node) is removed from the list.
This operation first finds previous node of last node.

removelast
iii) Remove in between
In general case, node to be removed is always located between two list nodes.
Head and tail links are not updated in this case.

removeinbetween

Leave a Reply

Your email address will not be published. Required fields are marked *