CS 357 Program: Linked List - Natural Merge The purpose of this assignment is to
ID: 671618 • Letter: C
Question
CS 357 Program: Linked List - Natural Merge
The purpose of this assignment is to give you experience manipulating linked lists.
You are given a linked list. You will write and test a subprogram that will identify the first two ordered sequences of keys at the beginning of the list, and then merge them together. For example, suppose the given list is named list1 and is as follows.
list1
12 16 16 35 67 13 16 40 38
9.6 7.2 4.8 1.0 5.3 2.9 5.0 6.7 2.4
The integer values 12, 16, etc. are the iData values in Lafore’s Link class on page 185, and the double values 9.6, 7.2, etc. are the dData values. Note that the keys in Lafore’s class are the iData values; dData is just another instance variable that tags along as part of the object but is never searched for.
The first ordered sequence of keys is {12, 16, 16, 35, 67}. It ends when we find a key (13) that is less than the previous key (67). The second ordered sequence is {13, 16, 40}. It ends when we find a key (38) that is less than the previous key (40). After we merge the two sequences, list1 will be
list1
12 13 16 16 16 35 40 67 38
9.6 2.9 7.2 4.8 5.0 1.0 6.7 5.3 2.4
We now have one ordered sequence of eight nodes, where previously we had two ordered sequences of five nodes and three nodes, respectively.
It is required that any two nodes in the final list that have the same key value must be in the same relative order that they were in the original list. That is, the three nodes (16, 7.2), (16, 4.8) and (16, 5.0) in the original list all have the same key (16), so they must be in the same relative order in the final list as in the original list, and they are. This is easily achieved and is useful if we are writing a merge sort subprogram and we want the sorting algorithm to be stable, meaning it preserves the relative order of nodes with equal keys, which is often a good property for a sorting algorithm to have.
One possible way to organize the subprogram is as follows.
1) Scan from the beginning of the list to find the last node in the first sequence. “Remember” where this node is, either by storing a copy of the address of that node, or by storing the number of nodes in the first sequence, or by some other method.
2) Scan from the end of the first sequence to find the last node in the second sequence. “Remember” where this node is.
3) Now scan the two sequences together, in one loop, removing each node in the second sequence from the list, if necessary, and re-inserting it into its proper place in the first sequence.
Of course the subprogram must handle cases where there is no second sequence because the first ordered sequence takes up the whole list, where there is at least one node after the end of the second sequence, or not, etc. Make sure that your subprogram will run in a worst-case time that is O(N), where N is the total number of nodes in the two ordered sequences. In your discussion, explain how you know that this is true.
You can use the source code for Lafore’s Link and LinkList classes, but name your node class Node, not Link. This is in agreement with most books. The link is just the instance variable next in the Link class (now renamed the Node class).
Or, you can use your own code everywhere. In any case, make the code robust: If any error could occur, such as trying to delete a node from an empty list, or follow a null link, etc., your program must detect the error and either print an error message and terminate, or throw an exception.
If you use any material or ideas from any other person or source, you must reference the source and explain just what you used.
Test your subprogram on the above list1. Test it also on cases where the given list is empty; where the first sequence takes up the whole list; and where the two sequences together take up the whole list.
Hand in (1) source code, (2) output, and (3) a thorough discussion.
Explanation / Answer
Answer):
public Node merge(Node first, Node second)
{
Node temp = new Node();
Node head = temp;
Node merged = head;
while(first != null && second != null)
{
if(first.iData <= second.iData)
{
merged.next = first;
merged = first;
first = first.next;
}
else
{
merged.next = second;
merged = second;
second = second.next;
}
}
if(first == null)
merged.next = second;
else
merged.next = first;
return head.next;
}