Linked List
Q. 29 What are linked lists ? Show a liked list with suitable example having six nodes with properly labelled diagram.
(Mar. 2002,04,05,06,07,08,13,14,15; Oct. 2003,07)
OR
With suitable example, show labelled diagram for link between two nodes having the information part and next pointer field.
Ans. : i) i) A linked list is a linear collection of data elements, called nodes, where the linear order maintained with the help of pointers.
ii) Linked list is also called as one-way list.
iii) Each node in the linked list is divided into two parts. First part is called as INFO per which contains the information about the element or actual element and second par
called as LINK part, which is next pointers field i.e. it contains the address of next node the list.
Image📝
(a) The above figure shows a linked list having six nodes.
(b) The left part of the node is the Info part, which contains information of the element, With the right part is Link part, which is next pointers field ie. it points to next node.
(c) An arrow is drawn from Link part of one node to the next node to indicate link
(d) The address of the list is stored in Start or Name of the list.
(e) The Link part of last node is NULL pointer ie. it contains nothing.
(f) To trace the linked list, we Just equine the address ot Start or Name.
Q 30 ) What are Hie advantages of linked lists over linear arrays ?
Ans : Advantages of linked lists over arrays :
i) To store arrays in memory, require consecutive memory locations, while to store linked lists. consecutive memorv locations are not required.
ii) Arrays can not be easily extended, while linked list can be easily extended.
ii) There is very complicated procedure to insert an element in an array. One can easily insert an element in an linked list.
(iv) Similary, deletion of an element from array is very complicated, while deletion from linkedlist iS easy.
(v) Linked lists can be easily implemented and maintained in computer memory.
Q. 31 How linked lists are represented in memory ?
OR (March 2003,12,14; Oct. 2006, 07,13)
With suitable example show the representation of linked list in memory.
Ans :
i) Linked lists can be represented in memory by using two arrays respectively known as INFO
and LINK, such that INFO[K] and LINK[K] contains information of element and next node address respectively.
ii) The list also requires a variable ‘Name’ or ‘Start’, which contains address of first node.
Pointer field of last node denoted by NULL which indicates the end of list. e.g. Consider a linked list given below :
Image📝
iii) The linked list can be represented in memory as –
Image 📝
Above figure shows linked list. It indicates that the node of a list need not occupy adjacent elements in the array INFO and LINK.
Q. 32 Explain insertion and deletion from linked list with example.
Ans. : It is easier to insert an element into or delete an element from a linked list than arrays.
(i) Insertion into a linked list :
For insertion of an element into a linked list, the only requirement is that free memory space is available to store a node.
e.g. Consider a linked list having four nodes as follows.
Image📝
This list can be represented in memory as :
Image 📝
Now, to insert an element on second position of the list, the content of AVAIL are stored in LINK part of first node (since, AVAIL points to the memory location where new node can be inserted) and LINK part of the first node is transferred to LINK part of new node. Then the list can be represented as follows.
Image 📝
This list can be represented in memory as :
Image📝
(ii) Deletion from linked list :
To delete a node from a linked list, the LINK part of that node is given to the LINK part of the previous node.
e.g. Consider a linked list as follows :
Image📝
This list can be represented in memory as :
Image📝
Now, to delete second node from the list, then just transfer the LINK part of second node to the LINK part of the first node.
Image📝
This list can be represented in memory as
Image📝
Q. 33 There is a list of 5 hospital patients and their corresponding room numbers. Fill the
values of N start and N link so that they form an alphabetical link of patient names. Also
fill the values of R start and R link so that they form an ordering of room numbers.
Image📝
Q. 34 The following figure pictures a linked list in memory.
Image📝
(i) Find the sequence of characters in the list.
(ii) Suppose F and then C are deleted from the list. After that G is inserted at the beginning of the list. Find the final structure of the list.
(iii) Suppose G is inserted at the beginning of the list and then F after that C is deleted from the list. Find the final structure of the list.
Ans:
i) Linear order of characters
START = 4 so INFO [4] = C is the first character
LINK [4] = 7 so INFO [7] = E is the second character
LINK [7] = 1 so INFO [1] = A is the third character
LINK [5] = 0, the NULL value so the list is ended.
C E A B FD is the character string. Hence sequence is C, E, A, B, F, D.
Image📝
Q. 35 Let LIST be a linked list in memory. Write an algorithm for traversing the linked list following purposes :
(i) Find the number of times given ITEM occurs in the list.
(ii) Find number of non-zero elements in the list.
(iii) Add given value K to each element of the list.
Ans. : Algorithm : Traversing a linked list
- Set Ptr = START
- Repeat While Ptr ≠ NULL :
Apply process to INFO[Ptr]
Set ptr := LINK [ptr]
[End of loop] - Exit (i) 1. Set Ptr = START
- Set N = 0
- Repeat steps 4 and 5 While Ptr # NULL :
- If INFO [ptr] = ITEM, Then :
setN =N+1
[End of If structure]
- Set Ptr = LINK [ptr]
[End of step 3 loop] - Write : N
7.Exit
(ii) 1. Set Ptr := START
2. Set N := 0
- Repeat steps 4 and 5 While Ptr # NULL :
- If INFO [Ptr] ≠ 0, Then :
Set N:=N+1
[End of If structure] - Set Ptr := LINK [Ptr]
[End of step 3 loop] - Write : N
- Exit
(iii) 1. Set Ptr := START
2. Repeat While Ptr # NULL :
Set INFO [Ptr] := INFO [Ptr] + K
Set Ptr := LINK [Ptr]
[End of loop]
3. Exit