筆者在上篇博客書(shū)寫(xiě)了一個(gè)名為：鏈?zhǔn)酱鎯?chǔ)之：鏈表的引出及其簡(jiǎn)介原文鏈接為：https://blog.csdn.net/weixin_64308540/article/details/128374876?spm=1001.2014.3001.5501

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊(cè)、網(wǎng)站空間、營(yíng)銷(xiāo)軟件、網(wǎng)站建設(shè)、寒亭網(wǎng)站維護(hù)、網(wǎng)站推廣。

對(duì)于此篇博客，在一寫(xiě)出來(lái)，便引起了巨大反響！！那么后續(xù)來(lái)了！！今日，筆者來(lái)帶領(lǐng)大家走進(jìn)：無(wú)頭單向非循環(huán)鏈表的實(shí)現(xiàn)（面試筆試經(jīng)常用到）

我們來(lái)看一下實(shí)現(xiàn)的主要代碼：

總體的方法：

//頭插法
    public void addFirst(int data) {
        
    }
    
    //尾插法
    public void addLast(int data){
        
    }
    
    //任意位置插入，（第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0下標(biāo)）
    public void addIndex(int index ,int data) {
        
    }
    
    //查找是否包含關(guān)鍵字key在鏈表當(dāng)中
    public boolean contains(int key) {
        return false;
    }
    
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
    public void remove(int key){
        
    }
    
    //刪除所有值為key的節(jié)點(diǎn)
    public void removeAllkey(int key){
        
    }
    
    //得到單鏈表的長(zhǎng)度
    public int size(){
        return -1;
    }
    
    //清空
    public void clear(){
        
    }
    
    //打印
    public void display(){
        
    }

對(duì)于上述的各種方法，可能就會(huì)有不少的老鐵感到犯渾了，一臉懵逼，那么接下來(lái)我們就主要來(lái)實(shí)現(xiàn)他們一下！！

準(zhǔn)備性的工作：

public class MySingleList {
    static class ListNode{ //靜態(tài)內(nèi)部類(lèi)

        public int val; //存儲(chǔ)數(shù)據(jù)
        public ListNode next; //存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址

        //構(gòu)建方法！沒(méi)有next，
        // 主要還是在于剛new對(duì)象的時(shí)候，不知道下一個(gè)節(jié)點(diǎn)的地址！！
        public ListNode(int val) {
            this.val = val;
        }

        public ListNode head; //代表當(dāng)前鏈表的頭節(jié)點(diǎn)的引用
        //不帶頭的非循環(huán)的單鏈表，大的問(wèn)題就是怎么知道頭節(jié)點(diǎn)在哪兒？？

        //手動(dòng)創(chuàng)建節(jié)點(diǎn)
        public void creatLink(){
            ListNode listNode1 = new ListNode(12);
            ListNode listNode2 = new ListNode(23);
            ListNode listNode3 = new ListNode(34);
            ListNode listNode4 = new ListNode(45);
            listNode1.next=listNode2;
            listNode2.next=listNode3;
            listNode3.next=listNode4;
            //listNode4所對(duì)應(yīng)的next默認(rèn)為空null

            //確定頭節(jié)點(diǎn)
            head=listNode1;
        }
    }
}

對(duì)于上述的代碼，我們來(lái)進(jìn)行小小的解析一下吧?。?/p>

首先，我們創(chuàng)建了一個(gè)內(nèi)部類(lèi)，而且還是一個(gè)靜態(tài)內(nèi)部類(lèi)喲！！原因在于：我們寫(xiě)成內(nèi)部類(lèi)是把節(jié)點(diǎn)看成鏈表的一部分，當(dāng)然，我們單獨(dú)寫(xiě)成一個(gè)類(lèi)也可以??！在我們這個(gè)寫(xiě)的情況下：脫離了鏈表，內(nèi)部類(lèi)ListNode沒(méi)有任何意義，因?yàn)殒湵硎怯梢粋€(gè)一個(gè)的節(jié)點(diǎn)組成的??！其次，我們使用了static（靜態(tài)），主要是想將ListNode這個(gè)內(nèi)部類(lèi)，不需要依靠MySingleList這個(gè)外部類(lèi)都可以單獨(dú)實(shí)現(xiàn)！！

