一.鏈表

1.什么是鏈表

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的，
鏈表的結構有多種多樣，我們學習的主要有兩個，單向不帶頭非回圈與雙向不帶頭非回圈，還有例外幾種沒有這兩種常用，所以我們暫時不學哈哈，

2.鏈表的用途

? 在你使用順序表時，是不是每次插入和洗掉元素，必須得移動元素，然后順序表擴容也是一個問題，順序表滿了我們都是乘2來擴容，順序表容量少還好，如果我們的容量達到了一個很大值，是不是會浪費很多空間，鏈表就解決了這些問題，鏈表在物理上并不是一定連續的，但在邏輯上是連續的，我們可以做到不移動元素進行插入和洗掉，在記憶體層面上可以做到隨用隨取，增加元素就加一個空間，只要使它的邏輯上連續就行了，

二.用代碼實作一個鏈表

學習鏈表前一定要知道的幾個概念

前驅，后繼，頭結點，尾結點，前驅和后繼明白了對學習鏈表真的很重，筆者在這方面吃過虧(哭了)，

除了頭結點其它每個結點多有一個前驅，

除了尾結點其它每個結點多有一個后繼，[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳在這里插入圖片描述

這張表里面的listNode2是listNosd3的前驅listNode4是listNode3的后繼，

我們用listNode2.val就能拿到listNode2里面的值，

用listNode2.next就能拿到下一個結點的地址

1.生成一個鏈表

第一步需要創建一個結點類這樣我們就能像超市批發一樣成批生成結點，

class ListNode{
    public int val;//結點值
    public ListNode next;//結點
    public ListNode(int val){
        this.val=val;
    }
}

生成一個頭結點用來執行接下來的一系列操作
```
 ListNode head;//鏈表頭
```

接下來就到我們生成第一個鏈表的時候了（窮舉法）

public void createList(){
        ListNode listNode1=new ListNode(21);//創建第一個結點
        ListNode listNode2=new ListNode(65);//創建第二個結點
        ListNode listNode3=new ListNode(48);//創建第三個結點
        ListNode listNode4=new ListNode(13);//創建第四個結點
        ListNode listNode5=new ListNode(98);//創建第五個結點
        //把所有的結點鏈接起來
        this.head=listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
    }

下面這張圖就是我們的鏈表[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳在這里插入圖片描述

2.列印鏈表

接下來可以寫個列印函式來列印我們的鏈表了

第一種從頭開始列印
```
public void display(){
        ListNode cur=this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
//運行結果：21 65 48 13 98 
```
程式開始我們把鏈表頭賦給了cur，如果不生成cur這個變數的話，我們的鏈表就變成一次性的了，這一個點要注意下，cur.val用來拿鏈表里的值，cur.next指向的是下個鏈表，這個可以結合上面圖理解一下，好了到了這里我們生成了一個鏈表并列印出來了，

第二種方法從指定的地方開始列印

 public void display2(ListNode newHead){
        ListNode cur=newHead;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

3.鏈表大小

要想得到鏈表的大小，第一步你是怎么想的，是不是通過遍歷鏈表來實作呀，對！目前就是用遍歷來實作的
```
 //得到單鏈表的長度
 public int size(){
     ListNode cur = this.head;
     int count=0;
     while (cur!=null){
     cur=cur.next;
     count++;
     }
 	return count;
 }
```
小技巧：每次我我們要遍歷鏈表的時候多要把鏈表頭，賦給一個臨時遍歷，這樣可以避免鏈表稱為一次性的，愛護環境人人有責，回圈利用才是最好的，開個玩笑哈哈，

4.查找包含的元素

只需要遍歷鏈表的值來和要查找的元素比較就行了

具體代碼實作

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

5.頭插法

頭插法就如它的名字一樣從頭部開始插入[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳
圖中，實作頭插法是要記得要先系結后面結點，在系結前面的結點，圖中藍色的框里的賦值就是沒有先系結后面的形成了一個自己指向自己的倍訓結點，

頭插頭法的具體實作

//頭插法
public void addFirst(int data){
    ListNode node=new ListNode(data);
    node.next=this.head;
    this.head=node;
}

第一步生成了一個新的結點，第二步把一開是的鏈表頭head給node.next,第三步把node給head，

6.尾插法

前面我么學尾插法時是從頭部插的，這個尾插法肯定就是從未尾部開始插的哈哈下面先看下畫的思維圖[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

代碼的具體實作

//尾插法
    public void addLast(int data){
        ListNode node =new ListNode(data);
        ListNode cur=this.head;
        if(this.head==null){
            this.head=node;
        }else {
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }

這里我們要注意的時回圈條件變了，不是cur了而是cur.next看圖我們可以發現cur！=null會走到listNode5后面才能結束回圈(listNode6先不看這是我們插入的)cur.next走到最后一個就會停，

7.任意位置插入

在任意地方插入的時候要考慮三個方面，如在頭結點插入，在尾結點插入，還有在中間插入，這里里面最難的就是在中間插入，插入頭和尾可以分別呼叫頭插入函式和尾插入函式就行，但在中間插入我們需要找到要插入位置的前驅或后繼才能插入[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

代碼具體實作

找到index-1位置的節點的地址

public ListNode findIndex(int index){
    ListNode cur=this.head;
    while (index-1!=0){
        cur=cur.next;
        index--;
    }
    return cur;
}

任意位置插入

//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index,int data){
    if(index<0||index>size()){
        System.out.println("index不合法！");
        return;
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==size()){
        addLast(data);
        return;
    }
    ListNode cur=findIndex(index);
    ListNode node=new ListNode(data);
    node.next=cur.next;
    cur.next=node;
}

8.洗掉第一次出現關鍵字為key的節點

要實作這函式要搞清楚head.val 和head.next.val的區別[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

代碼具體實作

找到要洗掉的關鍵字的前驅

public ListNode searchPerv(int key){
    ListNode cur=this.head;
    while (cur.next!=null){
        if(cur.next.val==key){
            return cur;
        }
        cur=cur.next;
    }
    return null;
}

洗掉第一次出現關鍵字為key的節點

public void remove(int key){
    if (this.head==null){
        System.out.println("鏈表為空");
        return;
    }
    if(this.head.val==key){
        this.head=this.head.next;
        return;
    }
    ListNode cur = searchPerv(key);
    if(cur==null){
        System.out.println("沒有洗掉的結點");
        return;
    }
    ListNode del=cur.next;
    cur.next=del.next;
}

我們利用cur.next.val可以找到我們要刪的結點，任何把他的前驅發回來，在進行操作，cur就是前驅，

9.洗掉所有值為key的節點

定義了兩個變數，可以理解成一個大哥(cur)和一位小弟(perv)，大哥在前面沖鋒陷陣，小弟跟在大哥后,大哥確認安全了才會叫小弟來
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

?

具體代碼實作

public ListNode removeAllKey(int key){
    if(this.head==null){
        System.out.println("沒有要洗掉的結點");
        return null;
    }
    ListNode perv=this.head;//鏈表頭
    ListNode cur=this.head.next;//第二個結點
    while (cur!=null){
        if(cur.val==key){
            perv.next=cur.next;
            cur=cur.next;
        }else {
            perv=cur;
            cur=cur.next;
        }
    }
    if (this.head.val==key){
        this.head=this.head.next;
    }
    return this.head;
}

10.洗掉整條鏈表

洗掉整條鏈表有兩種方法實作[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳在這里插入圖片描述

暴力法

public void clear(){
        this.head=null;
    }

相對溫柔

public void clear(){
    while (this.head!=null){
        ListNode curNext = head.next;
        this.head.next=null;
        this.head=curNext;
    }
}

三.單鏈表完整代碼

0.代碼模板

//頭插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一個資料節點為0號下標
public boolean addIndex(int index,int data);
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key);
//洗掉第一次出現關鍵字為key的節點
public void remove(int key);
//洗掉所有值為key的節點
public void removeAllKey(int key);
//得到單鏈表的長度
public int size();
public void display();
public void clear();

1.text

package com.wei.two;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:WLW
 * Data:2021-11-08
 * Time:23:48
 */
public class TextDome {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
       // myLinkedList.createList();
//        myLinkedList.addFirst(21);
//        myLinkedList.addFirst(65);
//        myLinkedList.addFirst(48);
//        myLinkedList.addFirst(13);
//        myLinkedList.addFirst(98);
        myLinkedList.addLast(21);
        myLinkedList.addLast(65);
        myLinkedList.addLast(48);
        myLinkedList.addLast(21);
        myLinkedList.addLast(21);
       myLinkedList.display();
       //myLinkedList.addIndex(2,33);
       //myLinkedList.addIndex(1,33);
//       myLinkedList.addIndex(5,33);
//       myLinkedList.display();
//        System.out.println(myLinkedList.size());
       // System.out.println(myLinkedList.contains(100));
        //myLinkedList.display2();
        myLinkedList.remove(21);
        myLinkedList.removeAllKey(21);
       // myLinkedList.clear();
        myLinkedList.display();
    }
}

2.MyLinkedList

package com.wei.two;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:WLW
 * Data:2021-11-08
 * Time:23:49
 */
//創建一個結點
class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}

public class MyLinkedList {
    ListNode head;//鏈表頭
    //創建一個鏈表
    public void createList(){
        ListNode listNode1=new ListNode(21);//創建第一個結點
        ListNode listNode2=new ListNode(65);//創建第二個結點
        ListNode listNode3=new ListNode(48);//創建第三個結點
        ListNode listNode4=new ListNode(13);//創建第四個結點
        ListNode listNode5=new ListNode(98);//創建第五個結點
        //把所有的結點鏈接起來
        this.head=listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
    }
    public void display(){
        ListNode cur=this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }


    public void display2(ListNode newHead){

        ListNode cur=newHead;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //得到單鏈表的長度
    public int size(){
        ListNode cur = this.head;
        int count=0;
        while (cur!=null){
            cur=cur.next;
            count++;
        }
        return count;
    }
    //頭插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        node.next=this.head;
        this.head=node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node =new ListNode(data);
        ListNode cur=this.head;
        if(this.head==null){
            this.head=node;
        }else {
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }
    public ListNode findIndex(int index){
        ListNode cur=this.head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入,第一個資料節點為0號下標
    public void addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("index不合法！");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode cur=findIndex(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }
    //查找是否包含關鍵字key是否在單鏈表當中
    public boolean contains(int key){
        ListNode cur = this.head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    public ListNode searchPerv(int key){
        ListNode cur=this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    //洗掉第一次出現關鍵字為key的節點
    public void remove(int key){
        if (this.head==null){
            System.out.println("鏈表為空");
            return;
        }
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        ListNode cur = searchPerv(key);
        if(cur==null){
            System.out.println("沒有洗掉的結點");
            return;
        }
        ListNode del=cur.next;
        cur.next=del.next;
    }
    //洗掉所有值為key的節點
    public ListNode removeAllKey(int key){
        if(this.head == null) return null;
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后處理頭
        if(this.head.val == key) {
            this.head = this.head.next;
        }
        return this.head;
    }

    public void clear(){
        while (this.head!=null){
            ListNode curNext = head.next;
            this.head.next=null;
            this.head=curNext;
        }
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/354634.html

標籤：其他

上一篇：[OS-Linux]詳解Linux的行程間通信2------system V共享記憶體（Shared Memory）

下一篇：線性表的鏈式存盤結構 ( 鏈表 )

從無都有生成一個單鏈表