認識鏈表以及其常見操作

1.鏈表的概念及其結構
- 1.1鏈表的概念
- 1.2鏈表的結構和種類
2.鏈表的實作
- 2.1無頭單向非回圈鏈表實作
- - 2.1.1準備方法
  - - 2.1.1.1列印單鏈表
    - 2.1.1.2得到鏈表的長度
    - 2.1.1.3查找是否包含關鍵自key在單鏈表中
    - 2.1.1.4查找具有指定值的前一個節點
    - 2.1.1.4查找是否包含關鍵字key在單鏈表當中
  - 2.1.2頭插法
  - 2.1.3尾插法
  - 2.1.4任意位置插入，假設第一個資料節點為0下標
  - 2.1.5洗掉第一次出現關鍵字為key的節點
  - 2.1.6洗掉所有值為key的節點
- 2.2無頭雙向鏈表實作
- - 2.2.1準備方法
  - - 2.2.1.1查找節點
    - 2.2.1.2得到鏈表的長度
  - 2.2.1.3查找是否包含關鍵字key在單鏈表當中
  - 2.2.1頭插法
  - 2.2.2尾插法
  - 2.2.3任意位置插入，假設第一個資料節點為0下標
  - 2.2.4洗掉第一次出現關鍵字為key的節點
  - 2.2.5洗掉所有值為key的節點
  - 2.2.6清空鏈表

1.鏈表的概念及其結構

1.1鏈表的概念

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的，

鏈表的每個節點都是有資料域和指標域組成，
指標域用來儲存資料，指標域用來指向下一個節點，

如下圖所示
在這里插入圖片描述

1.2鏈表的結構和種類

鏈表主要分為三類：

帶頭和不帶頭
單向和雙向
回圈和非回圈

這三類可以演化出8種結構：
單向：
單向帶頭回圈
單向帶頭非回圈
單向不帶頭回圈
單向不帶頭非回圈
雙向：
雙向帶頭回圈
雙向帶頭非回圈
雙向不帶頭回圈
雙向不帶頭非回圈

本篇博客重點是單向不帶頭非回圈

帶頭和不帶頭的區別：
帶頭：這個鏈表的頭結點隨時可能發生改變
不帶頭：這個鏈表的頭結點不在發生改變

常見鏈表示意圖：
無頭單向鏈表
無頭單鏈表
有頭單向鏈表：

回圈單鏈表：

在Java的集合框架庫中LinkedList底層實作就是無頭雙向回圈鏈表，
無頭雙向回圈鏈表：
在這里插入圖片描述

2.鏈表的實作

2.1無頭單向非回圈鏈表實作

class ListNode{
    public int val;//資料域
    public ListNode next;//null   指標域

