數據結構與演算法系列2 線性表鏈表的分類+使用java實現鏈表+鏈表源碼詳解

2020 年 9 月 2 日
筆記
數據結構與演算法

數據結構與演算法系列2.2 線性表

什麼是鏈表？

鏈表是一種物理存儲單元上非連續，非順序的存儲結構，數據元素的邏輯順序是通過鏈表的鏈接次序實現的一系列節點組成，節點可以在運行時動態生成，每個節點包括兩個部分，一個是村粗數據元素的數據域，一個是存儲指針的指針域，相比於線性表順序結構，操作複雜。由於不必須按照順序存儲，鏈表在插入的時候可以達到o(1)的複雜讀，比另一種線性表順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁碟上順序，數據的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。鏈表可以在多種程式語言中實現。像Lisp和Scheme這樣的語言的內建數據類型中就包含了鏈表的存取和操作。程式語言或面向對象語言，如C,C++和Java依靠易變工具來生成鏈表。

啥是單向鏈表和雙向鏈表及循環鏈表？

單向鏈表

其特點是鏈表的連接方向是單向的，對鏈表的訪問要通過順序從頭部開始，鏈表是使用指針進行構造的鏈表，又稱為結點列表，因為鏈表是由一個個結點組裝起來的；其中每個結點都有指針成員變數指向列表中的下一個結點；
因為單向鏈表的每個節點只包含兩部分,一部分存放數據變數的data,另一部分是指向下一節點的next指針

雙向鏈表

雙向鏈表和單向鏈表的差別不是很大，只是比單向鏈表多了一個指向直接前驅節點的指針，這樣使得，可以從雙向鏈表的任一一個節點開始，都可以方便的訪問它的前驅節點和後繼節點

循環鏈表

循環鏈表是另一種形式的鏈式存貯結構。它的特點是表中最後一個結點的指針域指向頭結點，整個鏈表形成一個環。

單向鏈表的程式碼實現，這裡只講幾個常用到的方法

int size（）；元素的數量
boolean isEmpty（）；是否為空
boolean contains（E element); 判斷是否包含某個元素
void add（E element） ；添加元素到最後
E get（int index）；返回index對應位置的元素
E set（int index，E element）；往index位置添加元素
void add（int index，E element）；往index位置添加元素
E remove（int index）； 刪除index位置對應的元素
int indexOf（E element）； 查看元素的位置
void clear（）；清除所有元素

成員變數

  //頭節點
    private Node<E> first;
 
  // 元素的數量
  
    protected int size;

將節點定義為內部類

public static class Node<E>{
        //元素
        E element;
        //指針
        Node<E> next;
        //構造函數
        public Node(E element,Node<E> next){
            this.element=element;
            this.next=next;
        }
    }

清空所有元素 clear（）

public void clear() {
           size=0;
           first=null;
    }

將fist設置為null即可，因為當fist與節點斷開連接後，該鏈表就會被自動回收，不必當心記憶體浪費

添加元素 add（int index，E element）

 public void add(int index, E element) {
      //檢查範圍是否合法
        rangeCheck(index);
        //如果在索引為零的地方插入
        if (index==0){
            first=new Node<>(element,first);
        }else{
            //查找插入節點的前一個節點
            Node<E> prev=node(index-1);
            prev.next=new Node<>(element,prev.next);
        }
        size++;
    }

以圖演示

要在1——2之間插入一個新的節點3，則要將1的指針指向3，再將3的指針指向2

在末尾添加元素

 public void add(E element) {
        add(size, element);
    }

直接調用上一個方法即可

獲得指定節點位置的元素node（int index）

  //獲取index位置對應的節點對象
    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node=first;
        for (int i = 0; i < index; i++) {
            node=node.next;
        }
        return  node;
    }

刪除元素remove（int index）

public E remove(int index) {
        //檢查插入位置是否合理
        rangeCheck(index);
        ///查找要移除元素的前一個元素
        //如果為零
        Node<E> node = first;
        if (index==0){
            first=first.next;
        }else{
            Node<E> prev = node(index - 1);
            node=prev.next;
            prev.next=node.next;
        }
        size--;
        return node.element;
    }

圖解

比如我要將3這個節點移除，那麼我就要將1的指針指向2，即3指針指向的的節點

獲取第index位置的元素

  @Override
    public E get(int index) {
        return node(index).element;
    }

設置第index位置的元素

   @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old= node.element;
        node.element=element;
        return old;
    }

以上就是java鏈表的源碼解析，我也會在我的部落格上經常更新一些演算法類的題目，喜歡的也可以關注我，創作不易，覺得有幫助的可以點贊收藏關注

Tags: 數據結構與演算法