一惊豺、鏈表數(shù)據(jù)結(jié)構(gòu)
要存儲多個元素，數(shù)組（或列表）可能是最常用的數(shù)據(jù)結(jié)構(gòu)禽作。然而這種數(shù)據(jù)結(jié)構(gòu)有一個缺點(diǎn)尸昧，數(shù)字的大小是固定的，從數(shù)組的起點(diǎn)或中間插入或移除項(xiàng)的成本很高旷偿，因?yàn)樾枰苿釉亍?br> 鏈表存儲有序的元素集合烹俗，但不用于數(shù)組爆侣，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本身的節(jié)點(diǎn)和一個指向下一個元素的飲用（也稱指針或鏈接）組成衷蜓。下圖展示了一個鏈表的結(jié)構(gòu)
image.png
相對于傳統(tǒng)的數(shù)組累提，鏈表的一個好處在于，添加或移動元素的時候不需要移動其他元素磁浇。然而斋陪，鏈表需要使用指針，因此實(shí)現(xiàn)鏈表時需要額外注意置吓。數(shù)組的一個細(xì)節(jié)是可以直接訪問任何位置的元素无虚，而想要訪問鏈表中間的一個元素，需要從起點(diǎn)（表頭）開始迭代列表直到找到所需的元素衍锚。
舉幾個形象的例子來形容：
- 尋寶游戲：你有一條線索友题，這條線索是指向?qū)ふ蚁乱粭l線索的地點(diǎn)的指針。你順著這條鏈接去下一個地點(diǎn)戴质，得到另一條指向再下一處的線索度宦。得到列表中間的線索的唯一辦法，就是從起點(diǎn)（第一條線索）順著列表尋找
- 火車：一列火車是由一系列車廂組成告匠，每節(jié)車廂相互連接戈抄，你很容易分離一節(jié)車皮，改變它的位置后专，添加或者移除它划鸽，車廂之間的連接就是指針
特點(diǎn)
- 鏈表是多個元素組成的列表
- 元素存儲不連續(xù)，用next指針連接到一起
- JS中沒有鏈表戚哎，但是可以用Object模擬鏈表
二裸诽、創(chuàng)建鏈表
下面我們實(shí)現(xiàn)一個鏈表類，并給他加點(diǎn)方法
class Node { //節(jié)點(diǎn)類
//構(gòu)造函數(shù)
constructor(item) {
this.item = item;
this.next = null;
}
}
class LinkedList { // 鏈表類
//構(gòu)造函數(shù)
constructor() {
this.head = null;
this.length = 0;
}
//新增節(jié)點(diǎn)
append(item) {
let node = new Node(item);
let current; //暫存當(dāng)前位置
if(this.head === null) { // 如果頭結(jié)點(diǎn)為空,當(dāng)前節(jié)點(diǎn)作為頭結(jié)點(diǎn)
this.head = node;
} else {
current = this.head;
while(current.next) { //遍歷找到鏈表尾部
current = current.next;
}
current.next = node; //在鏈表尾部加入新節(jié)點(diǎn)
}
this.length++; //更新鏈表長度
}
//刪除節(jié)點(diǎn),并獲得刪除節(jié)點(diǎn)的值
remove(index) {
if(index > -1 && index < this.length) { //預(yù)防下標(biāo)越界
var current = this.head;//暫存當(dāng)前位置
var previous; //暫存當(dāng)前位置的前一個
var position = 0;
if(index === 0) { //要刪除的是第一個位置型凳，就得改變頭指針指向
this.head = current.next;
} else {
while(position++ < index) { //遍歷直到current處于index位置
previous = current;
current = current.next; //此時current處于index處,previous在index-1處
}
previous.next = current.next; //改變鏈表結(jié)構(gòu),跳過index處
}
this.length--; //更新鏈表長度
return current.[圖片上傳中...(image.png-aecada-1661950439992-0)]
; //返回index處的值
} else {
return null; //下標(biāo)越界返回空
}
}
//插入節(jié)點(diǎn)
insert(index, item) {
if(index > -1 && index <= this.length) {
let node = new Node(item);
let current = this.head;
let previous;
let position = 0;
if(index === 0) {
node.next = current;
this.head = node;
} else {
while(position++ < index) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true; //插入成功
} else {
return false; //插入失敗
}
}
//獲取索引
indexOf(item) {
let current = this.head;
let position = 0;
while(current) {
if(current.item === item) {
return position;
}
position++;
current = current.next;
}
return -1; //未找到索引
}
//將鏈表轉(zhuǎn)換成字符串
toString() {
let current = this.head;
let string = '';
while(current) {
string += current.item + ((current.next ? ',': ''));
current = current.next;
}
return string;
}
//鏈表長度
size() {
return this.length;
}
//判斷鏈表是否為空
isEmpty() {
return this.length === 0;
}
}
這樣我們就實(shí)現(xiàn)了一個鏈表類丈冬，我們也為其添加了很多自定義方法
- 新增節(jié)點(diǎn) append
- 刪除節(jié)點(diǎn) remove
- 插入節(jié)點(diǎn) insert
- 獲取索引 indexOf
- 鏈表轉(zhuǎn)字符串 toString
- 獲取鏈表長度 size
- 判斷鏈表是否為空 isEmpty
未完待續(xù)......