經(jīng)過(guò)上述代碼的實(shí)現(xiàn)，我們可以進(jìn)行后續(xù)的真正壓軸的環(huán)節(jié)了?。?/p>進(jìn)入正題 遍歷鏈表

對(duì)于遍歷鏈表，雖然很簡(jiǎn)單，但是，經(jīng)過(guò)思考，有著一下幾個(gè)小小的疑問(wèn)：

1. head怎么往后走？？head=head.next;??當(dāng)我們打印完以后，head將會(huì)指向最后一個(gè)節(jié)點(diǎn)！這不是我們想要的！！

2. 循環(huán)結(jié)束的條件是什么？？（1）head?!=?null?????(2)還是head.next?!=null???

//遍歷數(shù)組
        public void display(){
            //重新定義一個(gè)頭節(jié)點(diǎn),使其等于head節(jié)點(diǎn)！
            ListNode cur = head;
            while (cur != null){
                System.out.print(cur.val+" ");
                cur=cur.next;
            }
            //換行
            System.out.println();
        }

對(duì)于：head != null ?? 我們可以看出來(lái)：打印全部的鏈表！head.next !=null 則是：鏈表的最后一個(gè)不能打印???！

因此，我們有著一下的總結(jié)：

1. 如果說(shuō)，把整個(gè)鏈表遍歷完成，就需要head==null;

2. 如果說(shuō)，遍歷到鏈表的尾巴（最后一個(gè)），則head.next?==?null;

3. 對(duì)于ListNode cur = head;這個(gè)部分，我們可以理解為：滴滴代跑??！確定頭節(jié)點(diǎn)不會(huì)隨著鏈表的遍歷而發(fā)生改變?。?/p>

從指定位置開(kāi)始遍歷數(shù)組

經(jīng)過(guò)上述的遍歷數(shù)組的過(guò)程，我們是不是可以想一下：從指定位置開(kāi)始遍歷數(shù)組呀？？那么請(qǐng)看筆者的代碼吧?。∑鋵?shí)大致上的代碼還是一樣的?。?/p>

//從指定位置開(kāi)始遍歷數(shù)組
        public void  display(ListNode newHead){
            ListNode cur = newHead;
            while (cur != null){
                System.out.print(cur.val+" ");
                cur=cur.next;
            }
            //換行
            System.out.println();
        }

僅僅經(jīng)過(guò)代碼的改寫(xiě)一下就可以了！沒(méi)有技術(shù)含量，筆者在此就不再進(jìn)行講解啦哈！！

查找鏈表當(dāng)中是否包含關(guān)鍵字key??

在這個(gè)過(guò)程中，我們?nèi)匀恍枰闅v一遍鏈表才可以，若是key在鏈表當(dāng)中，當(dāng)遍歷到哪兒的時(shí)候直接return??true?就可以了，若是沒(méi)有，則返回false!

