How to Merge Two Sorted ADT Lists

An Abstract Data Type (ADT) list, or linked list as it is more commonly called, is one of the fundamental data structures in computer science and one of the first alternatives to the simple array learned by a computer science student. Though it sacrifices the ability to move to the middle of the list without searching through the list first, the ADT list makes it trivially easy to expand and shrink the stored data. This code is implemented in Java, since Java's built-in Linked List data structure allows us to get directly to the point, but the same logic could be implemented with minimum modification in any other C-like language.

Instructions

1. Create your two linked lists and initialize them with some sorted data by pasting the following into a Java file:

   LinkedList<Double> list1 = new LinkedList<Double>();

   LinkedList<Double> list2 = new LinkedList<Double>();

   for(int x = 0; x < 100; x++) {

   list1.add(Math.random());

   list2.add(Math.random());

   }

   Collections.sort(list1);

   Collections.sort(list2);

   Now, you have two linked lists filled with random numbers that have been sorted.

2. Create a new Linked List to hold the merged list by pasting the following:

   LinkedList<Double> merged = new LinkedList<Double>();

3. Set up a simple while loop. This loop will proceed as long as both lists have at least one element in them, and it will move the smallest of the top elements to the merged list:

   // While both lists are not empty.

   while (!list1.isEmpty() && !list2.isEmpty()) {

   if (list1.peek() <= list2.peek()) {

   merged.add(list1.pop());

   } else {

   merged.add(list2.pop());

   }

   }

   The "Peek" command looks at the element at the front of the list, while "Pop" both looks at the element and removes it. When the comparison is made, you only want to peek at the top of the list to see which is smaller. When it comes time to merge the lists, you want to take away the top value and put it on the new lists.

4. Finish the job. As soon as either list is empty, there is no need to continue making comparisons. Therefore, the old loop ends, and another loop is created to fill the rest of the merged list with the remaining data of the last list:

   // While the first list is not empty

   while (!list1.isEmpty()) {

   merged.add(list1.pop());

   }

   // While the second list is not empty.

   while (!list2.isEmpty()) {

   merged.add(list2.pop());

   }

5. Print out the results so you can inspect the merged list and ensure it worked properly:

   int x = 1;

   for (Double y : merged) {

   System.out.println(x + " " + y);

   x++;

   }

References

• Aberdeen Institute of Mathematics: The ADT List