01-线性数据结构之数组
线性数据结构：也叫一维数据结构，线性的数据结构强调存储和顺序，常用的有数组和链表两种线性数据结构。
特性
存储在物理空间上是连续的；数组定长，底层的数组长度是不可变的；数组的变量，指向了数组第一个元素的位置；
优点
查询性能好
缺点
因为数组存储的空间必须得是连续的，所以如果数组比较大，当系统的空间碎片较多的时候，容易存不下；因为数组的长度是固定的，所以数组的内容难以被添加和删除；
补充
数组 a = [1, 2, 3, 4, 5, 6], a[1], a[2], a[3]中方括号表示存储地址的偏移。操作系统的小知识：通过偏移查询数据性能最好。
02-线性数据结构之链表
使用javascript创建一个链表
function ListNode (value
, next
= null) {
this.value
= value
;
this.next
= next
;
};
const d
= new Node(4);
const c
= new Node(3, d
);
const b
= new Node(2, c
);
const a
= new Node(1, b
);
特性
空间上是不是连续的；每存放一个值，都要多开销一个引用空间；
优点
只有内存足够大，就能存的下，不用担心空间碎片的问题；链表的添加和删除非常容易；
缺点
查询速度慢（指查询某个位置）链表的每一个节点都需要创建一个指向next的引用，浪费了一些空间。解决方法：当节点内数据越多的时候，这部分多开销的内存响应越小。
补充
如果传递一个链表，必须传递链表的根节点。每一个节点，都认为自己是根节点。
03-线性数据结构的遍历
03-线性数据结构的遍历
数组
循环遍历
const arr
= [1, 2, 3, 4, 5, 6];
function ArrTraverse(arr
) {
if (arr
== null) return;
for (let i
= 0; i
< arr
.length
; i
++) {
console
.log(arr
[i
]);
}
}
ArrTraverse(arr
);
递归遍历（重要）
function ArrTraverse1(arr
, i
) {
if (arr
[i
] == null) return;
console
.log(arr
[i
]);
ArrTraverse1(arr
, i
+ 1);
}
注： 递归的思路是先找递归的出口
链表
循环遍历
function linkTraverse(root
) {
let temp
= root
;
while (true) {
if (temp
!== null) {
console
.log(temp
.value
);
} else {
break;
}
temp
= temp
.next
;
}
}
linkTraverse(a
);
递归遍历（重要）
function linkTraverse1 (root
) {
if (root
== null ) return;
console
.log(root
.value
);
linkTraverse1(root
.next
);
}
04-链表的逆置
function linkNizhi(root
) {
if (root
.next
.next
=== null) {
root
.next
.next
= root
;
return root
.next
;
} else {
const result
= linkNizhi(root
.next
);
root
.next
.next
= root
;
root
.next
= null;
return result
;
}
}
05-排序算法
https://blog.csdn.net/weixin_42755677/article/details/91479533
06-栈和队列
栈
function Stack () {
this.arr
= [];
this.push = function (value
) {
this.arr
.push(value
)
};
this.pop = function () {
return this.arr
.pop();
}
}
队列
function Queue () {
this.arr
= [];
this.push = function(value
) {
this.arr
.push(value
);
};
this.pop = function () {
return this.arr
.shift();
}
}
07-双向链表
function listNode(value
) {
this.value
= value
;
this.next
= null;
this.pre
= null;
}
08-二维数据结构
二维数据结构（二维数组）
二位拓补结构（图、树）
描述的是一种关系，只看关系，不看大小、距离；
二叉树
https://blog.csdn.net/weixin_42755677/article/details/108906617
