Internal Implementation of LinkedList in Java

      In the previous post, we discussed the internal working of ArrayList. In this post, we will explore the internal working of LinkedList and understand the implementation of its main methods.

A LinkedList is a linear data structure in which each element is stored as a separate object called a node. Each node consists of two parts: the data and a reference to the next node in the list. The last node contains a reference to null, indicating the end of the list.

The entry point to a linked list is called the head. It is important to note that the head is not a separate node; rather, it is a reference to the first node in the list. If the list is empty, the head reference is null.

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)