前端必会算法-线性数据结构

最近想着开始看算法相关的东西准备根据前端来进行一个合集学习

本内容是已前端开发的角度去学习的哦，欢迎提问相互学习

数据结构与算法有什么关系

• 可以容纳数据的结构被称为数据结构

• 算法是用来对数据结构进行处理的方法

• 数据结构是静态的、算法是动态的(用来操作数据结构的)

线性数据结构

一维数据结构：（线性数据结构）

线性的数据结构强调的是存储与顺序

数组

• 数组有一个非常大的特性是：数组定长 ，数字的长度是不可变的

• JS 里面虽然没定长，但是JS引擎当存不下了会自动扩容，过程中会复制之前的内容放大更大的内存空间去存储，JS引擎会找操作系统去分配，这里涉及到操作系统的知识推荐一个学习路径参考

数组特性

1. 存储在物理空间上是连续的

2. 底层数组长度是不可变

3. 数组的变量，指向了数组的第一个元素在内存中的位置比如a[0]，索引代表存储地址的偏移，通过索引偏移查询数据性能号

数组的优点

1. 查询性能好(根据便与查询)，可以指定查询某个位置

数据缺点

1. 因为数组空间必须是连续的，所以如果数组比较大，当系统内存空间碎片较多的时候，容易存不下(所以尽量避免数组较大)

2. 因为数组的长度是固定的，所以数组的内容难以被添加和删除 （删除某一个位置，后续的数据会前移）

Javascript中的简单数组

var a = [1,2,3,4,5];
// 推荐 初始给定长度性能更高
var arr = new Array(10);

链表

链表也是线性的数据结构

数组像是棍子连续，链表是像是节点一样一个指向下一个

实际存储

a对象的值为1，指向的下一个对象b，然后存了b的地址，b的值为2同时也会存入下一个指向地址

代码示例

// 创建链表的时候要定义链表的结构
function Node(value) {
    this.value = value;
    this.next = null;
}

var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);

a.next = b;
b.next = c;
c.next = d;
d.next = null;

console.log(a.value); // 1
console.log(a.next.value); // 2
console.log(a.next.next.value); // 3
console.log(a.next.next.next.value); // 4

链表的特点

1. 空间上不是连续的

2. 每存放一个值，都要多开销一个引用空间

链表的优点

1. 只要内容够大，就能存的下，不用担心空间碎片的问题

2. 链表的添加和删除非常容易

链表的缺点

1. 查询速度慢（指查询某个位置）

2. 链表每一个节点都需要创建一个指向next的引用，浪费了一些空间。（但是当节点内数据越多的时候，开销的引用问题相对来说更少）

链表的关键需要注意！！！

想要传递一个链表，必须要传递链表的根节点

每一个节点，都认为自己是根节点，因为对于它自己来说，每个节点是不知道谁指向自己的