LinkedList Design

Design Single LinkedList

High Level

Middle Level:

• addHead/addTail/addIndex

• deleteHead/deleteTail/deleteIndex

  • 为啥deleteTail/deleteIndex会比较麻烦？

• size/isEmpty/get/getSize/searchByValue

TC&SC: O(n)

class ListNode{ 
    int value;
    ListNode next;
    
    @Override
    public String toString() {
        return "this value : " + value;
    }
}

class LinkedList {
    // Field 属性：静态的属性
    // Method 行为：动态的行为
    ListNode head;
    int size;
    
    public LinkedList(){
        this.head = null;
        this.size = 0;
    }
    
    public ListNode searchByValue(int value){
        ListNode cur = head;
        while (cur != null) {
            if (cur.value == value) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    
    public ListNode get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }
    
    public getSize(){
        return this.size;
    }
    
    public boolean isEmpty(){
        return this.size == 0;
    }
    
    public void printAllNodes(){
        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur);
            cur = cur.next;
        }
    }
    
    // 增
    public void addHead(int val){
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    public void addTail(int val){
        ListNode newNode = ListNode(val);
        if (head == null) {
            head = newNode;
        }
        else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
        }
        size++;
    }
    public void addIndex(int index, int val){
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            addHead(val);
            return;
        }
        if (index == size - 1) {
            addTail(val);
            return;
        }
        ListNode cur = head;
        ListNode newNode = new ListNode(val);
        //要想在index 这个位置插入一个node，需要找到index -1的这个node，然后在这个node之后加入新的node
        for (int i = 0; i < index - 1; i++) {
           cur = cur.next;  
        }
        //在中间插入node的方法一定是 先保留后面的node 再做插入
        newNode.next = cur.next;
        cur.next = newNode;
        size+=;
    }
    // 删
    public void deleteHead() {
        if (head == null) {
            return;
        }
        head = head.next;
        size--;
    }
    public void deleteTail() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            deleteHead();
            return;
        }
        ListNode cur = head;
        ListNode nextNode = head.next;
        while (cur.next != null && nextNode.next != null) {
            cur = cur.next;
            nextNode = nextNode.next;
        }
        cur.next = null;
        // ListNode prev = null;
        // ListNode cur = head;
        // while(cur.next != null) {
            //现在的cur，就是下一轮的prev
            //prev = cur;
            //cur = cur.next;
        //}
        // prev.next = null;
        size--;
    }
    
    public void deleteAtIndex(int index){
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            deleteHead();
            return;
        }
        if (index == size - 1) {
            deleteTail();
            return;
        }
        ListNode toBeDeletePrev = head;
        for (int i = 0; i < index - 1; i++){
            toBeDeletePrev = toBeDeletePrev.next;
        }
        toBeDeletePrev.next = toBeDeletePrev.next.next;
        size--;
    }
}

Design Double LinkedList

High Level

Middle Level:

• addHead/addTail/addIndex

• deleteHead/deleteTail/deleteIndex

  • 为啥deleteTail/deleteIndex会比较麻烦？

• size/isEmpty/searchByValue

TC&SC: O(n)

class ListNode{ 
    int value;
    ListNode next;
    
    @Override
    public String toString() {
        return "this value : " + value;
    }
}

class LinkedList {
    // Field 属性：静态的属性
    // Method 行为：动态的行为
    ListNode head;
    ListNode tail;
    int size;
    
    public LinkedList(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    public ListNode seachByValue(int value){
        ListNode cur = head;
        while (cur != null) {
            if (cur.value == value) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    
    public ListNode get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }
    
    public getSize(){
        return this.size;
    }
    
    public boolean isEmpty(){
        return this.size == 0;
    }
    
    public void printAllNodes(){
        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur);
            cur = cur.next;
        }
    }
    
    // 增
    public void addHead(int val){
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            tail = newNode;
        }
        else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++
    }
    public void addTail(int val){
        ListNode newNode = ListNode(val);
        if (head == null) {
            head = newNode;
            tail = newNode;
        }
        else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }
    public void addIndex(int index, int val){
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            addHead(val);
        }
        if (index == size - 1) {
            addTail(val);
        }
        ListNode cur = head;
        ListNode newNode = new ListNode(val);
        for (int i = 0; i < index - 1; i++) {
            cur.next = cur;
        }
        ListNode prev = cur;
        ListNode next = cur.next;
        newNode.next = next;
        next.prev = newNode;
        prev.next = newNode;
        newNode.prev = prev;
        size++;  
    }
    // 删
    public void deleteHead() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = null;
            tail = null;
            size = 0;
            return;
        }
        ListNode newHead = head.next;
        newHead.prev = null;
        head.next = null;
        head = newHead;
        size--;
        return;
    }
    
    public void deleteTail() {
         if (head == null) {
            return;
        }
        if (head.next == null) {
            head = null;
            tail = null;
            size = 0;
            return;
        }
        ListNode temp = tail;
        tail = tail.prev;
        temp.prev = null;
        tail.next = null;
        size--;
    }
    
    public void deleteAtIndex(int index){
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            deleteHead();
            return;
        }
        if (index == size - 1) {
            deleteTail();
            return;
        }
        ListNode toBeDeletePrev = head;
        for (int i = 0; i < index - 1; i++){
            toBeDeletePrev = toBeDeletePrev.next;
        }
        ListNode prev = toBeDeletePrev.prev;
        ListNode next = toBeDeletePrev.next;
        prev.next = next;
        next.prev = prev;
        toBeDeletePrev.prev = null;
        toBeDeletePrev.next = null;
        size--;
    }
    public void deleteNode(ListNode toBeDeleted) {
        ListNode prevNode = toBedeleted.prev;
        ListNode nextNode = toBedeleted.next;
        if (prevNode == null) { //  toBedeleted is head
            ListNode temp = head;
            head = head.next;
            head.prev = null;
            temp.next = null;
        }
        if (nextNode == null) {
            ListNode temp = tail;
            tail = tail.prev;
            tail.next = null;
            temp.prev = null;
        }
        prev.next = nextNode;
        next.prev = prevNode;
        toBeDeletePrev.prev = null;
        toBeDeletePrev.next = null;
        size--;
    }
}

