Linked List

For this update, i create & post it because i get a request for someone...
this post will show your how the linked list algorithm look like.....
Have two method
- first one is the source code i create ...
- second one is the source code i get from my friend (gray)....

First Step: create Node class

public class Node
    {
        protected Node next;
        protected Object data;
     
        public Node(Object _data)
        {
            next = null;
            data = _data;
        }

        public Node(Object _data, Node _next)
        {
            next = _next;
            data = _data;
        }

    }


Second step : start create linked list class..

public class LinkedList{

    private Node head;
    private Node tail;
    private int length;

    public LinkedList()
    {
        head=new Node(null); // second method : head = null;
        tail=null;
        length = 0;
    }
 
    public void insertAtFront(Object data)// add Object at first position
    {
        if(isEmpty()){          
            head.next = new Node(data); // second method : head = new Node(data);
            tail = head.next; // second method : tail = new Node(data);
        }
        else{
            Node temp = new Node(data);
            temp.next = head.next; // second method : temp.next = head;
            head.next = temp; // second method : head = temp;
        }
        length++;
    }// end insertAtFront
 
    public void removeAtFront()// delete Object at first position
    {
        if(isEmpty()){
            System.err.println("List is empty");
        }
        else{
            length--;
            Node temp = head; // second method : (not need - remove)
            temp.next = temp.next.next; // second method : head=head.next;
        }
    }// end removeAtFront
 
    public void removeAtBack() // delete Object at last position
    {
        if(isEmpty()){
            System.err.println("List is empty");
        }
        else{
            length--;
            Node temp = head;
            while(temp.next != tail){
                temp = temp.next;
            }
            tail = temp;
            temp.next = null;
        }      
    }// end removeAtBack
 
 
    public Node getFirst()
    {
        return head.next; // second method : return head;
    }
 
    public Node getLast()
    {
        return tail;
    }
 
    public boolean isEmpty(){
        return (length==0);
    }
 
    public void clear(){
        head = new Node(null); // second method : head=null;
        tail = null;
        System.gc();
     
        length=0;
    }
 
    public int size(){
       return length;
    }
 
    public String toString()
    {
        String output = "";
        if(!isEmpty()){
            Node temp= head.next;
            while(temp != null)
            {
                output += "[" + temp.data + "]";
                temp= temp.next;
            }
            return output;
        }
        else{
            return null;
        }
     
    }
 
 
}



Explanation :

Now i will explain what difference between current method i use and second method.....

how the block in node look like...

Figure below show how structure look when it initialize. For second method, the content will be empty but current method will create first block that it data is null.

                           

Figure below show how structure look when when the first data added. For second method, it start to create first block that it data is 10. current method will create new block that it data is 10.
then, second method block number is 1 but current method  block number is 2.

                         

Now, try use it in main program.


public class MainProgram{
    public static void main(String []args){
     
        LinkedList list=new LinkedList();
        System.out.println("Insert 10 at front");
        list.insertAtFront(10);
     
        System.out.println("Insert 58 at front");
        list.insertAtFront(58);
     
        System.out.println("Insert 64 at front");
        list.insertAtFront(64);
     
        System.out.print("\n-Result-------------------------------------------\n\t");
        System.out.println(list.toString());
        System.out.println("--------------------------------------------------\n");
     
        System.out.println("Remove at Back");
        list.removeAtBack();
     
        System.out.print("\n-Result-------------------------------------------\n\t");
        System.out.println(list.toString());
        System.out.println("--------------------------------------------------\n");;
     
        System.out.println("Remove at front");
        list.removeAtFront();
     
        System.out.print("\n-Result-------------------------------------------\n\t");
        System.out.println(list.toString());
        System.out.println("--------------------------------------------------\n");
     
        System.out.println("Clear List");
        list.clear();
     
        System.out.print("\n-Result-------------------------------------------\n\t");
        System.out.println(list.toString());
        System.out.println("--------------------------------------------------\n");
     
        System.exit(0);
    }
}



Sample Running :


Insert 10 at front
Insert 58 at front
Insert 64 at front

-Result-------------------------------------------
[64][58][10]
--------------------------------------------------

Remove at Back

-Result-------------------------------------------
[64][58]
--------------------------------------------------

Remove at front

-Result-------------------------------------------
[58]
--------------------------------------------------

Clear List

-Result-------------------------------------------
null
--------------------------------------------------

you can test it by your self..

i hope you like this souce code...

and please give some comment....

                                                                                                                                                      Created By : Z-man, 2012