Code Pumpkin

Linked List

March 31, 2017
Posted by Pumpkin
Subscribe

LinkedList

A linked list is a dynamic data structure which is consist of nodes and links. The number of nodes in a list is not fixed and can grow and shrink on demand.

As Discussed in previous article of ArrayList, this structure will provide us more space effective insertion/deletion for intermediate elements. In this structure it will be easier to add/remove elements at starting/end of the list.

Our LinkedList implementation will support below operations:

size – returns size of the LinkeList

isEmpty – Returns whether the list is empty.

get – Returns (but does not remove) the element at index i.

addAfter – Insert ad element after the given index

addFirst – Insert an element e at the start of the list

addLast – Insert an element e at the end of the list

remove – Removes the first occurrence of the element from the list

removeFirst – Removes and returns the first element value of the linked list

Implementation

As linked list is made of nodes which are connected with each-others with links. We will create Node inner class which will hold value of element and reference to next node.

In our main class, we will have head node, tail node and size variable to hold the size of the linkedlist. Below is code implementation for our linkedlist.

LinkedList Implementation


import java.util.NoSuchElementException;
 
public class SinglyLinkedList< E> {
 
     
    public SinglyLinkedList() {
    }
     
     
    /**
     * This inner class will hold the value of element and link to the next node.
     *
     */
    private static class Node< E>{
        private E element;
        private Node< E> next;
        public Node(E e, Node< E> n){
            element = e;
            next = n;
        }
         
        public E getElement(){
            return element;
        }
         
        public Node< E> next(){
            return next;
        }
         
        public void setNext(Node< E> n){
            next=n;
        }
    }
    /**
      * This will hold the first element of the linkedlist 
      */
    public Node< E> head=null;
    /**
      * This will hold the last element of the linkedlist
      */
    public Node< E> tail=null;
    /**
      * This will hold the size of the linkedlist
      */
    public int size=0;
     
     
    /**
      * This method is to check for current size of linkedlist
      * Complexity: O(1) as we need to return size element 
      */
    public boolean isEmpty(){
        return size==0;
    }
     
    /**
      * This method will return first element of linkedlist which is element in head
      * Complexity: O(1) as we have to return head element
      */
    public E first(){
        return head != null?head.getElement():null;
         
    }
     
    /**
      * This method will return last element of linkedlist which is element in tail
      * Complexity: O(1) as we have to return tail element
      */
    public E last(){
        return tail != null?tail.getElement(): null;
    }
     
    /**
      * This method is for adding element at the end of the linked list.
      * we are creating a new node for given element and change the reference with tail element
      * Complexity: O(1) as we have to just add element and set reference
      *
      */
    public void addLast(E e){
        Node< E> newest= new Node<>(e,null);
        if(isEmpty()){
            head= newest;
        }else{
            tail.setNext(newest);
        }
        tail = newest;
        size++;
    }
     
    /**
      * This method is for adding element at the starting of the linked list.
      * we are creating a new node for given element and change the reference with head element
      * Complexity: O(1) as we have to just add element and set reference  
      */
    public void addFirst(E e){
        head = new Node<> (e,head);
        if(isEmpty()){
            tail=head;
        }
        size++;
    }
     
    /**
      * This method is for removing element at the start of the linked list.
      * we than change the reference of head element and return the removed element
      * Complexity: O(1) as we have to just remove reference
      *   
      */
    public E removeFirst(){
        if(isEmpty()){
            return null;
        }
        E ele = head.element;
        head = head.next();
        size--;
        if(size==0)
            tail= null;
        return ele;
    }
     
    /**
      * This method is for retrieving element at given index i
      * Complexity: O(n) as we have to iterate to get to the given index  
      */
    public E get(int i){
        if(isEmpty()){
            return null;
        }
        Node< E> n = head;
        while(i>0){
            if(n.next == null)
                throw new IndexOutOfBoundsException();
            n = n.next;
            i--;
        }
        return n.getElement();
    }
     
    /**
      * This method is for removing first occurrence of given element from the linkedlist.
      *  Complexity: O(n) as we have to iterate to get to the given element 
      */
    public E remove(E v){
        if(isEmpty()){
            return null;
        }
        Node< E > n = head;
        while(n.element != v){
            if(n.next == null){
                throw new NoSuchElementException();
            }
            n=n.next;
        }
        size--;
        return n.element;
    }
     
    /**
      * This method is for adding new element after given index in the linkedlist
      * Complexity: O(n) as we have to iterate to get to the given index
      *   
      */
     public void addAfter(int i, E v) {
            Node< E > n = head;
            while(i>0) {
                if (n.next == null) {
                    throw new IndexOutOfBoundsException();
                }
                n = n.next;
                i--;
            }
            Node< E> newNode = new Node< E>(v,n.next);
            n.next = newNode;
            size++;
        }
      
     public static void main(String[] args){
             SinglyLinkedList< Integer > myList = new SinglyLinkedList<>();
             myList.addFirst(10);
             myList.addLast(20);
             myList.addLast(40);
             myList.addAfter(1, 30);
             System.out.println(myList.get(2));
             myList.addLast(50);            
         }
     
}

In addition to that, you can also think of some possible solution by which we can improve performance for accessing the element in linked list.

Here if you have observed the structure, if I want to go to any element in the middle of the list then I have to traverse through all the elements from the beggining. Lets take one more case, what if I want to access second last element in the list. I have to iterate to all the elements of list to reach the last element.

Now to resolve the above mentioned issue, we have few options. One of which is Doubly Linked List, where we can have link to next element and previous element as well. In this data structure we can have advantage of moving forward and backward both but this comes with an additional space to hold the link to previous element. You can go and try to implement the Doubly Linked List data strucure yourself.

To know detailed overview of when we should be using which (ArrayList/LinkedList) check the answers on SO here.

Happy Learning 🙂

Download Complete Java Program »

Tags: , , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank