**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 :)__- Create Node class containing two things. Object (basically data which node will hold) and Node which is reference to Next Node
- Create Your Own linkedList class which will have following methods.
- add(Object data) - add element to tail of LinkedList
- add(Object data,int index) - create new Node and add that new node containing given data at specific index.
- get(int index) - find node at given index and return its data
- remove(int index) - find node at given index and remove it
- size - which returns total size of your linkedlist
- toString - basically String representation based on your requirement.

**Head Node**". Initially headeNode's next is set to null.

__Logic goes as below__

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

__Logic goes as below__

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

__Logic goes as below__

**Get node's data at Specific Index in Your Own LinkedList.**- Set currentNode as HeadNode.
- 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.
- Just return node's data

__logic goes as below__

**Remove node at specific Index in your own LinkedList.**- if index is less than total size of linkedlist then we can not remove node since it doesn't present.
- In order to remove node at Specific Index, you need to do as below
- find node which is just before given index
- 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.
- 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]