Program To Implement Linked Lists and Its Application Using Java Programming Language Assignment Solution

Instructions

Objective

Write a java assignment program to implement linked lists and its application.

Source Code

import java.util.Random; /** * COMP 2140 SECTION A01 * INSTRUCTOR Cuneyt Akcora * Assignment 2 * * @author your name, your student number * @version date of completion * * PURPOSE: To implement Link list merge, fix and conversion methods. */ public class Assignment2 { public static void main(String[] args) { //Send input parameters to your method. In run/edit configurations, use program arguments and enter "1500 1300" int list1Size = Integer.parseInt(args[0]);//1500; int list2Size = Integer.parseInt(args[1]);//1300; Random r1 = new Random(); LinkedList list1 = new LinkedList(); for (int i = 0; i < list1Size; i++) { int randomInt = r1.nextInt(list1Size); list1.insertValue(randomInt); } LinkedList list2 = new LinkedList(); for (int i = 0; i < list2Size; i++) { int randomInt = r1.nextInt(list2Size); list2.insertValue(randomInt); } list1.quickSort(); list2.quickSort(); System.out.println("\nCOMP 2140 Assignment 2 linked list questions"); System.out.println("\nCurrently both List1 and List2 are circular."); System.out.println("\nWe insert nodes or values to the circular version only."); System.out.println("\nOtherwise we would need to rewrite the insert function."); list1.add(list2); int size = list1Size + list2Size; System.out.println("List1 is expanded: " + (list1.getSize() == size)); System.out.println("List1 is in order: " + list1.isSorted()); System.out.println("List2 is in order: " + list2.isSorted()); System.out.println("Type of List1 is Circular:" + list1.isCircular()); list1.convertCircularToOrdinary(); System.out.println("Type of List1 is Ordinary:" + list1.isOrdinary()); list1.deleteOddNodes(); System.out.println("Odd nodes are deleted:" + list1.getSize() + " nodes remain"); list1.convertOrdinaryToCircular(); System.out.println("Type of List1 is Circular:" + list1.isCircular()); list1.convertCircularToOrdinary();//again, in order to add dummies. list1.addDummies(); System.out.println("List1 has dummies:" + list1.hasDummies()); list1.reset();//back to a circular list int[] arr = new int[size]; //testInsertion below is overloaded. It has multiple // versions each with a different signature. //In your IDE, if you click on the function name while holding the CTRL key //the cursor will move to the function declaration long secondsList = testInsertion(size, list1); long secondsArray = testInsertion(size, arr); System.out.println("Insertions take " + secondsArray + " (array) " + (secondsList) + "(list) nsecs"); list1.reset(); long t1 = System.nanoTime(); int runs = 1000000; for (int i = 0; i < runs; i++) { insertValue(list1, i); } t1 = System.nanoTime() - t1; System.out.println("Linked list new values take " + (t1) + " nsecs"); arr = new int[size]; //insertvalue is overloaded. t1 = System.nanoTime(); for (int i = 0; i < runs; i++) { arr = insertValue(arr, i, i); } t1 = System.nanoTime() - t1; System.out.println("Array new values take " + (t1) + " nsecs"); //corrupt the linked list at one position int index = r1.nextInt(list1.getSize() / 2);// corrupted point is in the first half of the list1 list1.convertCircularToOrdinary();//ordinary linked list, with no duplicates (even the values are in sorted order). System.out.println("Type of List1 is Ordinary:" + list1.isOrdinary()); System.out.println("List is originally corrupt: " + list1.findCorruption()); int valueAtCorruption = list1.corrupt(index); boolean foundValue = list1.findCorruption(); System.out.println("Corruption at index " + index + " (value:" + valueAtCorruption + ") was found: " + (foundValue)); System.out.println("Program ends."); } // end main /* Insert new integers into the list (you can insert 1 every time) 'size' times, and return the time it takes to complete these insertions. */ private static long testInsertion(int size, LinkedList list1) { long start = System.nanoTime(); for (int i = 0; i < size; i++) { list1.insertValue(1); } return System.nanoTime() - start; } /* Insert new integers into the array (you can insert 1 every time) 'size' times, and return the time it takes to complete these insertions. */ private static long testInsertion(int size, int[] arr) { long start = System.nanoTime(); for (int i = 0; i < size; i++) { arr[i] = 1; } return System.nanoTime() - start; } /* insertValue: insert the given value into the array. If the array size is exceeded, you must create a new array (1.5 size of the current array, if arr size is 100, create a new arr for 150 values) and copy the old array into the new array. Afterwards, insert the new item value to the new array */ private static int[] insertValue(int[] arr, int i, int index) { //write your code here //everytime you create a new array, printout a log with arr.size and newarray.size if (arr.length == index) { int[] newArr = new int[arr.length * 3 / 2]; System.arraycopy(arr, 0, newArr, 0, arr.length); arr = newArr; } arr[index] = i; return arr; } /* insertValue: insert the given value into the link list. We could use the list.insert() but the goal of this exercise is to show the dynamic nature of lists. */ private static void insertValue(LinkedList list1, int i) { list1.insertValue(i); } } // end class Assignment2 /* 1. New array was created 15 times. 2. 182637 elements left unused. 3. Arrays are useful, when we need to perform huge amount of access queries to different elements of collection. */