單連結清單增删改查

單連結清單

• • 節點類
  • 連結清單類
  • 插入到最後
  • 按順序插入（完成後，連結清單有序）
  • 更新節點
  • 删除節點
  • 單連結清單反轉

節點類

class Node{
    public int id;
    public String name;
    public Node next;    //指向下一個節點

    public Node() {
    }

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
           

連結清單類

class SingleLinkedList{
    //單連結清單對象
    private Node head;   //頭節點

    public SingleLinkedList() {
    }

    public SingleLinkedList(Node head) {
        this.head = head;
    }
}
           

下面的兩個插入方法是SingleLinkedList裡面的方法

插入到最後

//單連結清單添加節點到最後的方法的方法
    public void add(Node node){
        //需要一個中間變量來周遊
        Node cur = head;
        //走到最後
        while(true){
            if(cur.next == null){
                //找到最後一個節點了
                break;
            }else{
                cur =cur.next;
            }
        }
        //插入即可
        cur.next = node;
    }
           

按順序插入（完成後，連結清單有序）

當遇到節點比插入的節點的值大的時候，說明要插入的地方就是遇到的節點的前面！

這裡的代碼不能設定了不能插入已有資料！

//插入資料的時候同時排好序
    public void addByOrder(Node node){
        Node cur = head;
        while(true){
            if(cur.next != null){
                if(cur.next.id > node.id){
                    //說明找到要插入的地方了
                    break;
                }else if(cur.next.id == node.id){
                    //存在了該節點，那麼就提示使用者不能插入
                    System.out.println("已存在該節點不能進行删除");
                    return;
                }else{
                    cur = cur.next;
                }
            }else{
                break;
            }
        }
        //找到了要插入的位置，直接插入
        node.next = cur.next;
        cur.next = node;  //無縫銜接
    }
           

更新節點

//修改單連結清單
    public void update(Node node){
        Node cur = head;
        while(true){
            //找到要被修改的節點
            if(cur.next != null){
                if(cur.next.id == node.id){
                    cur.next.name = node.name;
                    break;
                }
                cur = cur.next;
            }else{
                //找到了末尾都沒找到
                System.out.println("沒有該節點");
                return;
            }
        }
    }
           

删除節點

思路：找到要删除的節點的前置節點，然後讓前置節點越過要删除的節點指向後一個節點。那麼就删除成功了。沒有引用指向的節點會被垃圾回收機制收回。

//删除節點
    public void delete(int id){
        Node cur = head;
        //需要找到要删除的節點的前置節點
        while(true){
            if(cur.next != null){
                if(cur.next.id == id){
                    break;//找到了直接跳出
                }
                cur = cur.next;
            }else{
                //找到末尾也沒有找到
                System.out.println("沒有找到要删除的節點");
                return;
            }
        }
        //走到這裡說明找到了可以更新,跳過要删除的節點直接指向後一個，讓GC回收
        cur.next = cur.next.next;
    }
           

單連結清單反轉

思路：我們新建立一個節點，然後周遊原連結清單，不斷的将周遊到的元素頭插到新連結清單中。最後将新連結清單就是原連結清單的反轉 !

//反轉單連結清單
    public void reverse(Node head){
        Node newHead = new Node();
        Node cur = head.next;   //循環周遊用到
        Node next = null;       //記錄cur的下一個節點，保證改變連結清單引用後連結清單不會斷掉
        while(cur != null){
            next = cur.next;
            cur.next = newHead.next;  //讓目前節點指向newHead的下一個
            newHead.next = cur;
            cur = next;               //周遊下一個節點
        }
        head.next = newHead.next;
    }
           

如發現錯誤請評論一哈，馬上改