Singly linked list data structure implemented using Java

Hi,

This weekend I had a some free time, so I decided to play with Java. The point was  creating something simple using Java. I've downloaded JDK from Oracle, took Eclipse Juno IDE for Java.  It looks like that's all what I need to start doing fun. Instead of writing 100500  times Hello world java program, I decided to  write something  easy. What if I implement Singly Linked List data structure in Java? Piece of cake :)

So, What is Linked List?
It think- everyone know it, but any way-A linked list is a data structure in which the objects are arranged in a linear order. In a linked list, each data item is embedded in a link. A link is an object of a class called something like Link. Because there are many similar links in a list, it makes sense to use a separate class for them, distinct from the linked list itself. Each link object contains a reference (usually called next) to the next link in the list. A field in the list itself contains a reference to the first link. A list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not.
Here, is how I  implement Link class:

public class Link {

 public int data;
    
    public Link nextLink;

    //Link constructor
    public Link(int d1) {
     data = d1;     
    }

    //Print Link data
    public void printLink() {
     System.out.print("{" + data +  "} ");
    }

What we would like to get from our Linked List?
It will be good to have something like:

• Insert new Item
• Delete Item
• walk through all items in the list
• Reverse Singly Linked List

As for me, it should be enough for playing.

Here is how LinkList class will looks like.

public class LinkList {
 private Link first;

    //LinkList constructor
    public LinkList() {
     first = null;
    }

    //Returns true if list is empty
    public boolean isEmpty() {
     return first == null;
    }

    
    //Inserts a new Link at the first of the list
    public void insert(Link link) {
     //Link link = new Link(d1, d2);
     link.nextLink = first;
     first = link;
    }


    //Deletes the link at the first of the list
    public Link delete() {
     Link temp = first;
     first = first.nextLink;
     return temp;
    }

    //Prints list data
    public void printList() {
     Link currentLink = first;
     System.out.print("List: ");
     while(currentLink != null) {
      currentLink.printLink();
      currentLink = currentLink.nextLink;
     }
     System.out.println("");
    }
    
    
    public void Reverse(){
     Link currentLink, nextLink, loopLink;
     currentLink=this.first;
     nextLink=currentLink.nextLink;
     loopLink=null;
     
     while(nextLink!=null){
      currentLink.nextLink=loopLink;
      loopLink=currentLink;
      currentLink=nextLink;
      nextLink=nextLink.nextLink;      
     }
     this.first=currentLink;
     this.first.nextLink=loopLink;
     
    }
       
    
    public void Reverse(){
    Link current, next, tmp;
    current=this.first;
    next=this.first.nextLink;
    tmp=null;
    
    while(next!=null){
     current.nextLink=tmp;
     tmp=current;
     current=next;
     next=next.nextLink;     
    }
    this.first=current;
    this.first.nextLink=tmp;
      
    }

Heapsort Algorithm implementation in C#

Today I would like to introduce another sorting algorithm: heapsort. 

Heapsort’s running time is O(n lg n). Heapsort also introduces another algorithm design technique: using a data structure, in this case one we call a "heap", to manage information. The term "heap" was originally coined in the context of heapsort, but it has since come to refer to "garbage-collected storage", such as the programming languages C#, Java provide. My heap data structure is not garbage-collected storage, and whenever I refer to heaps,  I mean a data structure rather than an aspect of garbage collection.

The heapsort algorithm starts by using "Adjust" to build a max-heap on the input array A[1..n], where n=A.Length. Since the maximum element of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. If we now discard node n from the heap—and we can do so by simply decrementing A:heap-size—we observe that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call  Adjust(A,1), which leaves a max-heap in A[1..n-1]. The heapsort algorithm then repeats this process for the max-heap of size n - 1 down to a heap of size 2.

Here is code:

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

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortComparison { public class HeapSort<T> where T : IComparable<T> { public static void Sort(T[] A) { //build the initial heap for (int i = (A.Length - 1) / 2; i >= 0; i--) Adjust2(A, i, A.Length - 1); //swap root node and the last heap node for (int i = A.Length - 1; i >= 1; i--) { T Temp = A[0]; A[0] = A[i]; A[i] = Temp; Adjust(A, 0, i - 1); } } private static void Adjust(T[] list, int i, int len) { T Temp = list[i]; int j = i * 2 + 1; while (j <= len) { //more children if (j < len) if (list[j].CompareTo(list[j + 1]) < 0) j = j + 1; //compare roots and the older children if (Temp.CompareTo(list[j]) < 0) { list[i] = list[j]; i = j; j = 2 * i + 1; } else { j = len + 1; } } list[i] = Temp; } } }

Please, feel free post any comments!

Binary Search Algorithm

Generally, to find a value in unsorted array, we should  choose:
1 Take a look through elements of an array one by one, until searched value is found. If required value doesn't exists in  our array, then we will pass all array, all elements. In average, complexity of such an algorithm is  O(n) n- count of elements.
2. Sort array  using  any in place sort algorithms, QuickSort for instance, and then apply Binary Search algorithm.


Algorithm

Algorithm is very simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:

• searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
• searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

I decided  to implement it recursive way with a few enhancements.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class BinarySearch { public int Search(List A, T val) where T : IComparable { if (A == null || A.Count == 0) return -1; return InnerSearch(A, val, 0, A.Count() - 1); } private int InnerSearch(List A, T val, int min, int max) where T : IComparable { int middle = (min + max) / 2; if (max < min || min > max) return -1; if (A[middle].CompareTo(val) == 0) return middle; if (middle == A.Count() - 1) return -1; if (A[min].CompareTo(val) == 0) return min; if (A[max].CompareTo(val) == 0) return max; else if (A[middle].CompareTo(val) > 0) return InnerSearch(A, val, min+1, middle - 1); else return InnerSearch(A, val, middle + 1, max-1); } }