Friday, December 26, 2014

Implement your own LinkedList using Java

LinkedList consist of Nodes where each Node represent two things. One is Data and other is reference to Next node.

Let's check How you can create your own LinkList Implementation :)
  1. Create Node class containing two things. Object (basically data which node will hold) and Node which is reference to Next Node
  2. Create Your Own linkedList class which will have following methods.
    1. add(Object data) - add element to tail of LinkedList
    2. add(Object data,int index) - create new Node and add that new node containing given data at specific index.
    3. get(int index) - find node at given index and return its data
    4. remove(int index) - find node at given index and remove it
    5. size - which returns total size of your linkedlist
    6. toString - basically String representation based on your requirement.
First, Initialize your linked list with Node which we called as "Head Node". Initially headeNode's next is set to null.

Adding new node in your own LinkedList. Logic goes as below
  1. Start with head node and check node's next reference until you get last node.This will be Tail node(Last node of linkedList).
  2. Here tail node's next will be null.
  3. create new Node with data and next to null.
  4. Now you have tail node of your linked list and new node you have created. just add this new node to last node. how?
  5. To do so, set tail node's next to new node and increment total size count of your linkedlist.That's it.

Adding new node at specific index in your own LinkedList. Logic goes as below
  1. Start with head node and iterate until you get node which is before at given index.
  2. Create new Node with data and next to null.
  3. Now in order to add new node at given index, you need to do 3 things
    1. you need to set new Node's next to node at given index
    2. set node (which is just before node at given index)'s next to this new node.
    3. increment total size of linekdlist

Get node's data at Specific Index in Your Own LinkedList. Logic goes as below
  1. Set currentNode as HeadNode.
  2. Starting from 1 until i < index provided, if currnentNode's next is not null, move to next node. you will have node at given Index.
  3. Just return node's data

Remove node at specific Index in your own LinkedList. logic goes as below
  1. if index is less than total size of linkedlist then we can not remove node since it doesn't present.
  2. In order to remove node at Specific Index, you need to do as below 
    1. find node which is just before given index
    2. Set this node's next to Next of current Node's next where current Node is not at given index. So reference will be removed hence our job is done.
    3. Decrease size of linkedlist. Implementation of your own LinkedList using Java

Implementation of your own LinkedList using Java
package com.anuj.algorithms;

/**
 * 
 * @author anpatel
 * @source goldenpackagebyanuj.blogspot.com
 */
public class MyLinkedListExample {
 public static void main(String[] args) {
  MyLinkedList myLinkedList = new MyLinkedList();

  for (int i = 1; i <= 10; i++) {
   myLinkedList.add(i);
  }

  System.out.println("Total Size :" + myLinkedList.getSize());
  System.out.println("MyLinkedList : "+myLinkedList);

  System.out.println("Node with Element 4 :"+myLinkedList.get(4));
  
  System.out.println("Node with Element 6 removed : "+myLinkedList.remove(6));
  System.out.println("Total Size After removing Node:" + myLinkedList.getSize());
  System.out.println("MyLinked List After Removing Node :"+myLinkedList);
 }
}

/**
 * Node presenting data and next node
 * @author anpatel
 *
 */
class Node {
 Object data;
 Node next;

 public Node() {

 }

 /**
  * set Node property with data and nextNode
  * @param data
  * @param nextNode
  */
 public Node(Object data, Node nextNode) {
  this.next = nextNode;
  this.data = data;
 }

 /**
  * Next Node is null if only data provided
  * @param data
  */
 public Node(Object data) {
  this.data = data;
  this.next = null;
 }

 public Object getData() {
  return data;
 }

 public void setData(Object data) {
  this.data = data;
 }

 public Node getNext() {
  return next;
 }

 public void setNext(Node next) {
  this.next = next;
 }
}

/**
 * My Own LinkedList Implementation
 * @author anpatel
 *
 */
class MyLinkedList {
 private Node headNode;
 private int totalSize;

 public MyLinkedList() {
  //create headNode with data as null and nextNode as Null
  headNode = new Node(null);
  totalSize=0;
 }

 /**
  * add Element at tail of LinkedList with NextNode as Null
  * @param data
  */
 public void add(Object data) {
  Node newNode = new Node(data);
  Node currentNode = headNode;

  //Starting from head Node, iterate over all node to find last Tail node and add NewNode there
  while (currentNode.getNext() != null) {
   currentNode = currentNode.getNext();
  }

  //By this time, we found Tail Node which is currentNode, So add new Node
  currentNode.setNext(newNode);
  totalSize++;
 }

