資料結構與演算法系列2 線性表 鏈表的分類+使用java實作鏈表+鏈表原始碼詳解

資料結構與演算法系列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鏈表的原始碼決議，我也會在我的博客上經常更新一些演算法類的題目， 喜歡的也可以關注我，創作不易，覺得有幫助的可以點贊收藏關注

標籤：其他

上一篇：D. Equalize the Remainders 決議(思維)

下一篇：ubuntu16.04下使用pyinstaller打包pyqt5報錯