下面就進(jìn)行一下代碼的書(shū)寫(xiě)吧！

 //查找鏈表當(dāng)中是否包含關(guān)鍵字key
        public boolean contains(int key){
            ListNode cur = head;
            while (cur != null){
                if (cur.val == key){
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }

那么，我們來(lái)進(jìn)行簡(jiǎn)單的講解一下吧！

1. 當(dāng)cur?==?null的時(shí)候，所有的節(jié)點(diǎn)都已經(jīng)判斷完了

2. 當(dāng)代碼的循環(huán)條件寫(xiě)為cur.next?==?null的時(shí)候，則鏈表的最后一個(gè)節(jié)點(diǎn)不能進(jìn)行比較！！

3. 在循環(huán)中，if語(yǔ)句中，cur.val?==?key，用了“==“來(lái)進(jìn)行比較，主要還是在剛定義的時(shí)候，val，key都為int類(lèi)型??！否則，就使用equals來(lái)進(jìn)行比較了（返回值類(lèi)型為boolean）

上述的代碼講解完畢了，我們開(kāi)始進(jìn)行下面的：

得到單鏈表的長(zhǎng)度

不管怎么樣進(jìn)行得到單鏈表的長(zhǎng)度，我們都必須進(jìn)行遍歷一遍鏈表！所以時(shí)間復(fù)雜度為O(N)?

在遍歷鏈表的時(shí)候，我們可以用一個(gè)計(jì)算器count來(lái)進(jìn)行統(tǒng)計(jì)鏈表的長(zhǎng)度??！

請(qǐng)看代碼：

   //得到單鏈表的長(zhǎng)度
        public int size(){
            int count=0;
            ListNode cur =head;
            while (cur != null){
                count++;
                cur=cur.next;
            }
            return count;
        }

對(duì)于該段代碼沒(méi)有什么好解釋的哈！

頭插法

對(duì)于頭插法，顧名思義就是：給你一個(gè)新的節(jié)點(diǎn)，你將這個(gè)節(jié)點(diǎn)插入在該鏈表的頭部??！那么，我們需要想一想;更改些什么數(shù)據(jù)才能插入想要的數(shù)據(jù)呢？？

因此：有著下面的簡(jiǎn)單代碼：

//頭插法  時(shí)間復(fù)雜度為O(1)
        public void addFirst (int data){
            ListNode listNode = new ListNode(data);
            listNode.next = head;
            head=listNode;
        }

那么，對(duì)于上述的頭插法的簡(jiǎn)單代碼，筆者便來(lái)簡(jiǎn)單解釋一下吧！！

1. 得有一個(gè)想要節(jié)點(diǎn)！！不用管里面存儲(chǔ)的數(shù)據(jù)是多少??！

因此，我們通過(guò)代碼：來(lái)創(chuàng)建了一個(gè)節(jié)點(diǎn)：新創(chuàng)建的節(jié)點(diǎn)next的值為null?原因在于：只是實(shí)列化了一個(gè)節(jié)點(diǎn)，我們并不知道下一個(gè)節(jié)點(diǎn)是誰(shuí)??！

ListNode listNode = new ListNode(data);

因此，我們只需要將上述的節(jié)點(diǎn)，與原來(lái)的鏈表的頭節(jié)點(diǎn)進(jìn)行簡(jiǎn)單的更改數(shù)據(jù)即可?。?/p>

在上述的分析過(guò)程中，既然有了想法，那么我們便可以通過(guò)……

listNode.next = head;
            head=listNode;

將鏈表進(jìn)行頭節(jié)點(diǎn)的插入！

在這個(gè)過(guò)程中，我們需要注意的是：在鏈表里面的插入，一定要先綁后面??！

尾插法

在上個(gè)案列中，我們講述了頭插法，但是對(duì)于尾插法！不知道屏幕前的各位老鐵有何指教呢？？

其實(shí)對(duì)于尾插法！也是很簡(jiǎn)單！主要還是在于：找到該鏈表的尾巴??！但是，需要判斷原來(lái)鏈表是否為null，就連鏈表的空間都不用判斷??！相對(duì)于順序表，顯得簡(jiǎn)單多了！！

因此，我們有著下列的簡(jiǎn)單代碼：

//尾插法  時(shí)間復(fù)雜度為O(N) 找到鏈表的尾巴！
        //把一個(gè)節(jié)點(diǎn)插入到一個(gè)鏈表的最后
        public void addLast(int data){
            ListNode listNode = new ListNode(data);
            if (head == null){
                head = listNode;
                return;
            }
            ListNode cur = head;
            while (cur.next != null){
                cur=cur.next;
            }
            cur.next = listNode;//插入時(shí)候所需的代碼！
        }

在上述代碼中;如果鏈表中一個(gè)節(jié)點(diǎn)都沒(méi)有？？此時(shí)if(head?==?null)成立?，我們就不用進(jìn)行插入了?。‘吘箾](méi)啥用了也??！直接將要插入的節(jié)點(diǎn)當(dāng)作頭節(jié)點(diǎn)進(jìn)行返回就行了??！但是，這兒的return?是一定要寫(xiě)的??！如果不寫(xiě)，就會(huì)繼續(xù)往下走??！寫(xiě)上return是指：直接結(jié)束??！

定義一個(gè)新的節(jié)點(diǎn)cur?！相當(dāng)于滴滴代跑！使得頭節(jié)點(diǎn)保存不變！在while循環(huán)中，進(jìn)行找鏈表的尾巴節(jié)點(diǎn)??！當(dāng)找到后，進(jìn)行插入所需要的代碼就先了??！

總結(jié)一下：鏈表的插入！僅僅是修改了部分?jǐn)?shù)據(jù)的指向??！