 /**
  * Insert new Node at Specific Index Location
  * 
  * @param data
  * @param index
  */
 public void add(Object data, int index) {
  //Starting from Head, iterate and reach over Node having Index just less than provided index
  Node newNode = new Node(data);
  Node currentNode = headNode;

  int i = 1;
  while (currentNode.next != null && i < index) {
   currentNode = currentNode.getNext();
   i++;
  }

  //By This time , we have currentNode presenting node which is node just before Node having index provided
  //set NewNode's Next to Node existing at Specific Index
  Node existingNodeAtGivenIndex = currentNode.getNext();
  newNode.setNext(existingNodeAtGivenIndex);

  //Set CurrentNode's Next to newNode
  currentNode.setNext(newNode);

  totalSize++;

  System.out.println("Node " + newNode + " inserted at index " + index);
  System.out.println("Total Size of myLinkedList after inserting new Node - " + totalSize);
 }

 /**
  * Get Node at Specific Index and return it's Value
  * @param index
  */
 public Object get(int index) {
  Node currentNode = headNode;
  if (index <= 0) {
   return null;
  }

  //Find Node at Index just before given Index
  for (int i = 1; i < index; i++) {
   if (currentNode.getNext() == null) {
    return null;
   }
   currentNode = currentNode.getNext();
  }

  //By This time we have node at given Index
  return currentNode.getData();
 }

 /**
  * Remove Element at Specific Index in myLinkedList
  * @return
  */
 public boolean remove(int index) {
  boolean isRemoved = false;
  Node currentNode = headNode;
  if (index < 1 || index > totalSize) {
   isRemoved = false;
  }

  //Find Node at Index just before given Index
  for (int i = 1; i < index; i++) {
   if (currentNode.getNext() == null) {
    //we reached Last Node of HeadNode. TODO remove this one?
    isRemoved = false;
   }
   else{
    currentNode = currentNode.getNext();
   }
   
  }

  if (!isRemoved) {
   //By This time we have currentNode is not which is just before Node at given Index
   //currentNode's Next is node at Given Index
   //Current Node's Next's Next is node after just given Index
   currentNode.setNext(currentNode.getNext().getNext());
   isRemoved = true;
   totalSize--;
  }

  return isRemoved;
 }

 /**
  * Return size of MyLinkedList
  * @return
  */
 public int getSize() {
  return totalSize;
 }

 @Override
 public String toString() {
  String myList = "";
  Node currentNode = headNode;
  while (currentNode != null) {
   Object data = currentNode.getData();
   Node node = currentNode.getNext();
   if(node != null){
    myList += "[" + String.valueOf(data) + "->" + node + "] -->";
   }
   else{
    myList += "[" + String.valueOf(data) + "->" + node + "]";
   }
   currentNode = node;
  }
  return myList;
 }
}

Output:
Total Size :10
MyLinkedList :
[null->com.anuj.algorithms.Node@565f0e7d] -->[1->com.anuj.algorithms.Node@7ab05cd7] -->[2->com.anuj.algorithms.Node@509f662e] -->[3->com.anuj.algorithms.Node@10ed7f5c] -->[4->com.anuj.algorithms.Node@584479b2] -->[5->com.anuj.algorithms.Node@7791c263] -->[6->com.anuj.algorithms.Node@2712ee9] -->[7->com.anuj.algorithms.Node@54bec43f] -->[8->com.anuj.algorithms.Node@38462f90] -->[9->com.anuj.algorithms.Node@7dcb3cd] -->[10->null]
Node with Element 4 :3
Node with Element 6 removed : true
Total Size After removing Node:9
MyLinked List After Removing Node :
[null->com.anuj.algorithms.Node@565f0e7d] -->[1->com.anuj.algorithms.Node@7ab05cd7] -->[2->com.anuj.algorithms.Node@509f662e] -->[3->com.anuj.algorithms.Node@10ed7f5c] -->[4->com.anuj.algorithms.Node@584479b2] -->[5->com.anuj.algorithms.Node@2712ee9] -->[7->com.anuj.algorithms.Node@54bec43f] -->[8->com.anuj.algorithms.Node@38462f90] -->[9->com.anuj.algorithms.Node@7dcb3cd] -->[10->null]

No comments:

Post a Comment