前言
1、什么是鏈表警检？
官方解釋:
鏈表是一種非連續(xù)孙援、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn),常見的鏈表有: 單向鏈表扇雕、雙向鏈表拓售、循環(huán)鏈表、反向鏈表
通俗解釋：
鏈表其實(shí)就是一個(gè)俄羅斯套娃,一層套著一層镶奉，拿掉第一層可以找到第二層,....依次類推
0.png
2础淤、數(shù)組特點(diǎn)
- 數(shù)組是順序存儲(chǔ)結(jié)構(gòu)
- 數(shù)組需要預(yù)留空間，在使用前要先申請(qǐng)占內(nèi)存的大小哨苛，可能會(huì)浪費(fèi)內(nèi)存空間鸽凶，比如看電影時(shí)，為了保證10個(gè)人能坐在一起建峭，必須提前訂好10個(gè)連續(xù)的位置玻侥。這樣的好處就是能保證10個(gè)人可以在一起。但是這樣的缺點(diǎn)是迹缀，如果來的人不夠10個(gè)使碾，那么剩下的位置就浪費(fèi)了。如果臨時(shí)有多來了個(gè)人祝懂，那么10個(gè)就不夠用了
- 插入數(shù)據(jù)和刪除數(shù)據(jù)效率低，插入數(shù)據(jù)時(shí)拘鞋，這個(gè)位置后面的數(shù)據(jù)在內(nèi)存中都要向后移砚蓬。刪除數(shù)據(jù)時(shí)，這個(gè)數(shù)據(jù)后面的數(shù)據(jù)都要往前移動(dòng) 盆色，比如原來去了5個(gè)人灰蛙，然后后來又去了一個(gè)人要坐在第三個(gè)位置上，那么第三個(gè)到第五個(gè)都要往后移動(dòng)一個(gè)位子隔躲，將第三個(gè)位置留給新來的人摩梧。 當(dāng)這個(gè)人走了的時(shí)候，因?yàn)樗麄円B在一起的宣旱，所以他后面幾個(gè)人要往前移動(dòng)一個(gè)位置仅父，把這個(gè)空位補(bǔ)上
- 隨機(jī)讀取效率很高。因?yàn)閿?shù)組是連續(xù)的，知道每一個(gè)數(shù)據(jù)的內(nèi)存地址笙纤，可以直接找到給地址的數(shù)據(jù)
3耗溜、鏈表特點(diǎn)
- 在內(nèi)存中可以存在任何地方，不要求連續(xù)
- 每一個(gè)數(shù)據(jù)都保存了下一個(gè)數(shù)據(jù)的內(nèi)存地址省容，通過這個(gè)地址找到下一個(gè)數(shù)據(jù)
- 鏈表的插入刪除元素相對(duì)數(shù)組較為簡(jiǎn)單抖拴，不需要移動(dòng)元素，且較為容易實(shí)現(xiàn)長(zhǎng)度擴(kuò)充
- 查找數(shù)據(jù)時(shí)效率低腥椒，因?yàn)椴痪哂须S機(jī)訪問性阿宅，所以訪問某個(gè)位置的數(shù)據(jù)都要從第一個(gè)數(shù)據(jù)開始訪問，然后根據(jù)第一個(gè)數(shù)據(jù)保存的下一個(gè)數(shù)據(jù)的地址找到第二個(gè)數(shù)據(jù)笼蛛，以此類推家夺。 要找到第三個(gè)人，必須從第一個(gè)人開始問起
4伐弹、總結(jié)：
數(shù)組：
1拉馋、隨機(jī)訪問性強(qiáng)
2、查找速度快
鏈表：
1惨好、插入刪除速度快
2煌茴、內(nèi)存利用率高
3、拓展很靈活
一日川、單向鏈表
1.png
特點(diǎn):
- 用一組任意的內(nèi)存空間去存儲(chǔ)數(shù)據(jù)元素（這里的內(nèi)存空間可以是連續(xù)的仔役，也可以是不連續(xù)的）
- 每個(gè)節(jié)點(diǎn)(node)都由數(shù)據(jù)本身和一個(gè)指向后續(xù)節(jié)點(diǎn)的指針組成
- 整個(gè)鏈表的存取必須從頭指針開始打却，頭指針指向第一個(gè)節(jié)點(diǎn)
- 最后一個(gè)節(jié)點(diǎn)的指針指向空（NULL）
鏈表中的主要操作:
- 創(chuàng)建節(jié)點(diǎn)
- 插入節(jié)點(diǎn)
- 查找節(jié)點(diǎn)
- 刪除節(jié)點(diǎn)
1、創(chuàng)建節(jié)點(diǎn)
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
2、尾部插入節(jié)點(diǎn)
尾部插入節(jié)點(diǎn)我們只需要考慮2點(diǎn)
- 鏈表中head是否存在如果不存在代表插入的節(jié)點(diǎn)是第一個(gè)
- 如果存在則則找最后一個(gè)節(jié)點(diǎn)讶请，將最后一個(gè)節(jié)點(diǎn)的next指向插入的節(jié)點(diǎn)
// 尾部插入 this.tail的作用就是用來保存最后一個(gè)節(jié)點(diǎn)
append(data) {
let listNode = new ListNode(data);
if (this.head) {
this.tail.next = listNode;
this.tail = listNode;
} else {
this.head = listNode;
this.tail = listNode;
}
this.length++;
return true;
}
3、獲取節(jié)點(diǎn)
此方法很重要善炫，因?yàn)閯h除和添加都需要用到此方法.另外鏈表的缺陷也在此方法中體現(xiàn)了出來
- 如果index等于0則直接返回head
- 如果index不等于0則需要通過while循環(huán)找到對(duì)應(yīng)的節(jié)點(diǎn)
getNode(index) {
if (index < 0 || index > this.length) {
return false;
} else {
if (index === 0) {
return this.head;
} else {
let current_index = 0;
let current_node = this.head;
while (current_index < index) {
current_index += 1;
current_node = current_node.next;
}
return current_node;
}
}
}
4勒叠、插入節(jié)點(diǎn)
- 如果index的值等于this.length的值則代表需要插入到最后，直接調(diào)用尾部插入即可
- 如果index等于0則需要將head節(jié)點(diǎn)賦值給插入節(jié)點(diǎn)的next职抡，插入節(jié)點(diǎn)賦值給head
- 如果index不等于0則需要獲取到插入位置的
prevNode和nextNode,然后將插入節(jié)點(diǎn)的next等于nextNode葬燎，prevNode的next等于插入節(jié)點(diǎn)
2.png
insert(index, data) {
if (index < 0 || index > this.length) {
return fase;
} else if (index === this.length) {
this.append(data);
} else {
let listNode = new ListNode(data);
if (index === 0) {
listNode.next = this.head;
this.head = listNode;
} else {
const nextNode = this.getNode(index);
const prevNode = this.getNode(index - 1);
listNode.next = nextNode;
prevNode.next = listNode;
}
this.length += 1;
return true;
}
}
5、刪除節(jié)點(diǎn)
- 如果index等于0則將head值改為head.next
- 如果index不等于0則需要獲取到刪除節(jié)點(diǎn)的prevNode和nextNode缚甩，將nextNode賦值給prevNode的next
3.png
remove(index) {
if (index < 0 || index > this.length) {
return false;
} else if (index === 0) {
this.head = this.head.next;
this.length -= 1;
} else {
const nextNode = this.getNode(index).next;
const prevNode = this.getNode(index - 1);
prevNode.next = nextNode;
this.length -= 1;
}
}
6谱净、獲取節(jié)點(diǎn)數(shù)據(jù)
同理獲取節(jié)點(diǎn)
get(index) {
if (index < 0 || index > this.length) {
return false;
} else {
if (index === 0) {
return this.head.data;
} else {
let current_index = 0;
let current_node = this.head;
while (current_index < index) {
current_index += 1;
current_node = current_node.next;
}
return current_node.data;
}
}
}
7、完整版代碼
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
class List {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
/*
尾部插入
*/
append(data) {
let listNode = new ListNode(data);
if (this.head) {
this.tail.next = listNode;
this.tail = listNode;
} else {
this.head = listNode;
this.tail = listNode;
}
this.length++;
return true;
}
/*
獲取節(jié)點(diǎn)
*/
getNode(index) {
if (index < 0 || index > this.length) {
return false;
} else {
if (index === 0) {
return this.head;
} else {
let current_index = 0;
let current_node = this.head;
while (current_index < index) {
current_index += 1;
current_node = current_node.next;
}
return current_node;
}
}
}
/*
插入
*/
insert(index, data) {
if (index < 0 || index > this.length) {
return fase;
} else if (index === this.length) {
this.append(data);
} else {
let listNode = new ListNode(data);
if (index === 0) {
listNode.next = this.head;
this.head = listNode;
} else {
const nextNode = this.getNode(index);
const prevNode = this.getNode(index - 1);
listNode.next = nextNode;
prevInsertNode.next = listNode;
}
this.length += 1;
return true;
}
}
/*
移除
*/
remove(index) {
if (index < 0 || index > this.length) {
return false;
} else if (index === 0) {
this.head = this.head.next;
this.length -= 1;
} else {
const nextNode = this.getNode(index).next;
const prevNode = this.getNode(index - 1);
prevNode.next = nextNode;
this.length -= 1;
}
}
/*
獲取節(jié)點(diǎn)數(shù)據(jù)
*/
get(index) {
if (index < 0 || index > this.length) {
return false;
} else {
if (index === 0) {
return this.head.data;
} else {
let current_index = 0;
let current_node = this.head;
while (current_index < index) {
current_index += 1;
current_node = current_node.next;
}
return current_node.data;
}
}
}
}
二擅威、雙向鏈表
雙向鏈表其實(shí)就是多了一個(gè)指向上一個(gè)節(jié)點(diǎn)的指針壕探，不管刪除還是添加時(shí)刻記得改變prev的指向即可.其他邏輯和單向鏈表一致
1、完整代碼
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class List {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
/*
尾部插入
*/
append(data) {
let listNode = new ListNode(data);
if (this.head) {
this.tail.next = listNode;
listNode.prev = this.tail;
this.tail = listNode;
} else {
this.head = listNode;
this.tail = listNode;
}
this.length++;
return true;
}
/*
獲取節(jié)點(diǎn)
*/
getNode(index) {
if (index < 0 || index > this.length) {
return false;
} else {
if (index === 0) {
return this.head;
} else {
let current_index = 0;
let current_node = this.head;
while (current_index < index) {
current_index += 1;
current_node = current_node.next;
}
return current_node;
}
}
}
/*
插入
*/
insert(index, data) {
if (index < 0 || index > this.length) {
return fase;
} else if (index === this.length) {
this.append(data);
} else {
let listNode = new ListNode(data);
if (index === 0) {
listNode.next = this.head;
this.head.prev = listNode;
this.head = listNode;
} else {
const nextNode = this.getNode(index);
const prevNode = this.getNode(index - 1);
listNode.next = nextNode;
listNode.prev = prevNode;
nextNode.prev = listNode;
prevNode.next = listNode;
}
this.length += 1;
return true;
}
}
/*
移除
*/
remove(index) {
if (index < 0 || index > this.length) {
return false;
} else if (index === 0) {
this.head.next.prev = null;
this.head = this.head.next;
this.length -= 1;
} else {
const nextNode = this.getNode(index).next;
const prevNode = this.getNode(index - 1);
prevNode.next = nextNode;
nextNode.prev = prevNode;
this.length -= 1;
}
}
/*
獲取節(jié)點(diǎn)數(shù)據(jù)
*/
get(index) {
if (index < 0 || index > this.length) {
return false;
} else {
if (index === 0) {
return this.head.data;
} else {
let current_index = 0;
let current_node = this.head;
while (current_index < index) {
current_index += 1;
current_node = current_node.next;
}
return current_node.data;
}
}
}
}
三郊丛、反轉(zhuǎn)鏈表
什么是反轉(zhuǎn)鏈表? 假設(shè)套娃的順序是1<2<3<4,那么反轉(zhuǎn)也就是4<3<2<1李请。實(shí)現(xiàn)反轉(zhuǎn)的方法有2種
- 迭代法：就是需要定義三個(gè)節(jié)點(diǎn)指針瞧筛，一個(gè)指向當(dāng)前節(jié)點(diǎn)，一個(gè)指向前面一個(gè)節(jié)點(diǎn)捻艳，一個(gè)指向后面一個(gè)節(jié)點(diǎn)驾窟，反轉(zhuǎn)就是說，當(dāng)前節(jié)點(diǎn)的next指針指向前面一個(gè)節(jié)點(diǎn)
- 遞歸：遞歸方法就是你不會(huì)反轉(zhuǎn)當(dāng)前鏈表认轨，讓遞歸方法先幫你反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始的單鏈表绅络，把反轉(zhuǎn)后的頭節(jié)點(diǎn)返回。你再將當(dāng)前頭節(jié)點(diǎn)連接到返回頭節(jié)點(diǎn)的尾部
4.png
一嘁字、迭代法
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = null;
// 核心
function reverse(node) {
if (!node) {
return null;
}
let curr_node = node;
let pre_node = null;
while (curr_node) {
// 獲取下一個(gè)節(jié)點(diǎn),用來更改current_node的值,遍歷所有的節(jié)點(diǎn)
let next_node = curr_node.next;
// 將當(dāng)前節(jié)點(diǎn)的next指向上一次的current_node,如果第一次遍歷則指向null
curr_node.next = pre_node;
// 保存當(dāng)前current_node的節(jié)點(diǎn)
pre_node = curr_node;
// 進(jìn)行下一次遍歷
curr_node = next_node;
}
return pre_node;
}
let node = reverse(node1);
console.log(node);
5.png
二恩急、遞歸
function reverse_digui(node) {
if (!node) {
return null;
}
if (node.next == null) {
return node;
}
let new_head = reverse_digui(node.next);
node.next.next = node;
node.next = null;
return new_head;
}