    public ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList {
    public ListNode head;//標識單鏈表的頭節點
    //采用窮舉的方式創建鏈表，只是為了方便理解
   public void createList(){
       //對每一個節點進行賦值
       ListNode listNode1 = new ListNode(1);
       ListNode listNode2 = new ListNode(2);
       ListNode listNode3 = new ListNode(3);
       ListNode listNode4 = new ListNode(4);
       //將節點之間鏈接起來
       listNode1.next = listNode2;
       listNode2.next = listNode3;
       listNode3.next = listNode4;
       this.head = listNode1;//指明頭節點
   }

2.1.1準備方法

2.1.1.1列印單鏈表

   //列印單鏈表
    public void show(){
        ListNode cur = this.head;//防止在列印的程序中導致頭節點位置偏移
        while(cur!=null){//不是空節點
            System.out.println(cur.val+" ");
            cur=cur.next;//指向節點向后移動一位
        }
        System.out.println();
    }

2.1.1.2得到鏈表的長度

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

2.1.1.3查找是否包含關鍵自key在單鏈表中

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

2.1.1.4查找具有指定值的前一個節點

//查找具有指定值的前一個節點
    public ListNode searchPrevNode(int val){
        ListNode cur = this.head;
        while(cur.next!=null){
            if(cur.next.val == val){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

2.1.1.4查找是否包含關鍵字key在單鏈表當中

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

2.1.2頭插法

    //頭插法
    public void addFirst(int data){
        ListNode listNode = new ListNode(data);
        if(this.head == null){//判斷是否為第一次插入
            this.head = listNode;
        }else{
            listNode.next = this.head;//先系結后一個節點
            this.head = listNode;//更新頭節點位置
        }
    }

2.1.3尾插法

//尾插法
    public void addLast(int data){
        ListNode listNode = new ListNode(data);
        if(this.head == null){//判斷是否為第一次插入
            this.head = listNode;
        }else{
            ListNode cur = this.head;//防止頭節點位置偏移
            while(cur.next!=null){
                cur = cur.next;//找到尾節點
            }
            cur.next = listNode;//鏈接節點
        }
    }

2.1.4任意位置插入，假設第一個資料節點為0下標

 //任意位置插入，第一個資料節點為0號下標
    public void addIndex(int index,int data){
        if(index < 0 || index > size()){//首先判斷坐標是否合法
            System.out.println("下標不合法");
            return;
        }
        //若插入位置為第一個位置，頭插法
        if(index == 0){
            addFirst(data);
            return;
        }
        //若插入位置為最后一個位置，尾插法
        if(index == size()){
            addLast(data);
            return;
        }
        ListNode cur = searchPrev(index);//找到指定的坐標位置
        ListNode listNode = new ListNode(data);
        //插入節點
        listNode.next = cur.next;
        cur.next = listNode;
    }

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

洗掉某一個節點的原理就是不再有參考指向該節點，Java虛擬機會自動回收

    //洗掉第一次出現關鍵字key的節點
    public void remove(int val){
        if(this.head ==null) return;//沒有節點直接回傳
        //單獨判斷頭節點的問題
        if(this.head.val == val){
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrevNode(val);//查找到指定值的坐標位置的前一個節點
        if(cur ==null){//判斷坐標是否為空
            System.out.println("沒有你要洗掉的節點");
            return;
        }//洗掉該節點
        ListNode del = cur.next;
        cur.next = del.next;
    }

2.1.6洗掉所有值為key的節點

 //洗掉所有值為key的節點
    public void removeAllKey(int val){
        if(this.head == null){//若沒有節點，直接回傳
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while(cur!=null){//節點不為空，進入回圈
            if(cur.val == val){//找到一個與指定值相同的節點，洗掉
                prev.next = cur.next;
                cur = cur.next;//洗掉后向后移動一位
            }else{//與指定值不同，向后移動一位
                prev = cur;
                cur = cur.next;
            }
        }
        //最后判斷頭節點是否為該值
        if(this.head.val == val){
            this.head = this.head.next;

        }
    }

2.2無頭雙向鏈表實作

class ListNodeD{
    public int data;//資料域
    public ListNodeD prev;//前驅
    public ListNodeD next;//后繼

    public ListNodeD(int data){
        this.data = data;
    }
}

public class MyRealLinkedList {
    public ListNodeD head;//頭
    public ListNodeD last;//尾

    public MyRealLinkedList(){
        //this.head = new ListNode(-1);傀儡節點
    }

2.2.1準備方法

2.2.1.1查找節點

    //查找節點
    public ListNodeD findIndex(int index){
        ListNodeD cur = this.head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

2.2.1.2得到鏈表的長度

    //得到鏈表的長度
    public int size(){
        int count = 0;
        if(this.head == null) return count;//鏈表長度為零
        ListNodeD cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

2.2.1.3查找是否包含關鍵字key在單鏈表當中

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

2.2.1頭插法

   //頭插法
    public void addFirst(int data){
        ListNodeD node = new ListNodeD(data);
        if(head == null){
            this.head = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

2.2.2尾插法

    //尾插法
    public void addLast(int data){
        ListNodeD node = new ListNodeD(data);
        if(head == null){
            this.head = node;
            this.last = node;
        }else{
            last.next = node;
            node.prev = last;
            last = node;

        }
    }

2.2.3任意位置插入，假設第一個資料節點為0下標

   //任意位置插入，第一個節點為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;
        }
        ListNodeD cur = findIndex(index);
        ListNodeD node = new ListNodeD(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur;
        cur.prev = node;
    }

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

   //洗掉第一次出現key的節點
    public void remove(int key){
        ListNodeD cur = this.head;
        while(cur!=null){
            if(cur.data == key){
                //判斷是不是頭節點
                if(cur == this.head){
                    this.head = this.head.next;
                    if(this.head == null){//防止只有一個節點
                        this.last = null;
                    }else{
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    //尾巴節點
                    if(cur.next == null){
                        this.last = cur.prev;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }
        }
    }

2.2.5洗掉所有值為key的節點

    //洗掉所有值為key的節點
    public void removeAllKey(int key){
        ListNodeD cur = this.head;
        while(cur!=null){
            if(cur.data == key){
                //判斷是不是頭節點
                if(cur == this.head){
                    this.head = this.head.next;
                    if(this.head == null){//防止只有1個節點
                        this.last = null;
                    }else{
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    //尾巴節點
                    if(cur.next == null){
                        this.last = cur.prev;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
                cur = cur.next;//繼續往后走，直到null的時候
            }else{
                cur = cur.next;
            }
        }
    }

2.2.6清空鏈表

   //
    public void clear(){
        ListNodeD cur = this.head;
        while(cur != null){
            ListNodeD curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
        this.last = null;
    }

}

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

標籤：java

上一篇：【趁著室友干飯的時間，小舞偷偷學會了java例外~】

下一篇：LeetCode - 997 -找到小鎮的法官 - Java

認識鏈表以及其常見操作Java代碼實作