JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表 | 技術(shù)點(diǎn)評(píng)
Github來(lái)源：力扣 (LeetCode)｜刷題打卡 | 求星星 ? | 給個(gè)??關(guān)注，??點(diǎn)贊，??鼓勵(lì)一下作者
[已開(kāi)啟]任務(wù)一：刷題打卡 * 10 篇
哪吒人生信條：如果你所學(xué)的東西 處于喜歡 才會(huì)有強(qiáng)大的動(dòng)力支撐。
每天學(xué)習(xí)編程，讓你離夢(mèng)想更新一步，感謝不負(fù)每一份熱愛(ài)編程的程序員，不論知識(shí)點(diǎn)多么奇葩，和我一起，讓那一顆四處流蕩的心定下來(lái)，一直走下去，加油，2021加油！歡迎關(guān)注加我vx:xiaoda0423，歡迎點(diǎn)贊、收藏和評(píng)論
時(shí)間：3 月 1 日 ～ 3 月 13 日
力扣 (LeetCode)-兩數(shù)之和,有效的括號(hào),兩數(shù)相加｜刷題打卡-3月1日 力扣 (LeetCode)-合并兩個(gè)有序鏈表,刪除排序數(shù)組中的重復(fù)項(xiàng),JavaScript筆記｜刷題打卡-3月2日 力扣 (LeetCode)-最大子序和,JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（數(shù)組）｜刷題打卡-3月3日 針對(duì)CSS說(shuō)一說(shuō)｜技術(shù)點(diǎn)評(píng)-3月4日 力扣 (LeetCode)-棧,括號(hào)生成 ｜刷題打卡-3月5日 原來(lái)也沒(méi)有那么難！Vue商城開(kāi)發(fā) | 技術(shù)點(diǎn)評(píng)-3月6日 力扣 (LeetCode)-加一，隊(duì)列 ｜刷題打卡-3月7日
前言
如果這篇文章有幫助到你，給個(gè)??關(guān)注，??點(diǎn)贊，??鼓勵(lì)一下作者，接收好挑戰(zhàn)了嗎？文章公眾號(hào)首發(fā)，關(guān)注 程序員哆啦A夢(mèng) 第一時(shí)間獲取最新的文章
??筆芯??~
鏈表
鏈表數(shù)據(jù)結(jié)構(gòu)，向鏈表添加元素，從鏈表移除元素，使用LinkedList類(lèi)，雙向鏈表，循環(huán)鏈表。
鏈表存儲(chǔ)有序的元素集合，但鏈表中的元素在內(nèi)存中并不是連續(xù)放置的，每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用（指針或鏈接）組成。
示例：
鏈表的好處：添加或移除元素的時(shí)候不需要移動(dòng)其他元素
訪問(wèn)鏈表中間的一個(gè)元素，需要從起點(diǎn)（表頭）開(kāi)始迭代列表直到找到所需的元素
鏈表：生活中的尋寶游戲例子。
創(chuàng)建鏈表
function LinkedList() {
let Node = function(element) {
// LinkedList數(shù)據(jù)結(jié)構(gòu)還需要一個(gè)Node輔助類(lèi)
this.element = element;
this.next = null;
};
// Node類(lèi)表示要加入列表的項(xiàng)
// 它包含一個(gè)element屬性，即要添加到列表的值，以及一個(gè)next屬性，即指向列表中下一個(gè)節(jié)點(diǎn)項(xiàng)的指針
let length = 0;
// LinkedList類(lèi)也有存儲(chǔ)列表項(xiàng)的數(shù)量的length屬性
let head = null;
// 需要存儲(chǔ)第一個(gè)節(jié)點(diǎn)的引用，這個(gè)引用存儲(chǔ)在一個(gè)為head的變量中
// append(element),向列表尾部添加一個(gè)新的項(xiàng)
this.append = function(element){};
// insert(position,element),向列表的特定位置插入一個(gè)新的項(xiàng)
this.insert = function(position, element){};
// removeAt(position),從列表的特定位置移除一項(xiàng)
this.removeAt = function(position){};
// remove(element),從列表中移除一項(xiàng)
this.remove = function(element){};
// indexOf(element),返回元素在列表中的索引，如果列表中沒(méi)有該元素則返回-1
this.indexOf = function(element){};
// 如果鏈表中不包含任何元素，返回true，如果鏈表長(zhǎng)度大于0則返回false
this.isEmpty = function(){};
// 返回鏈表包含的元素個(gè)數(shù)
this.size = function(){};
this.getHead = function(){};
// 由于列表項(xiàng)使用了Node類(lèi)，就需要重寫(xiě)繼承來(lái)自JavaScript對(duì)象默認(rèn)的toString方法，讓其只輸出元素的值
this.toString = function(){};
this.print = function(){};
}
向鏈表尾部追加元素
場(chǎng)景：
列表為空，添加第一個(gè)元素 列表不為空，向其追加元素
this.append = function(element){
// 需要把element作為值傳入，創(chuàng)建Node項(xiàng)
let node = new Node(element),
//
current;
if(head === null) {
// 列表中第一個(gè)節(jié)點(diǎn)
// 在向列表添加第一個(gè)元素
// 下一個(gè)node元素將會(huì)自動(dòng)成為null
head = node;
}else{
// 要向列表的尾部添加一個(gè)元素，首先需要找到最后一個(gè)元素
current = head;
// 循環(huán)列表，直到找到最后一項(xiàng)
while(current.next){
// 需要一個(gè)指向列表中current項(xiàng)的變量
current = current.next
}
// 找到最后一項(xiàng)，將其next賦為node，建立鏈接
current.next = node
}
length++; // 更新列表的長(zhǎng)度
};
let list = new LinkedList();
list.append(1);
list.append(2);
從鏈表中移除元素
場(chǎng)景：1,移除第一個(gè)元素；2,移除第一個(gè)以外的任一元素
// 從特定位置移除一個(gè)元素
// 根據(jù)元素的值移除元素
this.removeAt = function(position) {
// 檢查越界值
if(position > -1 && position < length) {
// 該方法要得到需要移除的元素的位置，就需要驗(yàn)證這個(gè)位置是有效的
let current = head, // 將用current變量創(chuàng)建一個(gè)對(duì)列表中第一個(gè)元素的引用
previous, //
index = 0; //
// 移除第一項(xiàng)
if(position === 0) {
// 從列表中移除第一個(gè)元素 讓head指向列表的第二個(gè)元素
// 把head賦為current.next，就會(huì)移除第一個(gè)元素
head = current.next;
} else {
while (index++ < position) {
// 需要依靠一個(gè)細(xì)節(jié)來(lái)迭代列表，直到到達(dá)目標(biāo)位置
previous = current; // 對(duì)當(dāng)前元素的前一個(gè)元
素的引用
current = current.next; // current變量總是為對(duì)所循環(huán)列表的當(dāng)前元素的引用
}
// 將previous與current的下一項(xiàng)鏈接起來(lái)，跳過(guò)current，從而移除它
previous.next = current.next;
// 要從列表中移除當(dāng)前元素，要做的就是將previous.next和current.next鏈接起來(lái)
}
length--; //
return current.element;
}else{
return null; // 如果不是有效的位置，就返回null
}
}
在任意位置插入元素
使用insert方法，可以在任意位置插入一個(gè)元素
this.insert = function(position, element){
//檢查越界值
if (position >= 0 && position <= length){
//需要檢查越界值
let node = new Node(element),
current = head, // current變量是對(duì)列表中第一個(gè)元素的引用
previous,
index = 0;
if (position === 0){ //在第一個(gè)位置添加
node.next = current; //把node.next的值設(shè)為current
head = node; // 把head的引用改為node
// head和node.next都指向了current
} else {
// 在列表中間或尾部添加一個(gè)元素
while (index++ < position){ //需要循環(huán)訪問(wèn)列表，找到目標(biāo)位置
previous = current;
current = current.next;
}
node.next = current; //當(dāng)跳出循環(huán)時(shí)，current變量將是對(duì)想要插入新元素的位置之后一個(gè)元素的引用
// previous.next指向node
previous.next = node; //previous將是對(duì)想要插入新元素的位置之前一個(gè)元素的引用
}
length++; //更新列表的長(zhǎng)度
return true;
} else {
return false; //返回false值，表示沒(méi)有添加項(xiàng)到列表中
}
};
previous將是對(duì)列表最后一項(xiàng)的引用current將是nullnode.next將指向current，而previous.next將指向node
需要把 node.next的值指向current。然后把previous.next的值設(shè)為node
toString方法會(huì)把LinkedList對(duì)象轉(zhuǎn)換成一個(gè)字符串
this.toString = function(){
// 會(huì)把current變量當(dāng)作索引
let current = head, //需要有一個(gè)起點(diǎn)
string = ''; //還需要初始化用于拼接元素值的變量
while (current) { //循環(huán)訪問(wèn)列表中的每個(gè)元素
string += current.element + (current.next ? 'n' : '');
//得到了元素的內(nèi)容，將其拼接到字符串中
current = current.next;
//繼續(xù)迭代下一個(gè)元素
}
return string; //返回列表內(nèi)容的字符串
};
indexOf方法接收一個(gè)元素的值,如果在列表中找到它，就返回元素的位置，否則返回-1
this.indexOf = function(element){
let current = head, //是current，它的初始值是head
// 需要一個(gè)index變量來(lái)計(jì)算位置數(shù)
index = -1;
// 循環(huán)訪問(wèn)元素
while (current) {
if (element === current.element) {
return index; //檢查當(dāng)前元素是否是我們要找的。如果是，就返回它的位置
}
index++; //如果不是，就繼續(xù)計(jì)數(shù)
current = current.next; //檢查列表中下一個(gè)節(jié)點(diǎn)
}
// 如果列表為空，或是到達(dá)列表的尾部
// current = current.next將是null
return -1;
};
其他的方法：
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
雙向鏈表
在雙向鏈表中，鏈接是雙向的 一個(gè)鏈向下一個(gè)元素，另一個(gè)鏈向前一個(gè)元素
function DoublyLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //新增的 一個(gè)新指針
};
let length = 0;
let head = null;
let tail = null; //新增的
//這里是方法
}
在任意位置插入新元素
控制 next和prev（previous，前一個(gè)）
this.insert = function(position, element){
//檢查越界值
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
// 在列表的第一個(gè)位置（列表的起點(diǎn)）插入一個(gè)新元素1
if (position === 0){ //在第一個(gè)位置添加
if (!head){ //新增的
// 只需要把head和tail都指向這個(gè)新節(jié)點(diǎn)
head = node;
tail = node;
} else {
node.next = current;
// current.prev指針將由指向null變?yōu)橹赶蛐略?br> current.prev = node; //新增的
head = node;
}
} else if (position === length) { //最后一項(xiàng) //新增的
current = tail; // 控制著指向最后一個(gè)元素的指針（tail）
// current變量將引用最后一個(gè)元素
current.next = node; //current.next指針（指向null）將指向node
node.prev = current; //node.prev將引用current
tail = node; // 更新tail
// 它將由指向current變?yōu)橹赶騨ode
} else {
// 在列表中間插入一個(gè)新元素
while (index++ < position){ //直到到達(dá)要找的位置
previous = current;
current = current.next;
}
node.next = current; //node.next將指向current
previous.next = node; // previous.next將指向node
current.prev = node; //新增的current.prev將指向node
node.prev = previous; //新增的node.prev將指向previous
}
length++; //更新列表的長(zhǎng)度
return true;
} else {
return false;
}
};
從任意位置移除元素
示例：
從雙向鏈表移除第一個(gè)元素的過(guò)程：
this.removeAt = function(position){
//檢查越界值
if (position > -1 && position < length){
// current變量是對(duì)列表中第一個(gè)元素的引用
let current = head,
previous,
index = 0;
//移除第一項(xiàng)
if (position === 0){
// 改變 head 的引用
head = current.next; //將其從 current 改為下一個(gè)元素
//如果只有一項(xiàng)，更新tail //新增的
if (length === 1){
//檢查要移除的元素是否是第一個(gè)元素，如果是，只需要把tail也設(shè)為null
tail = null;
} else {
head.prev = null; //把head.prev的引用改為null
}
} else if (position === length-1){ //最后一項(xiàng) //新增的
// 從最后一個(gè)位置移除元素
current = tail; //把tail的引用賦給current變量
tail = current.prev;
tail.next = null;
} else {
// 從列表中間移除一個(gè)元素
while (index++ < position){
//需要迭代列表，直到到達(dá)要找的位置
// current變量所引用的就是要移除的元素
// 更新previous.next和current.next.prev的引用
// previous.next將指向current.next
previous = current;
// current.next.prev將指向previous
current = current.next;
}
//將previous與current的下一項(xiàng)鏈接起來(lái)——跳過(guò)current
previous.next = current.next; // {6}
current.next.prev = previous; //新增的
}
length--;
return current.element;
} else {
return null;
}
};
從最后一個(gè)位置移除元素
從列表中間移除一個(gè)元素
從頭部、從中間和從尾部移除一個(gè)元素
循環(huán)鏈表
循環(huán)鏈表和鏈表之間唯一的區(qū)別在于：最后一個(gè)元素指向下一個(gè)元素的指針（tail.next）不是引用null，而是指向第一個(gè)元素（head）
雙向循環(huán)鏈表有指向head元素的tail.next，和指向tail元素的head.prev。
總結(jié)：
JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表
回看筆者往期高贊文章，也許能收獲更多喔！
一個(gè)合格的初級(jí)前端工程師需要掌握的模塊筆記 Vue.js筆試題解決業(yè)務(wù)中常見(jiàn)問(wèn)題 【初級(jí)】個(gè)人分享Vue前端開(kāi)發(fā)教程筆記 長(zhǎng)篇總結(jié)之JavaScript，鞏固前端基礎(chǔ) 前端面試必備ES6全方位總結(jié) 達(dá)達(dá)前端個(gè)人web分享92道JavaScript面試題附加回答 【圖文并茂，點(diǎn)贊收藏哦！】重學(xué)鞏固你的Vuejs知識(shí)體系 【思維導(dǎo)圖】前端開(kāi)發(fā)-鞏固你的JavaScript知識(shí)體系 14期-連肝7個(gè)晚上，總結(jié)了計(jì)算機(jī)網(wǎng)絡(luò)的知識(shí)點(diǎn)！（共66條） 這是我的第一次JavaScript初級(jí)技巧 localStorage和sessionStorage本地存儲(chǔ) HTML5中的拖放功能 挑戰(zhàn)前端知識(shí)點(diǎn)HTTP/ECMAScript 必學(xué)必會(huì)-音頻和視頻 前端170面試題+答案學(xué)習(xí)整理（良心制作） 前端HTML5面試官和應(yīng)試者一問(wèn)一答 哪吒鬧海，席卷圖文學(xué)習(xí)前端Flex布局 騰訊位置服務(wù)開(kāi)發(fā)應(yīng)用 【進(jìn)階】面試官問(wèn)我Chrome瀏覽器的渲染原理（6000字長(zhǎng)文） 面試官一上來(lái)就問(wèn)我Chrome底層原理和HTTP協(xié)議（萬(wàn)字長(zhǎng)文） 熬夜總結(jié)了 “HTML5畫(huà)布” 的知識(shí)點(diǎn) this/call/apply/bind（萬(wàn)字長(zhǎng)文） HTTP/HTTPS/HTTP2/DNS/TCP/經(jīng)典題 執(zhí)行上下文/作用域鏈/閉包/一等公民 Web頁(yè)面制作基礎(chǔ) 學(xué)習(xí)總結(jié)之HTML5劍指前端（建議收藏，圖文并茂）
??關(guān)注+點(diǎn)贊+收藏+評(píng)論+轉(zhuǎn)發(fā)??，原創(chuàng)不易，鼓勵(lì)筆者創(chuàng)作更好的文章
點(diǎn)贊、收藏和評(píng)論
我是Jeskson(達(dá)達(dá)前端)，感謝各位人才的：點(diǎn)贊、收藏和評(píng)論，我們下期見(jiàn)！(如本文內(nèi)容有地方講解有誤，歡迎指出?謝謝，一起學(xué)習(xí)了)
我們下期見(jiàn)！
文章持續(xù)更新，可以微信搜一搜「 程序員哆啦A夢(mèng) 」第一時(shí)間閱讀，回復(fù)【資料】有我準(zhǔn)備的一線大廠資料，本文 http://www.dadaqianduan.cn/#/ 已經(jīng)收錄
github收錄，歡迎Star：https://github.com/webVueBlog/WebFamily
評(píng)論
圖片
表情