Java單鏈表的增刪改查怎么實(shí)現(xiàn)

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

一、單鏈表的增刪改查

1、創(chuàng)建結(jié)點(diǎn)

單鏈表是由結(jié)點(diǎn)連接而成，所以我們首先要?jiǎng)?chuàng)建結(jié)點(diǎn)類，用于對(duì)結(jié)點(diǎn)進(jìn)行操作。定義data屬性 表示序號(hào)，定義name屬性表示結(jié)點(diǎn)存放的數(shù)據(jù)信息，定義next屬性表示指向下一個(gè)結(jié)點(diǎn)。構(gòu)造器只需要放入data屬性和name屬性，重寫toString方法方便打印結(jié)點(diǎn)信息。

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、單鏈表的添加操作

首先創(chuàng)建頭結(jié)點(diǎn)

此結(jié)點(diǎn)表示鏈表的頭，不存放實(shí)際數(shù)據(jù)的。

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

添加操作

將新的結(jié)點(diǎn)添加到鏈表的尾部，我們首先要遍歷鏈表，找到鏈表的尾部，然后將最后一個(gè)結(jié)點(diǎn)的next指向新的結(jié)點(diǎn)，新結(jié)點(diǎn)的next指向NULL，這樣就完成了鏈表的添加操作，這種每次添加到鏈表的尾部的操作稱為尾插法。注意，當(dāng)我們遍歷鏈表時(shí)，需要一個(gè)輔助結(jié)點(diǎn)temp來進(jìn)行遍歷，因?yàn)閔ead頭結(jié)點(diǎn)不能動(dòng)。

public class SingleLinkedList {
    //首先創(chuàng)建頭結(jié)點(diǎn)，此結(jié)點(diǎn)表示鏈表的頭，無具體數(shù)據(jù)
    private Node head = new Node(0,"");
    //添加結(jié)點(diǎn)操作
    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、單鏈表的刪除操作

假設(shè)我們要?jiǎng)h除中間這個(gè)結(jié)點(diǎn)，我們只需要將這個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的next指向這個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)（也就是將第一個(gè)結(jié)點(diǎn)的next指向第三個(gè)結(jié)點(diǎn)）。

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

4、單鏈表的有效結(jié)點(diǎn)的個(gè)數(shù)

我們可以定義一個(gè)計(jì)數(shù)的變量count，初始化為0，然后循環(huán)遍歷鏈表，每遍歷到一個(gè)結(jié)點(diǎn)，count就加一，這樣就能求出單鏈表的有效個(gè)數(shù)。

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

二、大廠面試題

1、新浪微博：查找單鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

從上圖可以看出，假設(shè)要找倒數(shù)第2個(gè)結(jié)點(diǎn)，我們?cè)撛趺醋?？不難看出，倒數(shù)第二個(gè)結(jié)點(diǎn)也是順序的第三個(gè)結(jié)點(diǎn)，也就是將倒數(shù)的結(jié)點(diǎn)轉(zhuǎn)換成順序結(jié)點(diǎn)，遍歷鏈表找到順序結(jié)點(diǎn)即可。因?yàn)槭怯忻鞔_表示是第幾個(gè)結(jié)點(diǎn)，所以我們需要知道結(jié)點(diǎn)的有效個(gè)數(shù)，前面我們介紹了有效個(gè)數(shù)的求法，直接用即可。當(dāng)我們要找倒數(shù)第k個(gè)結(jié)點(diǎn)，我們可以轉(zhuǎn)換成順序的第（count - k + 1）個(gè)結(jié)點(diǎn)。比如：k = 2，count = 4， 倒數(shù)第2個(gè)結(jié)點(diǎn)也就是順序第（4 - 2 + 1 = 3）個(gè)結(jié)點(diǎn)。

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

2、騰訊面試題：單鏈表的反轉(zhuǎn)

首先創(chuàng)建輔助變量temp用于循環(huán)原來的鏈表，輔助變量temp1記錄temp的下一個(gè)位置，每遍歷到一個(gè)結(jié)點(diǎn)就插入到新鏈表的頭部，這種方式稱為頭插法。

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

以上就是關(guān)于“Java單鏈表的增刪改查怎么實(shí)現(xiàn)”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。