Internal Implementation of LinkedList in Java

      In Previous post, discussed about the internal working of ArrayList.  In this post, we can discuss the internal working of LinkedList and implementation of main methods in the LinkedList.

      The LinkedList is a linear data structure, where each element is a separate object.  Each element i.e Node of a list is comprising two items, the data and reference to the next node. The last node has a reference to null.  The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node.  If the list is empty then the head is a null reference.

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow dynamically.

Types of LinkedList : --

1) Singly Linked List 
2) Doubly Linked List

       Below code is internal implementation or source code of add(), remove(), contains(), get() and size() methods of LinkedList(Singly Linked List).
 

package com.pr;
public class CustomLinkedList {
 
      private Node head;
      private int listcount;
 
      public CustomLinkedList(){
           head = new Node(null);
           listcount = 0;
      }
 
      public void add(Object data) {
           Node temp = new Node(data);
           Node current = head;
           while (current.getNext() != null) {
                current = current.getNext();
           }
           current.setNext(temp);
           listcount++;
       }
 
       public void add(Object data, int index) {
            Node temp = new Node(data);
            Node current = head;
            for (int i = 0; i < index && current.getNext() != null ; i++) {
                 current = current.getNext();
            }
            temp.setNext(current.getNext());
            current.setNext(temp);
            listcount++;
       }
 
       public Object get(int index) {
            if (index < 0) {
                 return null;
            }
            Node current = head.getNext();
            for (int i = 0; i<index; i++) {
                 if (current.getNext() == null)
                      return null;
                 current = current.getNext();
            }
            return current.getData();
      }
 
      public boolean remove(int index) {
          if(index < 0 && index > listcount) {
               return false;
          }
          Node current = head;
          for (int i = 0; i < index; i++) {
               if (current.getNext() == null)
                       return false;
               current = current.getNext();
           }
           current.setNext(current.getNext().getNext());
           listcount--;
           return true;
     }
 
     public boolean contains(Object obj) {
          Node current = head;
          for (int i = 0; i< listcount; i++) {
              if (current.getNext().getData().equals(obj))
                       return true;
                   current = current.getNext();
          }
          return false;
      }
 
      public boolean isEmpty() {
            return listcount == 0;
      }
 
      public int size() {
           return listcount;
      }
 }

class Node {
      Node next;
      Object data;
      public Node(Object data) {
           this.data = data;
           this.next = null;
      }
      public Node(Object data, Node next) {
           this.data = data;
           this.next = next;
      }
      public Node getNext() {
           return next;
      }
      public void setNext(Node next) {
           this.next = next;
      }
      public Object getData() {
           return data;
      }
      public void setData(Object data) {
           this.data = data;
      }
 }

The main program :--

package com.pr;

public class MainClass {
      public static void main(String[] args) {
            CustomLinkedList list = new CustomLinkedList();
            list.add("AB");
            list.add("BC");
            System.out.println(list.size());
            System.out.println(list.isEmpty());
            System.out.println(list.contains("AB"));
            System.out.println(list.get(1));  
      }
}

Output : - 2
                false
                true
                BC


Related Post : -   
1) Internal implementation of ArrayList in Java  
2) Collection Related Interview Questions and Answers in Java(List,Map & Set)