Implementing Single Linked List in Java

Before I start, let me caution you that this post is not about LinkedList [Java Doc] API of Java. LinkedList API of Java is a specialized implementation of doubly linked list. This post talks in general about linked data structures (i.e. linked list) and implementation of single linked list in Java.

Definition

Linked data structures are composed of distinct chunks of memory; and these chunks are bounded/linked through pointers. These memory chunks are referred as nodes. As nodes are not stored in contiguous memory so adding or removing individual nodes is quite easier (unlike an array). But one drawback is that random access to node is not possible. 

typedef struct node {
         item_type item;  //data stored in node
         struct list *next;  //points to successor 
}node;

In C language; *p denotes the item that is pointed to by pointer p, and &x denotes the address (i.e. pointer) of a particular variable x. A special null value is used to denote the termination of the list. 

C pointers are similar to Java references; as both of them point to something.

Let's cover them in detail

C pointers:
    int var = 20; 
    int *ip;   //pointer to an integer
    ip = &var;  //store address of var in pointer ip

Java references:
     Integer x = new Integer(20);  //x is reference to Integer

Usually, Java references are implemented as pointers in C; but specification doesn't say it explicitly. Java reference should be just an abstraction on C pointers (i.e. references in Java will be implemented using C pointers). I am not going to stress if both are same or not; it's debatable!

Implementation

Below is custom single linked list implementation in Java. I have just provided add and print method.

package algo;  
   
 /**  
  * Generic single linked list implementation with generics  
  *   
  * @author Siddheshwar   
  */  
 public class SingleLinkedList<E> {  
      Node<E> start; // points to the head or first node  
   
      /**  
       * Node class    
       */  
      private class Node<E> {  
           E data;  
           Node<E> next;  
   
           public Node(E data, Node<E> next) {  
                this.data = data;  
                this.next = next;  
           }  
   
           public E getData() {  
                return data;  
           }  
   
           public Node<E> getNext() {  
                return next;  
           }  
   
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
   
      public void add(E d) { // add at the end of list  
           if (start == null) {  
                start = new Node<E>(d, null);  
           } else {  
                Node<E> tmp = start;  
                while (tmp.next != null) {  
                     tmp = tmp.next;  
                }  
                tmp.setNext(new Node<E>(d, null));  
           }  
      }  
   
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list are :");  
           while (current != null) {  
                System.out.print(current.getData() + "--> ");  
                current = current.getNext();  
           }  
           System.out.println("null");  
      }  
   
      public static void main(String[] args) {  
           SingleLinkedList<String> sll = new SingleLinkedList<>();  
           sll.add("abc");  
           sll.add("def");  
           sll.print();  
      }  
 } 

Output : 
values in link-list are :abc--> def--> null

Complexity of common operations 

1.  Insert/Update/delete at end of list: O(n) . Need to traverse whole list.  
2.  Insert at the beginning/head of the list : O(1)
3.  Find the size of list : O(n). But it can be achieved in O(1) if you keep track of the count in a separate attribute (increment its value on each addition and decrement on each deletion).

References from Java

1. LinkedList  [Java Doc] : Doubly linked list implementation of the List and Deque interfaces.
2. LinkedHashMap [Java Doc] : Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. Linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map.
3. LinkedHashSet [Java Doc] : Hash table and linked list implementation of the Set interface, with predictable iteration order.

Related Post :Implementing Doubly linked list in Java