/***************************************************************************
* Author: Isai Damier
* Title: Singly Linked List
* Project: geekviewpoint
* Package: datastructure
*
* Description: A LinkedList is a data structure that allows access
* to a collection of data using pointers/references. While an
* array can also be defined as above, LinkedLists and arrays differ
* in how they are stored in memory and in the operations they
* allow. Unlike an array that must be stored in a block of memory,
* the nodes of a LinkedList can be stored anywhere because each
* node has a reference to the node that succeeds it. Because the
* nodes are stored so loosely, inserting nodes into a LinkedList
* is easy; whereas in an array, all the succeeding elements must
* be shifted. Of course, insertion also means changing the size of
* the array, which means creating the entire array anew.
*
* Perhaps the greatest beauty of LinkedList is that it allows
* accessing an entire sequence of nodes using only one variable:
* a reference to the first node in the sequence.
*
* Countless operations can be performed on LinkedLists. Following
* are a few, ranging from the common to the very interesting.
**************************************************************************/
public class SinglyLinkedList {
Node head = null;
Node tail = null;
/*****************************************************************
* Time Complexity of Solution:
* O(n*log n).
*
* Description: Sort the elements in this linked list in ascending
* order.
*
* Technical Details: Sorting a LinkedList in place is very costly:
* in the order of O(n^2 * log(n)) with a good algorithm.
* Therefore it makes sense to create an array from the list,
* sort the array, and then empty the array into the list by
* index. It's kind of like: unbutton a shirt; move the buttons
* around; then button the shirt anew. (I think it's a good analogy.)
*****************************************************************/
public void sort() {
if (2 > this.size()) {
return;
}
int[] A = new int[this.size()];
//unfasten the buttons (i.e. unbutton the shirt)
int x = 0;
for (Node t = head; null != t; t = t.next) {
A[x++] = t.data;//list fills array
} //sort the buttons
mergesort(A, 0, A.length - 1);
//refasten the buttons (i.e. button the shirt anew)
x = 0;
for (Node t = head; null != t; t = t.next) {
t.data = A[x++];//array fills list
}
}
private void mergesort(int[] input, int first, int last) {
//break array into smaller structurally identical pieces
int mid = (first + last) / 2;
if (first < last) {
mergesort(input, first, mid);
mergesort(input, mid + 1, last);
}
//merge sorted pieces to get solution to original array
int a = 0, f = first, l = mid + 1;
int[] tmp = new int[last - first + 1];
while (f <= mid && l <= last) {
tmp[a++] = input[f] < input[l] ? input[f++] : input[l++];
}
while (f <= mid) {
tmp[a++] = input[f++];
}
while (l <= last) {
tmp[a++] = input[l++];
}
a = 0;
while (first <= last) {
input[first++] = tmp[a++];
}
}
}
public class SinglyLinkedListTest {
/**
* Test of sort method, of class SinglyLinkedList.
*/
@Test
public void testSort() {
System.out.println("sort");
int[] input = {9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11};
SinglyLinkedList linkedList = new SinglyLinkedList();
for (int i = 0; i < input.length; i++) {
linkedList.addToTail(input[i]);
}
assertTrue(Arrays.equals(input, linkedList.toArray()));
Arrays.sort(input);
assertFalse(Arrays.equals(input, linkedList.toArray()));
linkedList.sort();
assertTrue(Arrays.equals(input, linkedList.toArray()));
}
}
