1.链表的每一个节点都是封装性的结构
节点a中存储了数据和引用，而a的引用存储了b的地址，a可以通过引用寻找他下一个的节点。
注意a的next存的是b的地址，a节点中并没有包含b节点
var b = {
data : 2,
next : null
}
var a = {
data : 1,
next : b
}
a节点的next存了b的地址，a.next和b节点指向同一地址。
image.png
image.png
2.链表的特征
1.在空间上的存储是不连续的；
2.每存放一个值，都要多开销一部分引用空间
由于，链表中的节点是通过结构中存储的引用去寻找下一个节点，所以节点与节点之前没有连续存储的必要。
每一节点结构中都包含数据和引用两个部分，所以在一定程度上消耗了存储空间。
3.链表的优点
1.只要空间够大，即使空间碎片较多，也能存的下
2.链表的添加和删除操作非常容易。
因为链表在空间上的存储是连续的，所以不需要给链表分配一块连续的空间，只要空间够到，就能存的下。
链表的添加和删除都是通过节点的引用进行操作，不像数组需要扩容、复制、移动等做一系列的操作。
3.1链表的添加操作
在节点2和节点3之间添加节点5
image.png
1.节点5中的引用指向3
image.png
2.节点2中的引用指向节点5
image.png
3.2链表的删除操作
将节点5从链表中删除
image.png
1.节点2的引用指向节点3
image.png
我想传递一个链表，必须传递链表的根节点，该链表的根节点1->2->3->4，允许其他节点指向链表中的节点，但是以1为根节点的链表中不存在节点5。
注意：
1.想传递一个链表，必须传递链表的根节点
2.链表中的每一个节点都认为自己是根节点，因为，每个节点只存储了下一个节点的引用，没有存储他上一个节点的引用，所以，每个节点都认为自己是根节点，是该链表的起始。
4.链表的缺点
1.查询速度慢；
2.链表中的每个节点都要分配一部分空间存储下一个节点的引用，浪费一些空间。
链表的查询必须从根节点开始，当我们想获取链表中第四个节点中的数据时，必须从第一个节点开始查找至第四个节点，这导致查询速度变慢。
链表中的每个节点都要开销一部分引用空间，但是当该节点中存储的数据越多，分配的引用空间对空间的使用率就影响的越小。就像火锅底料都是70元，但是聚的人越多，人均的火锅底料费就越少。所以在这种情况下浪费空间的缺点可以忽略。
5.代码操作
如何在代码中创建链表
//创建链表的构造函数
function Node(value) {
this.value = value; //数据
this.next = next //引用
}
//给每个节点添加数据
var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);
这时，仅创建出4个单独的节点，还需要通过引用将4个节点连成链表
a.next = b;
b.next = c;
c.next = d;
d.next = null;
验证是否组成链表：
console.log('a:' + a.value); //a的数据
console.log('b:' + a.next.value); //b的数据
console.log('c:' + a.next.next.value) //c的数据
console.log('d:' + a.next.next.next.value) //d的数据
image.png
当然，上述方法虽然可以创建链表，但是代码过于冗余，后续会封装创建链表的函数。
总结链表和一维数组：
链表和一维数组的优缺点是互补的
1.一维数组存储连续，所以存储时受空间碎片的影响，链表的在空间上存储不连续，所以不受空间碎片的影响；
2.一维数组的长度固定，不宜使用添加和删除的操作，
（当添加的数据超过数据的长度时，就需要进行数组扩容，数组扩容的过程又需要分配空间和复制数据。当需要删除数组中的某一个数据时，需要将该位的数据删除，再将后面的数据往前移，再删除最后一位剩余的空间。）
链表的添加和删除操作很容易，靠节点中的引用进行
3.一维数组查询速度快，通过偏移地址查询数据，查询链表中的数据必须从根节点开始，所以查询速度慢
4.链表中的每个节点都要分配一部分引用空间，浪费空间
网友评论