Code random notes_ Linked list_ 707 design linked list

LC707. Design the list

---

Code Capriccio record two brush notes

subject

Design the realization of linked list . You can choose to use single or double linked list . Nodes in a single chain table should have two properties ：val and next.val Is the value of the current node ,next Is a pointer to the next node / quote . If you want to use a two-way linked list , Then you need an attribute prev To indicate the last node in the list . Suppose that all nodes in the list are 0-index Of .

Implement these functions in the linked list class ：

• get(index)： Get the index Values of nodes . If the index is invalid , Then return to -1.
• addAtHead(val)： Add a value of... Before the first element of the list val The node of . After inserting , The new node will be the first node in the list .
• addAtTail(val)： Will be worth val To the last element of the list .
• addAtIndex(index,val)： In the list, the index The value added before nodes is val The node of . If index It's equal to the length of the list , Then the node will be attached to the end of the list . If index Greater than the length of the list , The node will not be inserted . If index Less than 0, Then insert the node in the head .
• deleteAtIndex(index)： If the index index It works , Delete the index Nodes .

Example ：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); // Linked list becomes 1-> 2-> 3
linkedList.get(1); // return 2
linkedList.deleteAtIndex(1); // Now the list is 1-> 3
linkedList.get(1); // return 3

Ideas

Ideas ： This topic aims at the operation of adding, deleting, changing and checking the linked list . Pay attention to defining the data structure of the linked list , And some special judgments .

Code implementation

class MyLinkedList {
    

    /** *  Linked list node data structure  */
    static class ListNode{
    
        int val;
        ListNode next;
        public ListNode(int val){
    
            this.val = val;
        }
    }
    
    // Define linked list size , Head and tail nodes 
    int size;
    ListNode head;
    ListNode tail;
    /** Initialize your data structure here. */
    public MyLinkedList() {
    
        size = 0;
        head = null;
        tail = null;
    }
    
    /**  Get the value of the linked list node corresponding to the index  Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
    
        if(size != 0 && index < size){
    
            // Judge whether the length and index of the linked list are legal 
        	ListNode cur = head;
            // Traversing the linked list , Get node value 
            for(int i = 0;i < index;i++){
    
                cur = cur.next;
            }
        	return cur.val;
        }else{
    
            return -1;
        }
    }
    
    /**  The first interpolation  Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
    
        ListNode newNode = new ListNode(val);
        // Linked list is empty. 
        if(null == head){
    
            head = newNode;
            tail = newNode;
            size ++;
        }else{
    
            newNode.next = head;
            head = newNode;
            size++;
        }
    }
    
    /**  The tail interpolation  Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
    
        ListNode newNode = new ListNode(val);
        if(null == head){
    
            head = newNode;
            tail = newNode;
            size++;
        }else{
    
            tail.next = newNode;
            tail = newNode;
            size++;
        }
    }
    
    /**  Insert... According to index  -  To insert in order  Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
    
        if(index > size){
    
            return;
        }
        ListNode newNode = new ListNode(val);
        if(index == 0){
    
            //case1: The first interpolation , Insert the head of the linked list 
            newNode.next = head;
            head = newNode;
            size++;
        }else if(index == size){
    
            //case2: The tail interpolation , Insert the end of the list 
            tail.next = newNode;
            tail = newNode;
            size++;
        }else{
    
            //case3: To insert in order , current  The pointer records the current position , pre  Pointer record  cur  The previous position of the pointer 
            // When the index position is found , be  pre  Pointer link  newNode ,newNode  link  cur
            ListNode ppre = head;
            int i;
            for(i = 0;i < index - 1; i++){
    
                ppre = ppre.next;
            }
            ListNode cur = ppre.next;
            newNode.next = cur;
            ppre.next = newNode;
            size++;
        }

    }
    
    /**  Delete node according to index  Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
    
        if (size != 0 && index < size) {
    
            if (index == 0) {
    
                 //case1: The deleted node is the head node 
                head = head.next;
                size--;
                if (size == 0) {
    
                    tail = head;
                }
            } else {
    
                ListNode prev = head;
                for (int i = 1; i < index; i++) {
    
                    prev = prev.next;
                }
                if(index == size-1){
    
                    //case2: The deleted node is the tail node 
                    tail = prev;
                    size--;
                    return;
                }else {
    
                    //case3: The deleted node is the intermediate node 
                    ListNode cur = prev.next;
                    prev.next = cur.next;
                    size--;
                    return;
                }
            }
        }else{
    
            //case4: The deleted node does not exist 
            System.out.println("the element is not exist");
            return;
        }
    }
}

---

summary

This topic mainly examines the basic skills of adding, deleting, changing and checking linked lists . You need to pay attention to some special cases of insertion and deletion .