Saturday, February 2, 2013

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;
      
    }