資訊專欄INFORMATION COLUMN
摘要：鏈表鏈表存儲(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í)候不需要移動(dòng)其他元素。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)(C語(yǔ)言的數(shù)組需要預(yù)先定義長(zhǎng)度)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。
數(shù)組和鏈表的一個(gè)不同在于數(shù)組可以直接訪問(wèn)任何位置的元素，而想要訪問(wèn)鏈表中的一個(gè)元素，需要從起點(diǎn)開(kāi)始迭代列表。
鏈表又包括：?jiǎn)蜗蜴湵?和 雙向鏈表；
雙向鏈表雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個(gè)節(jié)點(diǎn)的鏈接。但在雙向鏈表中，還有指向上一個(gè)節(jié)點(diǎn)的鏈接，是雙向的。
讓我們來(lái)簡(jiǎn)單實(shí)現(xiàn)一個(gè)雙向鏈表類(lèi)，并包含如下功能：
append(element): 添加元素到鏈表尾部
insert(position,element): 向雙向鏈表中某個(gè)位置插入元素
removeAt(position): 移除雙向鏈表中某個(gè)位置的元素
getHead(): 獲取雙向鏈表的頭部
getTail(): 獲取雙向鏈表的尾部
isEmpty(): 檢查雙向鏈表是否為空，為空則返回true
size(): 返回雙向鏈表長(zhǎng)度
代碼如下：
function DoublyLinkedList() {
/**
* 雙向鏈表中節(jié)點(diǎn)的構(gòu)造函數(shù)
*
* @param {any} element 要插入鏈表的元素
*/
var Node = function (element) {
this.element = element;
this.next = null;
this.prev = null;
}
// 雙向鏈表的長(zhǎng)度
var length = 0;
// 雙向鏈表的頭結(jié)點(diǎn)，默認(rèn)為null
var head = null;
// 雙向鏈表的尾結(jié)點(diǎn)，默認(rèn)為null
var tail = null;
/**
* 添加元素到雙向鏈表的尾部
*
* @param {any} element 要插入的元素
*/
this.append = function (element) {
var node = new Node(element),
current = head;
if (head === null) {
head = node
tail = node
} else {
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return true;
}
/**
* 向雙向鏈表中某個(gè)位置插入元素
*
* @param {any} position 要插入的位置
* @param {any} element 要插入的元素
* @returns 插入成功或失敗
*/
this.insert = function (position, element) {
var node = new Node(element),
current = head,
previous,
index = 0;
// 限制邊界
if (position < 0 && position >= length) {
return false;
}
if (position === 0) {
// 在鏈表的頭部插入元素
node.next = head
head.prev = node
head = node
} else if (position === length) {
// 在鏈表的尾部插入元素
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
// 在鏈表的中間插入元素
while (index++ < position) {
previous = current
current = current.next;
}
// 綁定前一個(gè)節(jié)點(diǎn)和插入節(jié)點(diǎn)的關(guān)系
previous.next = node;
node.prev = previous;
// 綁定后一個(gè)節(jié)點(diǎn)和插入節(jié)點(diǎn)的關(guān)系
node.next = current;
current.prev = node;
}
length++;
return true;
}
/**
* 移除雙向鏈表中某個(gè)位置的元素
*
* @param {any} position 要移除元素的位置
* @returns 移除成功，返回移除的元素
*/
this.removeAt = function (position) {
var previous,
current = head,
index = 0;
// 限制邊界
if (position < 0 && position >= length) {
return false;
}
if (position === 0) {
// 移除鏈表的頭部
head = current.next;
head.prev = null;
} else if(position === length - 1) {
// 移除鏈表尾部的元素
current = tail;
tail = current.prev;
tail.next = null;
} else {
// 移除鏈表中間的元素
while (index++ < position) {
previous = current
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
}
this.getHead = function () {
return head.element;
}
this.isEmpty = function () {
return length === 0
}
this.getTail = function () {
return tail.element;
}
this.size = function () {
return length
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/89273.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)與...
摘要：創(chuàng)建雙向鏈表創(chuàng)建節(jié)點(diǎn)繼承添加前繼指針初始化雙向鏈表對(duì)鏈表最后一個(gè)元素進(jìn)行引用插入操作尾插法任意位置添加元素刪除操作刪除特定位置的元素查詢操作查詢?cè)氐奈恢貌樵兾膊吭匦薷牟僮髑蹇针p向鏈表雙向鏈表對(duì)象轉(zhuǎn)為字符串 線性表 （List）：零個(gè)或者多個(gè)數(shù)據(jù)元素的有限序列。線性表是一個(gè)序列，具有一對(duì)一的關(guān)系，而不能具備一對(duì)多的關(guān)系。線性表要求有限性，數(shù)據(jù)類(lèi)型也要相同。本文參考的主要是大話數(shù)據(jù)結(jié)構(gòu)...
摘要：鏈表數(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)看一...
摘要：每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。數(shù)組鏈表隊(duì)列棧等就是線性表結(jié)構(gòu)。非線性表數(shù)據(jù)之間并不是簡(jiǎn)單的前后關(guān)系。不包含任何元素的棧稱為空棧。移除棧頂?shù)脑?，同時(shí)返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言 基礎(chǔ)知識(shí)就像是一座大樓的地基，它決定了我們的技術(shù)高度。 我們應(yīng)該多掌握一些可移值的...
閱讀 1799·2021-11-24 10:18
閱讀 2313·2021-11-18 13:20
閱讀 2405·2021-08-23 09:46
閱讀 1086·2019-08-30 15:56
閱讀 2909·2019-08-30 15:53
閱讀 820·2019-08-30 14:22
閱讀 544·2019-08-29 15:34
閱讀 2597·2019-08-29 12:14