任意位置插入？

前提：第一個(gè)數(shù)據(jù)節(jié)點(diǎn)當(dāng)作0號(hào)下標(biāo)（數(shù)組的下標(biāo)）

我們?cè)谏鲜龅膬蓚€(gè)案列當(dāng)中，講述了：頭插法，尾插法，那么，現(xiàn)在讓我們來(lái)深入進(jìn)行一下：在任意位置進(jìn)行插入節(jié)點(diǎn)！

對(duì)于該案列，我們要有著一下簡(jiǎn)單的思考：

1. 是否需要檢查想要插入的位置是否合法？？（范圍）

//檢查想要插入的位置是否合法？？
        private void checkIndex(int index)throws  ListIndexOutOfExpection{
            if ( index< 0 || index >size()){
                throw new ListIndexOutOfExpection("index位置不合法");
            }
        }

2. 頭插法？？（當(dāng)想要插入的位置為0時(shí)）

//頭插法？？
            if (index == 0){
                addFirst(data);
                return;
            }

3. 尾插法？？（當(dāng)想要插入的位置等于原鏈表的長(zhǎng)度的時(shí)候）

//尾插法？？
            if (index == size()){
                addLast(data);
                return;
            }

4. 我們是要找到想要插入的位置的節(jié)點(diǎn)？？還是要找到想要插入位置的前一個(gè)節(jié)點(diǎn)呢？？

//找到index-1位置的節(jié)點(diǎn)的地址
        private ListNode findIndexSubOne(int index){
            ListNode cur =head;
            int count =0;
            while (count != index-1){
                cur = cur.next;
                count++;
            }
            return cur;
        }

對(duì)于該案列，筆者僅僅有著上述的4點(diǎn)猜想，當(dāng)然，有這4種猜想也夠了?。?/p>

對(duì)于實(shí)現(xiàn)該案列的總體代碼為：

//在任意位置插入（第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)）
        public void addIndex(int index , int data )
                throws  ListIndexOutOfExpection{
            //檢查想要插入的位置是否合法？？
            checkIndex(index);
            //頭插法？？
            if (index == 0){
                addFirst(data);
                return;
            }
            //尾插法？？
            if (index == size()){
                addLast(data);
                return;
            }
            //找到想要插入位置的前一個(gè)節(jié)點(diǎn)！
            ListNode cur = findIndexSubOne(index);

            ListNode listNode = new ListNode(data);
????????????//先捆綁后面
            listNode.next=cur.next;
            cur.next=listNode;
        }

        //檢查想要插入的位置是否合法？？
        private void checkIndex(int index)throws  ListIndexOutOfExpection{
            if ( index< 0 || index >size()){
                throw new ListIndexOutOfExpection("index位置不合法");
            }
        }

        //找到index-1位置的節(jié)點(diǎn)的地址
        private ListNode findIndexSubOne(int index){
???????????//走index-1步，然后返回所對(duì)應(yīng)的節(jié)點(diǎn)的地址
            ListNode cur =head;
            int count =0;
            while (count != index-1){
                cur = cur.next;
                count++;
            }
            return cur;
        }

當(dāng)然，筆者還創(chuàng)建了一個(gè)名為：ListIndexOutOfExpection.java?的類(lèi)?。≈饕怯脕?lái)拋出警告??！

public class ListIndexOutOfExpection extends RuntimeException{
    public ListIndexOutOfExpection() {
    }
    public ListIndexOutOfExpection(String message) {
        super(message);
    }
}

對(duì)于上述代碼的總體思路為：

刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)？

