資訊專欄INFORMATION COLUMN
摘要：鏈表數(shù)據(jù)結(jié)構(gòu)鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素咋內(nèi)存中并不是連續(xù)放置的每個(gè)元素有一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。
1.鏈表數(shù)據(jù)結(jié)構(gòu)
鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素咋內(nèi)存中并不是連續(xù)放置的每個(gè)元素有一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。下圖展示了一個(gè)鏈表的結(jié)構(gòu)：
鏈表的優(yōu)點(diǎn)：
鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu)，不需要初始化容量，可以任意加減元素；
添加或者刪除元素時(shí)只需要改變前后兩個(gè)元素結(jié)點(diǎn)的指針域指向地址即可，所以添加，刪除很快；
缺點(diǎn)：
因?yàn)楹写罅康闹羔樣?，占用空間較大；
查找元素需要遍歷鏈表來(lái)查找，非常耗時(shí)。
適用場(chǎng)景：
數(shù)據(jù)量較小，需要頻繁增加，刪除操作的場(chǎng)景
function LinkedList() {
// 創(chuàng)建一個(gè)node類，表示將要加入的項(xiàng) element表示要添加的值，next指向列表中下一個(gè)節(jié)點(diǎn)項(xiàng)的指針
let Node = function(element) {
this.element = element;
this.next = null;
}
let length = 0;
let head = null;
// 下面聲明鏈表的方法
// 1.向列表尾部添加一個(gè)新的項(xiàng)
this.append = function(element) {
let node = new Node(element);
current;
// 列表為空,添加的是第一個(gè)元素
if(head === null) {
head = node;
// 列表不為空，向其追加
} else {
current = head;
// 循環(huán)列表，直到找到最后一項(xiàng)
while(current.next) {
current = current.next;
}
// 找到最后一項(xiàng)，將其next賦為node，建立鏈接
current.next = node;
}
// 更新列表長(zhǎng)度
length++;
}
// 2.從列表中移除元素
this.removeAt = function(position) {
// 檢查position是否超出鏈表范圍
if(position > -1 && position < length) {
let current = head,
previous,
index = 0;
// 移除第一個(gè)元素
if(position === 0 ) {
head = current.next;
} else {
// 循環(huán)到指定位置，找到該位置的 previous和current
while(index++ < position) {
previous = current;
current = current.next;
}
// 將previous與current的下一項(xiàng)鏈接起來(lái)：跳過(guò)current
previous.next = current.next;
}
// 鏈表長(zhǎng)度減一
length--;
// 返回被刪除項(xiàng)
return current.element;
} else {
// 不是有效位置，返回null
return null
}
}
// 3.在任意位置插入元素
this.insert = function(element, position) {
//判斷是否超過(guò)鏈表范圍
if (position >= 0 && position<= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
// 在首位插入元素
if (position === 0 ) {
node.next = current;
head = node;
} else{
// x循環(huán)到position應(yīng)該添加的位置，取出previous和current
while(index++ < position) {
previous = current;
current = current.next;
}
// 在previous和current間插入
node.next = current;
previous.next = node;
};
// 更新鏈表長(zhǎng)度
length++;
return true;
} else{
return false;
};
}
//4. 把LinkedList對(duì)象轉(zhuǎn)化成字符串
this.toString = function() {
let current = head,
string = "";
while(current) {
string += current.element + (current.next ? "n" : "");
current = current.next;
}
return string;
}
//5.鏈表中是否存在某個(gè)值
this.indexOf = function(element) {
let current = head,
index = 0;
while(current) {
if(element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
//6.通過(guò)element實(shí)現(xiàn)remove元素
this.remove = function(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
//7.isEmpty size getHead方法
this.isEmpty = function() {
return length === 0;
}
this.size = function() {
return length;
}
this.getHead = function() {
return head;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/101731.html
摘要：實(shí)現(xiàn)移除給定的元素要移除的元素返回值表示移除成功方法說(shuō)明移除單向鏈表中某個(gè)位置的元素。的前端樂(lè)園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法二鏈表 本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合第四篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與...
摘要：鏈表鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個(gè)節(jié)點(diǎn)的鏈接，是雙向的。 鏈表 鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)元素由一個(gè)存儲(chǔ)元素本事的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或...
摘要：鏈表數(shù)據(jù)結(jié)構(gòu)與算法第五章鏈表數(shù)據(jù)結(jié)構(gòu)鏈表不同與數(shù)組數(shù)組要插入或者移入一個(gè)元素的成本很高，因?yàn)樗性囟夹枰苿?dòng)位置。 JavaScript-鏈表 《Javascript數(shù)據(jù)結(jié)構(gòu)與算法》第五章 5.1 鏈表數(shù)據(jù)結(jié)構(gòu) 鏈表不同與數(shù)組 數(shù)組要插入或者移入一個(gè)元素的成本很高，因?yàn)樗性囟夹枰苿?dòng)位置。 鏈表插入或者移動(dòng)一個(gè)元素時(shí)很高效，因?yàn)椴⒉恍枰苿?dòng)其他的元素位置。 鏈表存儲(chǔ)元素的方式...
摘要：循環(huán)鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。以下就以如何創(chuàng)建棧數(shù)據(jù)結(jié)構(gòu)為例。 循環(huán)鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。性能上也跟雙向鏈表差不多，如果position大于length/2，那就可以從尾部開(kāi)始迭代，可以減少迭代的元素。唯一的區(qū)別在于最后一個(gè)元素指向下一個(gè)元素的指針(tail.next)不是undefine，而是第一個(gè)元素（head）。接下來(lái)來(lái)看一...
摘要：鏈表鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或者刪除元素的時(shí)候不需要移動(dòng)其他元素。 鏈表 鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)元素由一個(gè)存儲(chǔ)元素本事的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。相對(duì)于傳統(tǒng)的數(shù)組，鏈表的一個(gè)好處在于，添加或者刪除元素的時(shí)候不需要移動(dòng)其他元素。...
閱讀 2418·2023-04-26 02:14
閱讀 2991·2021-09-30 09:46
閱讀 2199·2021-09-24 09:48
閱讀 1095·2021-09-24 09:47
閱讀 3317·2019-08-30 15:44
閱讀 1940·2019-08-30 15:44
閱讀 3350·2019-08-30 14:18
閱讀 2032·2019-08-30 12:58
