[數據結構與算法-小白系列]第2️⃣天鏈表

語言: CN / TW / HK

回顧

第一天我們學習了棧和隊列[數據結構與算法-小白系列]第1️⃣天棧、隊列 今天我們來學習下另外一種重要的數據結構鏈表,個人感覺鏈表理解起來比棧和隊列要難,但不管咱們樣 幹就完了

鏈表棧,隊列有着本質不同

在上一篇中,我們是通過javascript數組實現的棧和隊列,我們知道,數組是線性結構,也就是説數組中的數據是一個一個連續的存放的,我們可以通過下標來讀取元素,所以棧和隊列都是線性儲存數據的,而鏈表就不是了,我們可以先記着鏈表是鏈式存儲的線性表

鏈表是為了解決什麼問題?

存在是有原因的,我們要記着 每一種數據結構都對應着一種典型的應用場景

那鏈表是為了解決什麼問題呢?

我們先來盤盤棧和隊列這種數據結構有什麼缺點,也可以説數組有什麼缺點

首先數組是線性存儲數據,可以通過下標來讀取數據,固然它的 讀取速度非常高,但是如果我們向數據裏面新增或刪除數據,數據的執行效率就不那麼高了,下面我們來看看向數組裏面新增數據的過程

有個數組[2,4,6,8],現在我們需要在2,4之間新增一個3

可以看出我們在插入一個數據的同時,需要改變三個數據的位置,那如果數據量非常大呢,可見 數組在新增和修改數據的時候效率比較低

而鏈表就是為了解決這個問題而生

鏈表的結構

鏈表的精髓在於指針,我們可以把鏈表中的元素稱之為節點,每個節點之間都是通過指針建立關係

那問題來了,為什麼要通過指針建立關係呢?

這就要研究下鏈表是如何存儲數據的了,我們知道數組存儲是連續的,所以可以通過數組的索引拿到值,而鏈表的存儲數據是離散的,那我們如何知道一個節點下個數據是什麼呢?那就只能通過指針,買個節點都保存下個節點的引用,如下所示:

現在如果我們要添加內容只需要移動指針就可以了,如下我們要在2和3中添加一個4

現在的數據結構為1->2->4->3如果要刪除元素4的話直接讓2的指針直接指向3即可 1->2->3

原理很簡單,下面就讓我們用代碼實現一邊把

使用JavaScript實現鏈表

單向鏈表

單向列表就是每個節點都保存的有指向下一個節點的引用,這個指向只能是單向的,比如 1->2->3->4,那我們用代碼怎麼實現呢? 首先我們要創建一個節點

function Node(data){
    this.data = data
    this.next = null
}

複製代碼

我們封裝一個鏈表類,其中有以下幾個方法:

  • append 追加
  • insert 插入
  • get 獲取對應下標的數據
  • indexof 獲取對應數據下標值
  • updata 跟新節點
  • remove 刪除節點
  • toString 鏈表字符串化
