Java單鏈表的增刪改查怎么實現

這篇“Java單鏈表的增刪改查怎么實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java單鏈表的增刪改查怎么實現”文章吧。

一、單鏈表的增刪改查

1、創建結點

單鏈表是由結點連接而成，所以我們首先要創建結點類，用于對結點進行操作。定義data屬性 表示序號，定義name屬性表示結點存放的數據信息，定義next屬性表示指向下一個結點。構造器只需要放入data屬性和name屬性，重寫toString方法方便打印結點信息。

public class Node {
    public int data;
    public String name;
    public Node next;
    public Node(int data, String name){
        this.data = data;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", name='" + name + '\'' +
                '}';
    }
}

2、單鏈表的添加操作

首先創建頭結點

此結點表示鏈表的頭，不存放實際數據的。

private Node head = new Node(0,"");

添加操作

將新的結點添加到鏈表的尾部，我們首先要遍歷鏈表，找到鏈表的尾部，然后將最后一個結點的next指向新的結點，新結點的next指向NULL，這樣就完成了鏈表的添加操作，這種每次添加到鏈表的尾部的操作稱為尾插法。注意，當我們遍歷鏈表時，需要一個輔助結點temp來進行遍歷，因為head頭結點不能動。

public class SingleLinkedList {
    //首先創建頭結點，此結點表示鏈表的頭，無具體數據
    private Node head = new Node(0,"");
    //添加結點操作
    public void addData(Node node){
        Node temp = head;
        while (true){
            if (temp.next == null){
                temp.next = node;
                node.next = null;
                break;
            }
            temp = temp.next;
        }
    }
}

3、單鏈表的刪除操作

假設我們要刪除中間這個結點，我們只需要將這個結點的上一個結點的next指向這個結點的下一個結點（也就是將第一個結點的next指向第三個結點）。

     public void delData(Node node){
        Node temp = head;
        while (true){
            //如果是要刪除的結點
            if (temp.next.data == node.data){
                temp.next = temp.next.next;
                break;
            }else if(temp.next == null){
                System.out.println("未找到結點！");
                break;
            }
            temp = temp.next;
        }
    }

4、單鏈表的有效結點的個數

我們可以定義一個計數的變量count，初始化為0，然后循環遍歷鏈表，每遍歷到一個結點，count就加一，這樣就能求出單鏈表的有效個數。

    public int countData(){
        Node temp = head.next;
        int count = 0;
        while (true){
            if (temp == null){
                break;
            }
            count++;
            temp = temp.next;
        }
        return count;
    }

二、大廠面試題

1、新浪微博：查找單鏈表中倒數第k個結點

從上圖可以看出，假設要找倒數第2個結點，我們該怎么做？不難看出，倒數第二個結點也是順序的第三個結點，也就是將倒數的結點轉換成順序結點，遍歷鏈表找到順序結點即可。因為是有明確表示是第幾個結點，所以我們需要知道結點的有效個數，前面我們介紹了有效個數的求法，直接用即可。當我們要找倒數第k個結點，我們可以轉換成順序的第（count - k + 1）個結點。比如：k = 2，count = 4， 倒數第2個結點也就是順序第（4 - 2 + 1 = 3）個結點。

    public Node referNode(int n){
        //根據前面計算有效個數的方法，求得鏈表總結點個數
        int max = countData();
        //計數
        int count = 1;
        //判斷指定的結點是否在范圍內
        if (!(n >= 1 && n <= max)){
            throw new RuntimeException("沒有此結點!");
        }
        //輔助結點
        Node temp = head.next;
        //循環遍歷查找
        while (true){
            //滿足條件，則是我們要找的結點
            if (count == (max - n + 1)){
                return temp;
            }else {
                temp = temp.next;
                count++;
            }
        }
    }

2、騰訊面試題：單鏈表的反轉

首先創建輔助變量temp用于循環原來的鏈表，輔助變量temp1記錄temp的下一個位置，每遍歷到一個結點就插入到新鏈表的頭部，這種方式稱為頭插法。

public void nodeReversal(Node head){
        //如果鏈表為空或鏈表只有一個結點，則不需要反轉
        if (head.next == null || head.next.next == null){
            return;
        }
        //輔助變量temp
        Node temp = head.next;
        //輔助變量temp1
        Node temp1 = null;
        //循環遍歷
        while (true){
            //退出循環的條件
            if (temp == null){
                break;
            }
            //首先將temp的下一個結點給temp1
            temp1 = temp.next;
            //然后將temp的next指向新鏈表頭headReversal的next（頭指向的下一個）
            temp.next = headReversal.next;
            //再然后將新鏈表頭headReversal的next指向temp結點
            headReversal.next = temp;
            //最后將temp1記錄的結點賦值給temp
            temp = temp1;
        }
        //遍歷結束，將新的順序替換原來的順序
        head.next = headReversal.next;
        //顯示鏈表，這個方法需要自己寫
        showList(head);
}

以上就是關于“Java單鏈表的增刪改查怎么實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。