Design Circular LinkedList

class ListNode{ 
    int value;
    ListNode next;
    
    @Override
    public String toString() {
        return "this value : " + value;
    }
}

class LinkedList {
    // Field 属性：静态的属性
    // Method 行为：动态的行为
    ListNode head;
    int size;
    
    public LinkedList(){
        this.head = null;
        this.size = 0;
    }
    
    public ListNode searchByValue(int value){
        ListNode cur = head;
        while (cur != head) {
            if (cur.value == value) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    public ListNode get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }
    
    public getSize(){
        return this.size;
    }
    
    public boolean isEmpty(){
        return this.size == 0;
    }
    
    public void printAllNodes(){
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur.next != head) {
            System.out.println(cur);
            cur = cur.next;
        }
        System.out.println(cur);
    }
    
    // 增
    public void addHead(int val){
        // corner case : only have zero or one?
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            head.next = head;
        }
        if (head.next == null) {
            head.next = newNode;
            newNode.next = head;
            head = newNode;
        }
        ListNode cur = head;
        // find tail
        while (cur.next != head) {
            cur = cur.next;
        }
        cur.next = newNode;
        newNode.next = head;
        head.next = null;
        head = newNode;
        size--;
    }
    public void addTail(){
        // find tail
        // corner case : only have zero or one?
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            head.next = head;
        }
        ListNode cur = head;
        // find tail
        while (cur.next != head) {
            cur = cur.next;
        }
        cur.next = newNode;
        newNode.next = head;
        head.next = null;
        head = newNode;
        size++;
    }
    public void addIndex(int index, int val){
        if (index < 0) {
            return;
        }
        if (index > size) {
            index = index % size;
        }
        // corner case
        if (index == 0) {
            addHead(val);
        }
        if (index == size - 1) {
            addTail(val);
        }
        ListNode cur = head;
        ListNode newNode = new ListNode(val)
        // find index - 1 th Node
        for (i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        
        // find index th Node 
        ListNode nextNode = cur.next;
        
        // add newNode between them
        newNode.next = nextNode;
        cur.next = newNode;
        size++;
    }
    // 删
    public void deleteHead() {
        // corner case
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = null;
            size--;
            return;
        }
        
        // find head.next
        ListNode nextNode = head.next;
        
        // find tail
        ListNode cur = head;
        while (cur.next != head) {
            cur = cur.next;
        }
        ListNode prev = cur;
        
        // link tail and head.next
        prev.next =nextNode;
        
        // clear anything related to head
        head.next = null;
        
        // reset head
        head = nextNode;
        
        // size--
        size--;
    }
    public void deleteTail() {
        // corner case
        if (head == null) {
            return;
        }
        if (head.next = null) {
            head = null;
            size--;
            return;
        }
        // find prev: the previous Node of tail
        ListNode cur = head;
        ListNode prev = null;
        // link head and prev
        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }
            // prev is the previous node of tail, cur is the tail now
        prev.next = head;
        // clear tail's pointer
        cur.next = null;
        size--;
    }
    
    public void deleteAtIndex(int index){
     // corner case
        if (index < 0) {
            return;
        }
        if (index > size) {
            index = index % size;
        }
        if (index == 0) {
            deleteHead();
        }
        if (index == size - 1) {
            deleteTail();
        }
        ListNode cur = head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;   
        }
     
     // find index - 1 th ListNode
     
     // find index + 1th ListNode
         cur.next = cur.next.next;
         size--;
         return;
    }

}

class ListNode{ 
    int value;
    ListNode next;
    
    @Override
    public String toString() {
        return "this value : " + value;
    }
}

class LinkedList {
    // Field 属性：静态的属性
    // Method 行为：动态的行为
    ListNode head;
    int size;
    
    public LinkedList(){
        this.head = null;
        this.size = 0;
    }
    
    public ListNode searchByValue(int value){
        ListNode cur = head;
        while (cur != null) {
            if (cur.value == value) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    
    public ListNode get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }
    
    public getSize(){
    
    }
    
    public boolean isEmpty(){
    
    }
    
    public void printAllNodes(){
    }
    
    // 增
    public void addHead(){
    
    }
    public void addTail(){
    
    }
    public void addIndex(int index, int val){
    
    }
    // 删
    public void deleteHead() {
    
    }
    public void deleteTail() {
    
    }
    
    public void deleteAtIndex(int index){
    
    }

}