DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Design LinkedList

Problem

class MyLinkedList {
    Node head;
    Node tail;
    int size = 0;
    public MyLinkedList() {
    }

    public int get(int index) {
        if(index<0 || index>=size) return -1;
        Node temp = head;
        int c = 0;
        while(temp!=null){
            if(c == index) return temp.val;
            c++;
            temp = temp.right;
        }
        return -1;
    }

    public void addAtHead(int val) {
        if(head==null && tail==null){
            Node node = new Node(val);
            head = node;
            tail = node;
        }
        else {
            Node node = new Node(val);
            node.right = head;
            head.left  = node;
            head = node;
        }
        size++;
        //print("add at head val: "+ val, head);
    }

    public void addAtTail(int val) {
        if(head==null && tail==null){
            Node node= new Node(val);
            head = node;
            tail = node;
        }
        else{
            Node node = new Node(val);
            tail.right = node;
            node.left = tail;
            tail = node;
        }
        size++;
        //print("add at tail: "+val, head);
    }

    public void addAtIndex(int index, int val) {
        if(index<0 || index> size) return;
        if(index == size){
            //add at tail
            addAtTail(val);
            return;
        }
        else if(index ==0){
            addAtHead(val);
            return;
        }
        //Otherwise add at somewhere in the middle
        Node node = new Node(val);
        Node temp = head;
        int c = 0;
        while(temp!=null){
            if(c == index) break;
            c++;
            temp = temp.right;
        }
        Node leftPartNode  = temp.left;
        node.right = temp;
        temp.left  =node;
        leftPartNode.right = node;
        node.left = leftPartNode;
        size++;
        //print("after add at index "+index +",val "+ val , head);
    }

    public void deleteAtIndex(int index) {
        if(index<0 || index>=size) return;
        if(head == tail){
            head =null;
            tail =null;
            size--;
            return;
        }
        if(index ==0){
            head = head.right;

        }
        else if(index == size-1){
            tail = tail.left;
            tail.right = null;
        }
        else{
            int c= 0;
            Node temp  = head;
            while(temp!=null){
                if(c == index) break;
                c++;
                temp = temp.right;
            }
            Node leftPartNode = temp.left;
            Node rightPartNode = temp.right;
            leftPartNode.right = rightPartNode;
            rightPartNode.left = leftPartNode;
            temp.left  =null;
            temp.right = null;
        }
        size--;
       // print("deletion at index "+index, head);
    }
    public void print(String purpose, Node head){
        System.out.println(purpose + ",current list size "+ size);
        Node temp  = head;
        System.out.print("null<-");
        while(temp!=null){
            System.out.print(temp.val +"->");
            temp = temp.right;
        }
        System.out.print("null");
        System.out.println();
    }
}
class Node{
    Node left;
    Node right;
    int val;
    public Node(int d){
        this.val = d;
    }
    public Node(int d, Node l, Node right){
        this.val = d;
        this.left = l;
        this.right = right;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
Enter fullscreen mode Exit fullscreen mode

Top comments (0)