JavaScript數(shù)據(jù)結構之鏈表各種操作詳解
更新時間：2022年10月19日 15:47:55 作者：橘貓吃不胖～
數(shù)據(jù)結構是一種有效處理大量數(shù)據(jù)的手段，了解它的結構和組成為我們提供了更有效的工具來設計與某些問題相關的產(chǎn)品。這次我們將進行鏈表介紹，回顧它的特點和用途
1 數(shù)組與鏈表的優(yōu)缺點
鏈表和數(shù)組一樣，都可以用于存儲一系列的元素，但是鏈表和數(shù)組的實現(xiàn)機制完全不同。
一般情況下，要存儲多個元素，數(shù)組可能是最常用的數(shù)據(jù)結構。但是使用數(shù)組存儲有一些缺點：
- 數(shù)組的創(chuàng)建需要申請一段連續(xù)的內存空間（一整塊的內存），并且大小是固定的，所以當當前數(shù)組不能滿足容量需求時，就需要擴容（一般情況下會申請一個更大的數(shù)組，比如2倍，然后將原數(shù)組中的元素復制過去）。
- 在數(shù)組的開頭或中間位置插入數(shù)據(jù)的成本很高，需要進行大量元素的位移。
存儲多個元素的另一個選擇就是鏈表，但是不同于數(shù)組，鏈表中的元素在內存中不必是連續(xù)的空間，鏈表的每個元素由一個存儲元素本身的節(jié)點和指向下一個元素的引用（指針）組成。
那么和數(shù)組相比，鏈表有一些優(yōu)勢：
- 內存空間不是必須連續(xù)的，可以充分利用計算機的內存，實現(xiàn)靈活的內存動態(tài)管理；
- 鏈表不必在創(chuàng)建時就確定大小，并且大小可以無限延伸下去；
- 鏈表在插入和刪除數(shù)據(jù)時，時間復雜度可以達到O(1)，相對數(shù)組效率高很多；
鏈表也有一些缺點：
- 鏈表訪問任何一個元素的位置時，都需要從頭開始訪問，并且無法跳過第一個元素訪問任何一個元素
- 鏈表無法通過下標直接訪問元素，需要從頭一個個訪問，直到找到對應的元素
2 什么是鏈表
鏈表的每個元素由一個存儲元素本身的節(jié)點和指向下一個元素的引用（指針）組成。
它類似于火車，火車頭就是頭節(jié)點，火車車廂之間的連接類似于指針，火車上的乘客類似于數(shù)據(jù)。
接下來我們根據(jù)它的特性來手動封裝一個鏈表。
3 封裝鏈表結構
首先我們來封裝一個鏈表類LindedList，用來表示我們的鏈表結構。LindedList類中應該有兩個屬性，鏈表的頭節(jié)點head和鏈表的長度length。
function LinkedList() {
this.head = null; // 初始指向null
this.length = 0; // 初始鏈表長度為0
}
在LindedList類內部有一個ListNode類，用于創(chuàng)建節(jié)點，創(chuàng)建節(jié)點時應該為節(jié)點傳入數(shù)據(jù)data，并且該節(jié)點有指向下一個節(jié)點的指針。
function LinkedList() {
this.head = null; // 初始指向null
this.length = 0; // 初始鏈表長度為0
function ListNode(data) {
this.data = data;
this.next = null;
}
}
到這里鏈表的基礎結構就完成了，接下來我們來封裝鏈表的方法。
4 向鏈表尾部添加一個新的項
向鏈表尾部添加一個新的節(jié)點，有兩種情況：
- 當鏈表本身為空時，頭節(jié)點就是新添加的節(jié)點
- 當鏈表不為空時，讓鏈表最后一個節(jié)點指向新添加的節(jié)點
根據(jù)這個思路，我們可以實現(xiàn)append方法如下：
LinkedList.prototype.append = function (data) { // data是新節(jié)點的值
let node = new ListNode(data); // 創(chuàng)建新的節(jié)點
if (this.length === 0) { // 如果鏈表為空，則新節(jié)點就是頭節(jié)點
this.head = node;
} else { // 如果鏈表不為空，新節(jié)點添加到鏈表尾部
let current = this.head; // 將current指向頭節(jié)點
// 鏈表無法直接訪問到最后的節(jié)點，只能通過一次次遍歷來訪問
while (current.next) { // 當達到最后一個節(jié)點時，循環(huán)結束
// 當下一個節(jié)點存在時，就讓current指針移動到下一個節(jié)點上
current = current.next;
}
// 最后一個節(jié)點指向新節(jié)點
current.next = node;
}
this.length += 1; // 鏈表的長度+1
}
5 向鏈表某個位置插入一個新的項
在鏈表的任意位置插入節(jié)點時，也分為兩種情況：
- 當插入到第一個位置時，新節(jié)點變成了頭節(jié)點，那么新節(jié)點要指向原來的頭節(jié)點，屬性
head也應該變成新節(jié)點 - 當插入到其他位置時，首先通過循環(huán)找到該位置，同時保存上一個節(jié)點和下一個節(jié)點，然后將上一個節(jié)點指向新節(jié)點，新節(jié)點指向下一個節(jié)點
插入insert方法代碼實現(xiàn)如下：
// position為節(jié)點要插入的位置，data為節(jié)點的值
LinkedList.prototype.insert = function (position, data) {
// 對position進行越界判斷，當該值小于0或者大于鏈表長度時，不能進行插入操作
if (position <= 0 || position > this.length) return false;
let node = new ListNode(data); // 創(chuàng)建新節(jié)點
if (position === 0) { // 如果節(jié)點要插入第一個位置
node.next = this.head; // 新節(jié)點指向原來的頭節(jié)點
this.head = node; // 頭節(jié)點修改為新節(jié)點
} else {
let previous = null; // 指向前一個位置
let current = this.head; // 指向下一個位置
let index = 1; // 記錄循環(huán)的位置
// 循環(huán)結束，previous和current之間就是插入的節(jié)點
while (index < position) {
previous = current;
current = current.next;
index++;
}
previous.next = node; // 在正確的位置插入元素
node.next = current;
}
this.length += 1; // 長度加1
}6 獲取對應位置的元素
獲取某個位置上的元素，也要通過循環(huán)鏈表來找到當前元素，get方法實現(xiàn)如下：
LinkedList.prototype.get = function (position) {
// 越界判斷，如果位置小于0或者大于鏈表長度，不能獲取到元素
if (position <= 0 || position > this.length) return null;
let index = 1; // 記錄當前位置
let current = this.head; // current指向頭節(jié)點
// 循環(huán)結束，current指向該位置上的節(jié)點
while (index < position) {
current = current.next;
index++;
}
return current.data;
}
7 獲取元素在鏈表中的索引
獲取索引時，要循環(huán)遍歷鏈表，將鏈表的每一個節(jié)點值都和給定的值比較，如果相等返回當前節(jié)點的位置，如果沒找到，則返回-1。indexOf方法實現(xiàn)如下：
// 獲取某個元素的位置
LinkedList.prototype.indexOf = function (data) {
let current = this.head;
let index = 1; // 記錄元素的位置
while (current) { // 循環(huán)遍歷鏈表
if (current.data === data) { // 如果當前節(jié)點的值等于元素的值
return index; // 返回位置
} else { // 如果不等于，繼續(xù)循環(huán)
current = current.next;
index++;
}
}
return -1; // 循環(huán)結束了，說明沒找到
}
8 修改某個位置的元素
修改某個位置的元素時，循環(huán)遍歷鏈表，找到給定的位置，修改該位置上元素的值。update方法實現(xiàn)如下：
// 修改某個位置的元素
LinkedList.prototype.update = function (position, data) {
// 越界判斷
if (position <= 0 || position > this.length) return false;
let current = this.head;
let index = 1;
while (index < position) {
current = current.next;
index++;
}
current.data = data; // 修改數(shù)據(jù)
return true;
}
9 從鏈表中刪除某位置節(jié)點
刪除某個位置上的節(jié)點分為兩種情況：
- 刪除第一個位置上的節(jié)點時，要將第一個位置上的節(jié)點指向null，并且第二個位置上的節(jié)點成為頭節(jié)點
- 刪除其他位置上的節(jié)點，循環(huán)找到該位置，同時記錄該節(jié)點上一個節(jié)，將上一個節(jié)點指向該位置的下一個節(jié)點
刪除某位置節(jié)點removeAt方法實現(xiàn)如下：
LinkedList.prototype.removeAt = function (position) {
if (position <= 0 || position > this.length) return false; // 越界判斷
let current = this.head;
if (position === 1) { // 如果刪除第一個位置上的節(jié)點（頭節(jié)點）
this.head = this.head.next;
} else { // 刪除其他位置的節(jié)點
let index = 1; // 記錄當前位置
let previous = null;
while (index < position) {
previous = current;
current = current.next;
index++;
}
// 上一個節(jié)點指向當前元素的下一個節(jié)點
previous.next = current.next;
}
this.length--;
return current; // 返回被刪除的節(jié)點
}
10 全部代碼
function LinkedList() {
this.head = null; // 初始指向null
this.length = 0; // 初始鏈表長度為0
function ListNode(data) { // 創(chuàng)建新節(jié)點類
this.data = data;
this.next = null;
}
// 添加元素
LinkedList.prototype.append = function (data) { // data是新節(jié)點的值
let node = new ListNode(data); // 創(chuàng)建新的節(jié)點
if (this.length === 0) { // 如果鏈表為空，則新節(jié)點就是頭節(jié)點
this.head = node;
} else { // 如果鏈表不為空，新節(jié)點添加到鏈表尾部
let current = this.head; // 將current指向頭節(jié)點
// 鏈表無法直接訪問到最后的節(jié)點，只能通過一次次遍歷來訪問
while (current.next) { // 當達到最后一個節(jié)點時，循環(huán)結束
// 當下一個節(jié)點存在時，就讓current指針移動到下一個節(jié)點上
current = current.next;
}
// 最后一個節(jié)點指向新節(jié)點
current.next = node;
}
this.length += 1; // 鏈表的長度+1
}
// 插入元素
// position為節(jié)點要插入的位置，data為節(jié)點的值
LinkedList.prototype.insert = function (position, data) {
// 對position進行越界判斷，當該值小于0或者大于鏈表長度時，不能進行插入操作
if (position <= 0 || position > this.length) return false;
let node = new ListNode(data); // 創(chuàng)建新節(jié)點
if (position === 0) { // 如果節(jié)點要插入第一個位置
node.next = this.head; // 新節(jié)點指向原來的頭節(jié)點
this.head = node; // 頭節(jié)點修改為新節(jié)點
} else {
let previous = null; // 指向前一個位置
let current = this.head; // 指向下一個位置
let index = 1; // 記錄循環(huán)的位置
// 循環(huán)結束，previous和current之間就是插入的節(jié)點
while (index < position) {
previous = current;
current = current.next;
index++;
}
previous.next = node; // 在正確的位置插入元素
node.next = current;
}
this.length += 1; // 長度加1
}
// 獲取某個位置上的元素
LinkedList.prototype.get = function (position) {
// 越界判斷，如果位置小于0或者大于鏈表長度，不能獲取到元素
if (position <= 0 || position > this.length) return null;
let index = 1; // 記錄當前位置
let current = this.head; // current指向頭節(jié)點
// 循環(huán)結束，current指向該位置上的節(jié)點
while (index < position) {
current = current.next;
index++;
}
return current.data;
}
// 獲取某個元素的位置
LinkedList.prototype.indexOf = function (data) {
let current = this.head;
let index = 1; // 記錄元素的位置
while (current) { // 循環(huán)遍歷鏈表
if (current.data === data) { // 如果當前節(jié)點的值等于元素的值
return index; // 返回位置
} else { // 如果不等于，繼續(xù)循環(huán)
current = current.next;
index++;
}
}
return -1; // 循環(huán)結束了，說明沒找到
}
// 修改某個位置的元素
LinkedList.prototype.update = function (position, data) {
// 越界判斷
if (position <= 0 || position > this.length) return false;
let current = this.head;
let index = 1;
while (index < position) {
current = current.next;
index++;
}
current.data = data; // 修改數(shù)據(jù)
return true;
}
LinkedList.prototype.removeAt = function (position) {
if (position <= 0 || position > this.length) return false; // 越界判斷
let current = this.head;
if (position === 1) { // 如果刪除第一個位置上的節(jié)點（頭節(jié)點）
this.head = this.head.next;
} else { // 刪除其他位置的節(jié)點
let index = 1; // 記錄當前位置
let previous = null;
while (index < position) {
previous = current;
current = current.next;
index++;
}
// 上一個節(jié)點指向當前元素的下一個節(jié)點
previous.next = current.next;
}
this.length--;
return current; // 返回被刪除的節(jié)點
}
}到此這篇關于JavaScript數(shù)據(jù)結構之鏈表各種操作詳解的文章就介紹到這了,更多相關JS鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- JavaScript數(shù)據(jù)結構之雙向鏈表
- JavaScript數(shù)據(jù)結構之雙向鏈表和雙向循環(huán)鏈表的實現(xiàn)
- JavaScript數(shù)據(jù)結構之單鏈表和循環(huán)鏈表
- JavaScript數(shù)據(jù)結構之雙向鏈表定義與使用方法示例
- 使用JavaScript實現(xiàn)鏈表的數(shù)據(jù)結構的代碼
- JavaScript數(shù)據(jù)結構之鏈表的實現(xiàn)
- JavaScript數(shù)據(jù)結構鏈表知識詳解
- JavaScript數(shù)據(jù)結構與算法之鏈表
- JavaScript實現(xiàn)的鏈表數(shù)據(jù)結構實例
相關文章
最近需要用到預加載和延遲加載的東東，就參考寫了一個。支持跨頁面，支持超時設置與依賴設置。2010-05-05
javascript 構造函數(shù)強制調用經(jīng)驗總結
本文將介紹javascript構造函數(shù)調用方面的案例應用，需要了解的朋友可以參考下2012-12-12
javascript FAQ函數(shù)，當點擊問題時顯示下面的回復內容。2009-07-07
JS保存、讀取 換行 轉Json報錯異常信息：Unexpected token ILLEGAL，具體解決方法如下，感性的朋友可以參考下哈2013-06-06
這篇文章主要介紹了Angularjs手動解析表達式（$parse）的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-10-10
用js的document.write輸出的廣告無阻塞加載的方法
這篇文章主要介紹了用js的document.write輸出的廣告無阻塞加載的方法,需要的朋友可以參考下2014-06-06
Typescript 實現(xiàn)函數(shù)重載的方式
函數(shù)重載簡單點說就是,同一個函數(shù)的不同實現(xiàn)方式,根據(jù)傳入的參數(shù)的類型或者長度,決定最終調用哪一個實現(xiàn),本文給大家介紹了Typescript 實現(xiàn)函數(shù)重載的方式,需要的朋友可以參考下2024-05-05
在做 《JS在線打字練習》時，發(fā)現(xiàn)JS在不同瀏覽器上的字符處理是不一樣的。2010-12-12
IE的有條件注釋是一種專有的（因此是非標準的）、對常規(guī)（X）HTML注釋的Miscrosoft擴展。2009-08-08
這篇文章主要介紹了在微信小程序中使用mqtt服務的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-12-12