How to implement singly linked listing inward Java using Generics

Linked listing is a pop information construction for writing programs together with lots of questions from linked listing is asked inwards various data structures together with algorithmic interviews. Though Java provides a audio implementation of Doubly linked listing as java.util.LinkedList, all these interview questions require you lot to code linked listing inwards Java. If you lot are non comfortable to brand a linked list, it would last actually hard to solve questions similar reversing a linked listing or finding middle chemical constituent of linked list. Java v brought around other twist of this form of questions, straight off interview expects you lot to write a type-safe implementation of linked listing using Generics. This enhance difficulty score every bit writing parameterized cast is non slowly inwards Java, together with it requires a practiced agreement of Generics fundamental.

This enquiry too offers you lot an chance to larn a improve programmer, solving data construction based questions are a lot improve than trying piddling examples, It non exclusively helps to improve programming science only too prepares you lot for Java interviews.

I bring already shared an implementation of linked listing without generics inwards an before post service of unit of measurement testing linked listing inwards Java, together with hither nosotros volition encounter a type safe, parameterized implementation of singly linked listing inwards Java.

How to implement linked listing inwards Java using Generics

Linked listing is a information construction which is used to shop information inwards the cast of nodes. As opposed to an array, which stores information inwards a contiguous retention location, linked listing stores information at dissimilar places. Each node contains a information together with a reference part, reference role contains an address or side past times side node. In brusk linked listing is a listing of nodes, which are linked together. See the difference betwixt linked listing together with array inwards Java  for to a greater extent than differences.

In club to do a linked listing inwards Java, nosotros demand 2 classes a Node together with a SinglyLinkedList cast which contains the address of outset chemical constituent together with diverse methods to piece of job on linked list.

There are mainly 2 kinds of linked list, Singly together with Doubly linked list. Singly linked listing allows you lot to traverse inwards i direction, field doubly linked listing allows you lot to traverse inwards both frontwards together with contrary direction. In this example, nosotros volition implement singly linked list, amongst an append() method which insert elements at the tail.

Java Program to implement Singly linked list 

package datastructure;  /**   * Type Safe implementation of linked listing inwards Java amongst Generics.   * This event creates a singly linked listing amongst append(), isEmpty() together with length() method.    * @author Javin   */ public class SinglyLinkedList {     private Node head;  // Head is the outset node inwards linked list      public boolean isEmpty(){         return length() == 0;     }       public void append(T data){         if(head == null){             caput = new Node(data);             return;         }         tail().next = new Node(data);     }       private Node tail() {         Node tail = head;               // Find terminal chemical constituent of linked listing known every bit tail         while(tail.next != null){             tail = tail.next;         }               return tail;           }          @Override     public String toString(){         StringBuilder sb = new StringBuilder();         Node electrical flow = head;         while(current != null){            sb.append(current).append("-->");            electrical flow = current.next;         }             if(sb.length() >=3){             sb.delete(sb.length() - 3, sb.length()); // to take away --> from terminal node         }               return sb.toString();     }      public int length() {        int length = 0;        Node electrical flow = head;  // Starts counting from caput - outset node        while(current != null){            length ++;            electrical flow = current.next;        }        return length;     }        // Node is nested static cast because it exclusively exists along amongst linked list     // Node is somebody because it's implementation detail, together with should non last exposed     private static class Node {         private Node next;         private T data;          public Node(T data) {             this.data = data;         }          @Override         public String toString() {             return data.toString();         }     } }

Now, let's do a sample programme to assay this linked list implementation.

Test Program to assay Singly linked list

/**   * Java programme to do singly linked listing of String together with Integer type,   * to banking concern represent type safety.   * @author Javin   */ public class LinkedListTest {      public static void main(String args[]) {          // Creating Singly linked listing inwards Java of String type         SinglyLinkedList singlyLinkedList = new SinglyLinkedList();         singlyLinkedList.append("Java");         singlyLinkedList.append("JEE");         singlyLinkedList.append("Android ");         //singlyLinkedList.append(2); // compile fourth dimension error               System.out.println("Singly linked listing contains : " + singlyLinkedList);         System.out.println("length of linked listing : " + singlyLinkedList.length());         System.out.println("is this linked listing empty : " + singlyLinkedList.isEmpty());               SinglyLinkedList iList = new SinglyLinkedList();         iList.append(202);         iList.append(404);         //iList.append("one"); // compilation mistake - Trying to insert String on integer list         System.out.println("linked listing : " + iList);         System.out.println("length : " + iList.length());     }   }  Output Singly linked listing contains: Java-->JEE-->Android the length of linked list: 3 is this linked listing empty: false linked list: 202-->404 Length: 2

That's all on how to brand linked listing inwards Java using Generics. As a follow-up question, Interview may inquire you lot to implement circular linked list, or implement doubly linked listing inwards Java. You tin too exercise them every bit an exercise to improve your coding skills. Apart from implementing a dissimilar form of linked list, Interviewer is too interested on implementing diverse methods e.g. insert a node at the start, middle together with destination of linked list, delete a node from the start, middle together with destination of linked list, sorting elements of linked list, searching a node inwards linked list etc. If you lot bring time, you lot tin abide by a lot of practiced questions on linked list, only cry back outset to start amongst implementing singly linked listing inwards Java.

Further Reading
Algorithms together with Data Structures - Part 1 together with 2
Java Fundamentals, Part 1 together with 2
Cracking the Coding Interview - 189 Questions together with Solutions

Further Reading
How to implement Binary Search tree inwards Java? (solution)
How to abide by the length of singly linked list? (answer)
How to implement QuickSort using recursion inwards Java? (solution)
How to banking concern represent if a linked listing contains a loop or wheel inwards Java? (answer)
How to take away duplicates from ArrayList inwards Java (solution)
150 Programming Questions together with Solutions for Interviews (book)

Share on Facebook

Share on Twitter

Share on Google+

Share on LinkedIn

Subscribe to receive free email updates: