什么是链表
链表是一个集合，是 C 或 C++中的概念。和数组有什么区别呢？
链表每个元素有两部分组成，第一部分是存储的值，第二部分是记录了下一个元素的位置信息。在 C 中即使下一个元素的指针，其实就通过第二个属性能直接拿到下一个元素的值。
一个元素通过他的next就知道下一个值是什么。就像一个链子，上一个元素连着下一个元素。
向链表中插入一个值，不需要把后面的每个元素往后移动位置。
- 只需要把修改插入位置前一个元素的 next 属性指向插入的值；
- 插入的值的 next 只插入之后的那个元素即可。
因为在 JavaScript 中不能像 C 一样那样直接操作指针，所以现在用数组模拟一个链表。
javascript 版本的链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| //比如有一个集合
let left = [2, 3, 4, 5, 8, 9];
//用另一个集合对应位置的值来记录下一个元素的索引。每个值存储的是需要获取值的索引，如果没有对应的则存-1；
//这个集合的奥妙在于，它的**索引**和**值**是能串联起来的“一条绳”,索引和值前后衔接。
// [1, 2, 3, 4, 5, -1]
// 0 1 2 3 4 5
let right = [1, 2, 3, 4, 5, -1];
//一个要插入的值
let middle = 6;
let len = left.length;
left.push(middle);
let t = 0;
while (t != -1) {
if (left[right[t]] > middle) {
right[len] = right[t];
right[t] = len;
break;
}
t = right[t];
}
console.log("输出结果：");
console.log(left);
console.log(right);
t = 0;
while (t != -1) {
console.log(left[t]);
//这就体现出了索引和值前后衔接的关系了。注意right的索引用的也是t
t = right[t];
}
|
结果
分析
原始：
1
2
| [2, 3, 4, 5, 8, 9];
[1, 2, 3, 4, 5, -1]
|
插入后：
所谓的插入是保证输出的顺序像插入的效果。
1
2
| [2, 3, 4, 5, 8, 9, 6];
[1, 2, 3, 6, 5, -1, 4]
|