function linkedList() {
  //鏈表的節點類
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  this.head = null; // 鏈表的hede 可以理解為指針
  this.length = 0; //鏈表的長度
  // 添加方法
  linkedList.prototype.append = function(data) {
    var newNode = new Node(data);
    // 判斷現在的鏈表是不是空
    if (this.length == 0) {
      // 添加的是第一個節點
      this.head = newNode;
    } else {
      // 不是第一個節點,找到最後一個節點,在其後面追加節點
      var current = this.head;
      while (current.next) {
        current = current.next; //一直往下找
      }

      // 追加最後一個節點
      current.next = newNode;
    }
    this.length++;
  };
  // 插入方法,可以把數據插入到鏈表的任何地方
  linkedList.prototype.insert = function(position, data) {
    // 對 position 越界判斷
    if (position < 0 || position > this.length) {
      return false;
    }
    var newNode = new Node(data);
    // 判斷是不是插入到第一個
    if (position == 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      var index = 0;
      var current = this.head;
      var previous = null; // 記錄上一個節點
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      newNode.next = current;
      previous.next = newNode;
    }
    this.length++;
    return true;
  };
  // 獲取對應位置上的數據
  linkedList.prototype.get = function(position) {
    if (position < 0 || position >= this.length) {
      return null;
    }
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    return current.next;
  };
  // 獲取對應數據的下標值
  linkedList.prototype.indexOf = function(data) {
    var current = this.head;
    var index = 0;
    while (current) {
      if (current.data == data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  };
  // 更新方法
  linkedList.prototype.updata = function(position, data) {
    if (position < 0 || position >= this.length) {
      return false;
    }
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    current.data = data;
    return true;
  };
  // 根據位置 刪除元素
  linkedList.prototype.removeAt = function(position) {
    if (position < 0 || position >= this.length) {
      return false;
    }
    //  刪除第一個
    if (position == 0) {
      this.head = this.head.next;
    } else {
      var current = this.head;
      var previous = null;
      var index = 0;
      while (index++ < position) {
        position = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length -= 1;
    return true;
  };
  // 字符串化
  linkedList.prototype.toString = function() {
    var current = this.head;
    var listString = "";
    // 循環獲取一個個節點
    while (current) {
      listString += current.data + " ";
      current = current.next;
    }
    return listString;
  };
}

複製代碼

雙向鏈表

每個節點都記錄了他上一個和下一個節點的引用,如:

把單向鏈表的的方法改為雙向鏈表實現如下:

// 雙向鏈表
function DoublyList() {
  this.head = null; //指針 指向第一個
  this.tail = null; // 指針 指向最後一個
  this.length = 0; // 列表的長度
  // 內部節點類
  function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
  // 插入到鏈表的尾部
  DoublyList.prototype.append = function(data) {
    // 判斷是否添加的第一個節點
    var newNode = new Node(data);
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length += 1;
  };
  // 插入
  DoublyList.prototype.insert = function(position, data) {
    if (position < 0 || position > this.length) return false;
    var newNode = new Node(data);
    // 插入的節點是第一個節點
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    }
    if (position == 0) {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    } else if (position == this.length) {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      var current = this.head;
      var index = 0;
      while (index++ < position) {
        current = current.next;
      }
      // 更改對應指針指向
      newNode.next = current;
      newNode.prev = current.prev;
      current.prev.next = newNode;
      current.prev = newNode;
    }
    this.length += 1;
  };
  // 獲取對應下標的數據
  DoublyList.prototype.get = function(position) {
    if (position < 0 || position >= this.length) return false;
    // 獲取元素
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    return current.data;
  };
  // 獲取對應值的下標
  DoublyList.prototype.indexOf = function(data) {
    var current = this.head;
    var index = 0;
    while (current) {
      if (current.data == data) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };
  // 根據下標更新
  DoublyList.prototype.updata = function(position, newData) {
    if (position < 0 || position >= this.length) return false;
    // 獲取元素
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    current.data = newData;
    return true;
  };
  // 根據下標刪除
  DoublyList.prototype.removeAt = function(position) {
    if (position < 0 || position > this.length) return false;
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    }

    if (position == 0) {
      this.head.next.prev = null;
      this.head = this.head.next;
    } else if (position == this.length - 1) {
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    } else {
      var index = 0;
      var current = this.head;
      while (index++ < position) {
        current = current.next;
      }

      current.prev.next = current.next;
      current.next.prev = current.prev;
    }
  };
  DoublyList.prototype.toString = function() {
    return this.bacckwardToString();
  };
  // 從後向前遍歷
  DoublyList.prototype.forwardToString = function() {
    var current = this.tail;
    var resString = "";
    while (current) {
      current = current.prev;
      resString += current.data + " ";
    }
    return resString;
  };
  // 從前向後遍歷
  DoublyList.prototype.bacckwardToString = function() {
    var current = this.head;
    var resString = "";
    while (current) {
      current = current.next;
      resString += current.data + " ";
    }
    return resString;
  };
}
複製代碼

最後

點個👍希望和你交個朋友