Custom LinkedList implementation using Java

LinkedList is one of the most used data structure. We know how to use java.util.LinkedList class in Java. But, most of them are not aware, how it has been implemented it’s methods internally. Please have a look at below program to know how LinkedList will work internally.

Note: This is not exactly equal to the java.util.LinkedList implementation. This is a custom implementation of LinkedList class.

package com.ds.practice.linked;

public class LinkedList<T> {
 Node head;

 static class Node<T> {
  Node next;
  T data;

  public Node(T data) {
   this.data = data;
   next = null;
  }
 }

 public void add(T new_data) {
  addLast(new_data);
 }

 public void addFirst(T new_data) {
  Node new_node = new Node<Object>(new_data);
  new_node.next = head;
  head = new_node;
 }

 public void add(Node prevNode, T new_data) {
  if (prevNode == null) {
   System.out.println("The give previous Node can't be null");
   return;
  }

  Node new_Node = new Node<Object>(new_data);
  new_Node.next = prevNode.next;
  prevNode.next = new_Node;

 }

 public void addLast(T new_data) {
  if (head == null) {
   head = new Node<Object>(new_data);
   return;
  }

  Node new_node = new Node<Object>(new_data);
  new_node.next = null;

  Node last = head;
  while (last.next != null)
   last = last.next;

  last.next = new_node;
  return;
 }

 public void print() {
  if (head == null) {
   System.out.println("LinkedList is empty");
   return;
  }

  Node tempNode = head;
  while (tempNode != null) {
   System.out.println(tempNode.data + "");
   tempNode = tempNode.next;
  }
 }

 @SuppressWarnings("unchecked")
 public T removeFirst() {
  if (head == null)
   return null;

  Node temp = head;
  if (temp.next == null) {
   head = null;
  } else {
   head = temp.next;
  }
  return (T) temp.data;
 }

 @SuppressWarnings("unchecked")
 public T remove(T data) {
  Node temp = head, prev = null;
  if (temp != null && temp.data == data) {
   head = temp.next;
   return (T) temp.data;
  }

  while (temp != null && temp.data != data) {
   prev = temp;
   temp = temp.next;
  }

  if (temp == null)
   return null;

  prev.next = temp.next;
  return (T) temp.data;
 }

 @SuppressWarnings("unchecked")
 public T removeLast() {
  Node temp = head;
  while (temp.next.next != null)
   temp = temp.next;
  T result = (T) temp.next.data;
  temp.next = null;
  return result;
 }

 public int size() {
  Node temp = head;
  int count = 0;
  while (temp != null) {
   count++;
   temp = temp.next;
  }
  return count;

 }

 public boolean search(T data) {
  Node temp = head;

  while (temp != null) {
   if (temp.data == data)
    return true;

   temp = temp.next;
  }

  return false;

 }

 public static void main(String[] args) {
  LinkedList<Integer> inList = new LinkedList<Integer>();
  inList.add(2);
  inList.addFirst(1);
  inList.addLast(4);
  inList.add(inList.head.next, 4);
  inList.print();
  System.out.println();
  System.out.println("Removed from LinkedList: " + inList.remove(25));
  inList.print();
  System.out.println(inList.search(10));
  System.out.println("Size of the LinkedList is: " + inList.size());
  System.out.println("\n");
  LinkedList<String> stList = new LinkedList<String>();
  stList.add("Subba");
  stList.addLast("Reddy");
  stList.addFirst("Nallamachu");
  System.out.println("Removed First element: " + stList.removeFirst());
  System.out.println("Removed Last element: " + stList.removeLast());
  stList.print();
 }

}

Advertisement