Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Insertion in double linked list in java

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 246
    Comment on it

    Double linked list is a type of data structure that contains data in linear way but its different from single linked list because we can traverse in both direction in list. This provides previous and next pointer and node value.

    Insertion in deletion performs complexity of O(1) if insertion in start or in end but in case of any position or in middle complexity is O(n).

     

    Structure of node :

    public class Node<T> implements Comparable {
    
        private T value;
        private Node<T> nextReference;
        private Node<T> prevReference;
    
        public Node<T> getPrevReference() {
            return prevReference;
        }
    
        public void setPrevReference(Node<T> prevReference) {
            this.prevReference = prevReference;
        }
    
        public T getValue() {
            return value;
        }
    
        public void setValue(T value) {
            this.value = value;
        }
    
        public Node<T> getNextReference() {
            return nextReference;
        }
    
        public void setNextReference(Node<T> nextReference) {
            this.nextReference = nextReference;
        }
    
        @Override
        public int compareTo(Object another) {
            if (another == this.value){
                return 0;
            }else{
                return 1;
            }
        }
    }

    Class to perform insertion operation in linked list :

    public class DoubleLinkedList<T> {
    
        private Node<T> start;
        private Node<T> end;
    
        public void insertAtFirst(T value){
            Node<T> newNode = new Node<T>();
            newNode.setValue(value);
    
            if (start == null){
                start = newNode;
                end = start;
            }else{
                start.setPrevReference(newNode);
                newNode.setNextReference(start);
                start = newNode;
            }
        }
    
        public void insertAtLast(T value){
            Node<T> newNode = new Node<T>();
            newNode.setValue(value);
            if (start == null){
                start = newNode;
                end = start;
            }else{
                newNode.setPrevReference(end);
                end.setNextReference(newNode);
                end = newNode;
            }
        }
    
    
        public void insertAtPos(T value, T after){
            Node<T> tempNode = start;
            Node<T> refNode = null;
    
            while(true){
    
                if (tempNode == null){
                    break;
                }else{
                    if (tempNode.compareTo(after) == 0){
                        refNode = tempNode;
                        break;
                    }
                }
    
                tempNode = tempNode.getNextReference();
            }
    
            if (refNode != null){
                Node<T> newNode = new Node<>();
                newNode.setValue(value);
    
                tempNode = refNode.getNextReference();
                refNode.setNextReference(newNode);
                newNode.setPrevReference(refNode);
                newNode.setNextReference(tempNode);
                tempNode.setPrevReference(newNode );
    
            }
        }
    

    Insertion in double linked list is easy than insertion in single linked list.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: