> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-17-2022-707.-design-linked-list.md).

# 04/17/2022 707. Design Linked List

//Original one double linkedlist

* Time complexity: O(1) for addAtHead. O(N) addAtTail. O(N) for get, addAtIndex, and deleteAtIndex.
* Space complexity: O(1) for all operations.

```
// Some code
class MyLinkedList {
    int size;
    Node head;
    Node tail;

    public MyLinkedList() {
       size = 0;
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.prev = head;
    }
    
    
    public int get(int index) {
        if (index >= size || index < 0) return -1;
        Node curr = head;
        
        for (int i = 0; i < index + 1; i++){
            curr = curr.next;
        }
        return curr.val;
    }
    
    //Time O(1)
    public void addAtHead(int val) {
        addAtIndex(0,val);
        
    }
    
    //Time O(N)
    public void addAtTail(int val) {
       addAtIndex(size, val);
    }
    
    //Time O(k) k = index
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;//need to check with the interviewer
        
        size++;
        Node pred = head;
        //find the predecessor
        for (int i = 0; i < index; i++){
            pred = pred.next;
        }
        Node toAdd = new Node(val);
        
        //get the succecessor
        Node succ = pred.next;
        toAdd.next = succ;
        toAdd.prev = pred;
        succ.prev = toAdd;
        pred.next = toAdd;
    }
    
    //Time O(N)
    public void deleteAtIndex(int index) {
        if (index >= size) return;
        if (index < 0) index = 0;
        size--;
        Node pred = head;
        for (int i = 0; i < index; i++){
            pred = pred.next;
        }
        Node succ = pred.next.next;
        pred.next = succ;
        succ.prev = pred;
        
    }
    
    private class Node{
        int val;
        Node prev;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }
}

/**
 * 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);
 */
```

//optimized

* Time complexity: O(1) for addAtHead and addAtTail. O(min(k,N−k)) for get, addAtIndex, and deleteAtIndex, where k is an index of the element to get, add or delete.
* Space complexity: O(1) for all operations.

```
// Some code
class MyLinkedList {
    int size;
    Node head;
    Node tail;

    public MyLinkedList() {
       size = 0;
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.prev = head;
    }
    
    //optimzied O(min(k, n-k)
    public int get(int index) {
        if (index >= size || index < 0) return -1;
        
        Node curr = head;
        //decide to move from the head or from the tail by the index
        if (index + 1 < size - index){
           for (int i = 0; i < index + 1; i++)
            curr = curr.next;
        } else {
               curr = tail;
           for (int i = 0; i < size - index; i++){
               curr = curr.prev;
           }
        }
        
        
        return curr.val;
    }
    
    //Time O(1)
    public void addAtHead(int val) {
        Node toAdd = new Node(val);
        Node pred = head;
        Node succ = head.next;
        
        toAdd.next = succ;
        toAdd.prev = head;
        pred.next = toAdd;
        succ.prev = toAdd;
        size++;
        
    }
    
    //Time O(1) optimized
    public void addAtTail(int val) {
       Node toAdd = new Node(val);
       Node pred = tail.prev;
       Node succ = tail;
        
       toAdd.next = succ;
       toAdd.prev = pred;
       pred.next = toAdd;
       tail.prev = toAdd;
       size++;
    }
    
    //Time Optimized O(min(k, n-k)
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;//need to check with the interviewer
        
        Node pred, succ;
        if (index < size - index){
            pred = head;
            for (int i = 0 ; i < index; i++){
                pred = pred.next;
            }
            succ = pred.next;
        } else{
            succ = tail;
            for (int i = 0; i < size - index; i++){
                succ = succ.prev;
            }
            pred = succ.prev;    
        }
        size++;
        Node toAdd = new Node(val);
        
        toAdd.next = succ;
        toAdd.prev = pred;
        succ.prev = toAdd;
        pred.next = toAdd;
    }
    
    //Time O(min(k, n-k)
     public void deleteAtIndex(int index) {
        if (index >= size) return;
        if (index < 0) index = 0;
        
        Node pred, succ;
        if (index < size - index){
            pred = head;
            for (int i = 0; i < index; i++){
                pred = pred.next;
            }
            succ = pred.next.next;//noted
        } else {
            succ = tail;
            for (int i = 0; i < size - index - 1; i++){// note the index here
                succ = succ.prev;
            }
            pred = succ.prev.prev;//nodted
        }
        size--;
        pred.next = succ;
        succ.prev = pred;
        
    }
    
    private class Node{
        int val;
        Node prev;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }
}

/**
 * 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);
 */
```