LinkedList.java (insertion sort version)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
import java.util.Random; import java.util.stream.Collectors; import java.util.List; import java.util.ArrayList; import java.util.Collections; public class LinkedList<T extends Comparable<T>> { private class Node<T extends Comparable<T>> { T data; Node<T> next; public Node(T data){ this.data = data; } public Node(T data, Node<T> next){ this(data); this.next = next; } public String toString(){ return "" + data; } } private Node<T> head; private int count; public LinkedList(){ head = null; count = 0; } public LinkedList(T d){ head = new Node<T>(d); count = 1; } public int length() { return count; } public boolean isEmpty(){ return head == null; } public void clear(){ head = null; count = 0; } public void prepend(T d){ head = new Node<T>(d, head); count++; } public void insertionSort(){ Node<T> tempHead = head; head = null; count = 0; while ( tempHead != null) { sortedInsert(tempHead.data); tempHead = tempHead.next; } } private void sortedInsert(T d){ if (head == null || d.compareTo(head.data) < 0) head = new Node<T>(d, head); else { Node<T> curr = head; for ( ; curr.next != null && (d.compareTo(curr.next.data) > 0) ; curr = curr.next); curr.next = new Node<T>(d, curr.next); } count++; } public String toString(){ String retVal = "Linked List with " + count + " nodes: "; for (Node<T> temp = head ; temp != null ; temp = temp.next){ retVal += temp + " "; } return retVal; } public static List<Integer> getRandoms(int count){ return new Random().ints().limit(count).boxed().collect(Collectors.toList()); } public static void main(String[] args){ LinkedList<Integer> ll = new LinkedList<>(); ll.prepend(20); ll.prepend(60); ll.prepend(30); ll.prepend(65); ll.prepend(35); System.out.println(ll); ll.insertionSort(); System.out.println(ll); ll.clear(); List<Integer> randoms = getRandoms(100000); long startTime = System.currentTimeMillis(); for(Integer r : randoms) ll.prepend(r); long endTime = System.currentTimeMillis(); System.out.println("Total prepend execution time: " + (endTime - startTime) ); startTime = System.currentTimeMillis(); ll.insertionSort(); endTime = System.currentTimeMillis(); System.out.println("Total insertionSort execution time: " + (endTime - startTime) ); Collections.sort(randoms); Collections.reverse(randoms); ll.clear(); startTime = System.currentTimeMillis(); for (Integer r : randoms) ll.sortedInsert(r); endTime = System.currentTimeMillis(); System.out.println("Total sortedInsert of reverse-sorted data execution time: " + (endTime - startTime) ); } } |