Saturday, June 5, 2010

LinkedList in Java



This tutorial will show you a Linked List implementation in Java. It will have following features-
- Add nodes from both ends (Beginning and End)
- Delete nodes from Beginning
- Get count of nodes
- Get First & Last node
- Get Node at a specific position
Please let me know if you find some incorrect scenarios.


Node structure-
/**
 * LinkedList Node
 */
public class Node {
      /**
       * Holds any type of Object Data
       */
      public Object data;
      /**
       * Pointer to a Node
       */
      public Node pointer;
}

Linked List
/**
 * LinkedList Implementation
 */
public class LinkedList {

      Node first;
      /**
       * Stores the count of nodes in the linked list
       */
      int count;
     
      /**
       * Add an element at the beginning
       * @param data
       */
      public void addToBeginig(Object data){
            if(first == null){
                  /*
                   * The Linkedlist is empty and adding the first node
                   *
                   */
                  Node node = new Node();
                  node.data = data;
                  node.pointer = null;
                  first = node;
                  count = 1;
                  return;
            }
            // Add the node at the beginning
            Node newFirst = new Node();
            newFirst.data = data;
            newFirst.pointer = first;
            first = newFirst;
            count++;
      }
     
      /**
       * Add one element at the end of the list
       * You can store multiple type Objects in a single LinkedList
       * e.g. String, your Custom Class etc. as long as you cast it properly
       * @param data
       */
      public void addToEnd(Object data){
            if(first == null){
                  /*
                   * The Linkedlist is empty and adding the first node
                   *
                   */
                  Node node = new Node();
                  node.data = data;
                  node.pointer = null;
                  first = node;
                  count = 1;
                  return;
            }
            Node next = first;
            while(next.pointer != null){
                  next = (Node)next.pointer;
            }
            // Add the node at the end
            Node newNode = new Node();
            newNode.data = data;
            newNode.pointer = null;
            next.pointer = newNode;
            count++;
      }
     
     
      /**
       * Deletes the first node
       */
      public void deleteFromBegining(){
           
            if(first == null){
                  /*
                   * The Linklist is empty, nothing to delete
                   */
                  count = 0;
                  return;
            }
            // get the pointer to next node
            Node next = first;
            // delete the first node
            first = null;
            // make the next node as first node
            first = next.pointer;
            count--;
      }
     
      /**
       * Get the first node
       * @return
       */
      public Node getFirst(){
            return first;
      }
     
      /**
       * Get the last node
       * @return
       */
      public Node getLast(){
            Node next = first;
            while(next.pointer != null)
                  next = next.pointer;
            return next;
      }
     
      /**
       * Get a node at a particular position
       * @param nodeID
       */
      public Object get(int position){
            /*
             * If the position index is more than the count of
             * nodes in the Linkedlist, throw Exception
             */
            if(position >= count)
                  throw new IndexOutOfBoundsException();
           
            Node next = first;
            int i = 0;
            if(i == position)
                  return next.data;
            while(next.pointer != null){
                  next = next.pointer;
                  i++;
                  if(i == position)
                        return next.data;
            }
            // for the last element
            i++;
            return next.data;
      }
     
      /**
       * Returns the count of nodes stored in LinkedIn
       * @return
       */
      public int count(){
            return count;
      }
}
 






No comments:

Post a Comment