對(duì)于這個(gè)案列，我們有著一下的想法：

1. 原鏈表當(dāng)作是否一個(gè)節(jié)點(diǎn)都沒(méi)有？？即head==null是否成立？

2. 判斷頭節(jié)點(diǎn)是否為對(duì)應(yīng)的key??

3. 找到關(guān)鍵字key的前一個(gè)節(jié)點(diǎn)??！

下面請(qǐng)看筆者的代碼吧！

//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn) 時(shí)間復(fù)雜度為O(N)
        public void remove(int key){
            if (head == null){
                return;
                //此時(shí)，一個(gè)節(jié)點(diǎn)都沒(méi)有！
            }
?????       //判斷頭節(jié)點(diǎn)是否為對(duì)應(yīng)的key
            if (head.val == key){
                head =head.next;
                return;
            }
?????????//searchPrev找到關(guān)鍵字key的前一個(gè)節(jié)點(diǎn)
            ListNode cur = searchPrev(key);
          if (cur == null){
              return;
          }
          //dele為要?jiǎng)h除的節(jié)點(diǎn)
          ListNode dele = cur.next;
          cur.next=dele.next;
        }
        
        //找到關(guān)鍵字key的前一個(gè)節(jié)點(diǎn)!
        private ListNode searchPrev(int key){
            ListNode cur =head;???//這樣操作的前提為head不為null?

            while (cur.next != null){
                if (cur.next.val == key){
                    return cur;??//此時(shí)cur時(shí)key的前一個(gè)節(jié)點(diǎn)
                }
                cur =cur.next;
            }
            return null;
            //此時(shí)，沒(méi)有要?jiǎng)h除的節(jié)點(diǎn)！
        }

對(duì)應(yīng)該案列代碼的總體過(guò)程為：

刪除所有值為key的節(jié)點(diǎn)？？

要求：遍歷一遍就能全部都刪除掉?。?/p>

經(jīng)過(guò)上述幾個(gè)案列的分析，能夠堅(jiān)持閱讀下去的你！是否已經(jīng)收獲滿滿呢？？自信滿滿呢？？那么，這次便來(lái)個(gè)壓軸的吧！！

下面請(qǐng)看筆者的代碼：

  //刪除所有值為key的節(jié)點(diǎn)
        //要求：遍歷一遍就都刪除了！
        public void removeAllKey(int key){
            if (head == null ){
                return;
            }
            ListNode prev =head;
            ListNode cur =head.next;
            
            while (cur != null){
                if (cur.val == key){
                    prev.next=cur.next;
                    cur=cur.next;
                }else {
                    prev=cur;
                    cur=cur.next;
                }
            }
            if (head.val ==key){
                head=head.next;
            }
        }

對(duì)于該段代碼，由于文本+筆者發(fā)熱頭疼的原因，打算偷懶會(huì)??！噓噓，千萬(wàn)不要往外說(shuō)！

對(duì)于該段代碼看不懂的讀者，請(qǐng)私聊筆者喲?。‘?dāng)作個(gè)懸念吧?。?/p>回收鏈表

要求：保證所有的節(jié)點(diǎn)都被回收??！

其實(shí)一開(kāi)始，感覺(jué)還是是挺蠻煩的！但是細(xì)細(xì)想來(lái)！每個(gè)節(jié)點(diǎn)都是由一個(gè)存儲(chǔ)當(dāng)前的數(shù)據(jù)，及其下一個(gè)節(jié)點(diǎn)的地址組成的！！如果將第一個(gè)節(jié)點(diǎn)給置為null，那么不就找不到第二個(gè)節(jié)點(diǎn)在哪兒了嗎？？同樣也就被回收了??！

經(jīng)過(guò)上述的分析，因此，有著下列的代碼：

//鏈表回收
        public void clear(){
            head=null;
        }

當(dāng)頭節(jié)點(diǎn)被回收了（置為null)，后續(xù)的階段的就沒(méi)有引用的了，從而也會(huì)都被回收的??！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：鏈表的實(shí)現(xiàn)：無(wú)頭單向非循環(huán)鏈表的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://weahome.cn/article/ddiijh.html