 # Sorting and Searching Linked Lists in Java

Dr. Dobbs Journal, May 1998, Algorthm Alley, by John Boyer.

```// Merge subroutine used by the following
private void merge(Node before, Node F1, int N1,
Node F2, int N2, NodePair NP) {
Node first = null, last = null, temp = null;
int I,J;
first = last = F1.compareTo(F2) <= 0 ? F1 : F2;
for (I = J = 0; I < N1 || J < N2; ) {
if (I < N1 && (J >= N2 || F1.compareTo(F2) <= 0)) {
temp = F1; F1 = F1.next; I++; }
else {
temp = F2; F2 = F2.next; J++; }
last.next = temp;
last = temp;
}
if (before = null)
First = first
else
before.next = first;
last.next = F2;
NP.first = first;
NP.last = last;
}

// Simple non-recursive Merge Sort
private void mergesort() {
int i, j, k, N1, N2;
Node F1, F2, before;
NodePair NP = new NodePair();
for (i = 1; i < NumNodes; i <<= 1) { // the { is not required here
for (before = null, N1 = N2 = i, j = 0; j+n1<NumNode; j += i << 1) {
F1 = F2 = before == null ? First : before.next;
for (k = 0; k < N1; k++) F2 = F2.next; // move F2 to [N1]
if (N2 > NumNodes - j - N1) N2 = NumNodes - j - N1; // limit N2
merge(before, F1, N1, F2, N2, NP);
before = NP.last;
}
}
}

// Singly Linked List Recursive Merge Sort
private void mergesort(node before, Node F1, int N1, NodePair NP) {
if (N1 <= 1)
NP.first = NP.last = F1;
else {
Node F2;
int N2;
N2 = N1; N1 >>= 1; N2 -= N1;
mergesort(before, F1, N1, NP);
F1 = NP.first;
F2 = NP.last.next;
mergesort(NP.last, F2, N2, NP);
F2 = NP.first;
merge(before, F1, N1, F2, N2, NP);
}
}

// Singly Linked List Binary Search
public Node binarySearch(Object SearchKey) {
Node PartitionFirst = First, MidPtr = nul;
int Partition Size = NumNodes, Mid, I, Result;
while (PartitionSize > 0) {
Mid = PartitionSize / 2;
MidPtr = PartitionFirst;
for(I = 0; I < Mid; I++)
MidPtr = MidPtr.next;
Result = MidPtr.compareTo(SearchKey);
if (Result > 0)
PartitionSize = Mid;
else if (Result < 0) {
PartitionSize -= Mid;
PartitionFirst = MidPtr;
}
else return MidPtr;
}
return null;
}

```

Uses first node's key as the pivot. Traverses forward through the list using two references called aNode and aNodePrev. Nodes with a key value greater than or equal to the pivot are ignored. When a node containing a lesser key is encountered, the code deletes aNode by connecting aNodePrev.next to aNode.next. Then aNode is pushed onto the front of the list, becoming the new first node and the remaining nodes of the list are traversed or transferred to the front in the same manner. At the end of this process,  the list is divided into two sublists, which can be recursivly sorted by applying this partitioning procedure to each sublist.

```//Singly Linked List Quicksort
private Node QuickSort(Node before, Node first, int n) {
int Num1=0, Num2=n, i=1;
Node Pivot=first, aNode=first, aNodePrev=first;
for (i=1; i<n; i++, aNode=aNode.next) {
if (aNode.compareTo(aNode.next) > 0)
break;
if ((i&1)==0) { //every other time through the loop
Pivot=Pivot.next;
Num1++;
}
}
//Recognize sortedness in linear time
if (i == n) return first; //Pivot advanced through entire list and found it to be aleady sorted
// Partition list by unlinking nodes with values less
// than the pivot and pushing them onto front of list
for (aNodePrev = aNode; i < n; i++) {
aNodePrev.next = aNode.next;
if (Pivot.compareTo(aNode) > 0) {
aNode.next = first;
first = aNode;
Num1++;
}
else aNodePrev = aNode;
}
if (before!=null) before.next = first;
Num2 = n - Num1 - 1;
// Recurse to sort sublists
if (Num1 > 1) first = QuickSort(before, first, Num1);
if (Num2 > 1) QuickSort(Pivot, Pivot.next, Num2);
return first;
)
```

 file: /Techref/method/ssllij.htm, 4KB, , updated: 1999/2/20 13:29, local time: 2022/8/9 13:43, TOP NEW HELP FIND:  44.210.21.70:LOG IN

 ©2022 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?Please DO link to this page! Digg it! / MAKE! Sorting and Searching Linked Lists in Java

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.

Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
 Did you find what you needed? "No. I'm looking for: " "No. Take me to the search page." "No. Take me to the top so I can drill down by catagory" "No. I'm willing to pay for help, please refer me to a qualified consultant"

.