Wednesday, April 17, 2013

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.

6 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. Greetings! Very useful advice within this article! It is the little
    changes that make the largest changes. Thanks a lot for sharing!


    my web-site ... Corrie Morgen

    ReplyDelete
  3. It's going to be end of mine day, but before ending I am reading this impressive paragraph to increase my knowledge.


    My webpage: After Effects Tutorial

    ReplyDelete
  4. Hello mates, nice piece of writing and good urging
    commented at this place, I am truly enjoying by these.

    Here is my webpage - product design and development

    ReplyDelete
  5. Thanks for ones marvelous posting! I truly enjoyed reading it, you're a great author.I will remember to bookmark your blog
    and will eventually come back down the road.
    I want to encourage you to continue your great work,
    have a nice evening!

    My blog post ... cubic zirconia

    ReplyDelete