Page 50 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 2: Linked Lists

This program appends a new node to the existing list (that is, it inserts a new node in the existing Notes

list at the end), and it makes the link field of the newly inserted node point to the start or fi rst
node of the list. This ensures that the link field of the last node always points to the starting node

of the list.
2.9 Sorting and Reversing a Linked List

To sort a linked list, first we traverse the list searching for the node with a minimum data value.
Then we remove that node and append it to another list which is initially empty. We repeat this
process with the remaining list until the list becomes empty, and at the end, we return a pointer
to the beginning of the list to which all the nodes are moved, as shown in Figure 2.7.

Figure 2.7: Sorting of a Linked List
NULL
5 10 3 7

start
List to be sorted
5 10 7
NULL
start
q 3 NULL
After the first pass

To reverse a list, we maintain a pointer each to the previous and the next node, then we make the

link field of the current node point to the previous, make the previous equal to the current, and
the current equal to the next, as shown in Figure 2.8.
Figure 2.8: A Linked List Showing the Previous, Current, and Next Nodes at
some Point during Reversal Process

NULL

prev curr next

Therefore, the code needed to reverse the list is:
Prev = NULL;
While (curr != NULL)
{
Next = curr->link;
Curr -> link = prev;
Prev = curr;
Curr = next;
}
2.10 Merging two Sorted Lists

Merging of two sorted lists involves traversing the given lists and comparing the data values
stored in the nodes in the process of traversing.

LOVELY PROFESSIONAL UNIVERSITY 45