这篇文章上次修改于 308 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

线性结构-数组与链表(单链表)

线性结构是数据结构分类的一种,它表示一系列数据元素形成的有序集合

数组

数据结构中的数组与JS中的数组不一样,下面说的数组是数据结构的数组

数组是一整块连续的内存空间,它由固定数量的元素组成,数组具有以下基本特征:

  1. 整个数组占用的内存空间是连续的
  2. 数组中元素的数量是固定的(不可增加也不可减少),创建数组时就必须指定其长度
  3. 每个元素占用的内存大小是完全一样的

特点

1、通过下标寻找对应的数据元素效率及高,一次遍历速度快。

创建一个数组:arr

长度为7,每一个我数据单元占用内存空间为8字节

寻找arr[3]:arr地址+2*8字节

CPU执行加运算快到极致,数组下标查找用的就是地址长度加运算查找,所以遍历速度快

2、无法添加和删除数据,虽然可以通过某种算法完成类似操作,但会增加额外的内存开销或时间开销

向内存申请一个数组存储空间后,这个数组的长度的不可变得,所以要进行添加和删除操作需要新建一个指定长度的数组

添加

首要创建一个length+1的数组,然后将数组的数据元素按顺序复制到新数组,最后将添加的数据存储在新数组中。

删除

首要创建一个length-1的数组,然后将数组的需要的数据元素按顺序复制到新数组

3、因为数组的存储是连续的,所以当数组需要的空间很大,可能一时无法找到足够大的连续内存

JS中的数组

在ES6之前,JS没有真正意义的数组,所谓的Array,实际上底层实现是链表。ES6之后,出现真正的数组(类型化数组),但是由于只能存储数字,因此功能有限目前来讲,JS语言只具备不完善的数组(类型化数组)

类型化数组

是真正的数据结构的数组,但目前只能存储数字。常用的数值类型像Int8Uint32Float64 等等

就拿Int8Array举例

// 表示申请一个长度为5且每个数据元素都是8字节的整型数字
var arr = new Int8Array(5);
/*
   需要注意的是该arr数组中没有push、splice、unshift等方法
*/

链表(单向链表)

为弥补数组的缺陷而出现的一种数据结构,它具有以下基本特征:

  1. 每个元素除了存储数据,需要有额外的内存存储一个引用(地址),来指向下一个元素
  2. 每个元素占用的内存空间并不要求是连续的
  3. 往往使用链表的第一个节点(根节点)来代表整个链表

特点:

  1. 长度是可变的,随时可以增加和删除元素
  2. 插入和删除元素的效率极高

只需改变地址指向就够了

  1. 由于要存储下一个元素的地址,会增加额外的内存开销(新加了地址存储空间)
  2. 通过下标查询链表中的某个节点,效率很低,因此链表的下标遍历效率低

下标查询只能从根节点一个一个向下找。就拿上图说,只能从0找到1,1再找到3,0不能直接找到3,那链表长度要有成千上万个就非常慢了。所以js中尽量不要使用for循环遍历数组

那js数组怎么实现查询的呢?

js采用迭代查询(就是查询一个数据返回一个数据,然后顺着返回的数据地址指向继续向下找,for循环每次循环都会从头开始找,所以效率低)

js常见的迭代查询的方法:for....of,forEach,map,filter等等;

手动用代码实现链表

实际上,很多语言本身已经实现了链表(如JS中的数组,底层就是用链表实现的),但链表作为一种基础的数据结构,通过手写代码实现链表,不仅可以锻炼程序思维和代码转换能力,对于后序的复杂数据结构的学习也是非常有帮助的。

因此,手写链表是学习数据结构和算法的一门基本功

手写一个链表结构,并完成一些链表的相关函数,要实现以下功能:

先简单创建一个链表,很简单

 // 创建新链表节点
function CreateNode(val) {
  this.value = val;
  this.nextNode = null;
}

var a = new CreateNode(1);
var b = new CreateNode(2);
var c = new CreateNode(3);

// 对象链接形成链表结构
a.nextNode = b;
b.nextNode = c;

1、遍历打印

function log(rootNode) {
    //var node = rootNode;
    //while (node) {
    //    console.log(node.value);
    //    node = node.next;
    //}
    
    // 分治法(相当于递归):将一个规模为N的问题,分解成K个规模较小的子问题,这些子问题相互独立且月原问题性质相同。
    if(!rootNode) return;
    console.log(rootNode.value);
    log(rootNode.nextNode); 
}
log(a);
/*输出:
      1
      2
      3
*/

2、获取链表的长度

function getLen(rootNode) {
  if(!rootNode) return 0; // 该节点为空,返回0
  return 1 + getLen(rootNode.nextNode);
}
console.log(getLen(a)); // ==> 3

3、通过下标获取链表中的某个数据

function getIndexValue(rootNode, index) {
  function getValue(node, i) {
    if(!node) return null;
    if(index === i) return node.value;
    return getValue(node.nextNode, i + 1);
  }
  getValue(rootNode, 0);
}

console.log(getIndexValue(a, 1));// ==> 2

4、通过下标设置链表中的某个数据

function setIndexValue(rootNode, index, val) {
  function setValue(node, i) {
    if(!node) return null;
    if(index === i) return node.value = val;
    return setValue(node.nextNode, i + 1);
  }
  setValue(rootNode, 0)
}
setIndexValue(a, 1, 5);
log(a); 
/*
    1
    5
    3
*/

5、在链表某一个节点之后加入一个新节点

假如要插入数据4,只需要改变数据2的地址指向数据4的存储地址,然后数据4的地址指向数据3的存储地址

function insertAfterNode( node, val) {
  var new_node = new CreateNode(val);
  new_node.nextNode = node.nextNode;
  node.nextNode = new_node;
}
insertAfterNode(b, 8);
log(a)
/*
    1
    2
    8
    3
*/

6、在链表末尾加入一个新节点

function insertEndNode(rootNode, val) {
  if(!rootNode.nextNode) {
    var new_node = new CreateNode(val);
    return rootNode.nextNode = new_node;
  }
  insertEndNode(rootNode.nextNode, val);
}
insertEndNode(a, 8);
log(a);
/*
    1
    2
    3
    8
*/

7、删除一个链表节点

假如要插入数据3,只需要改变要删除节点的上一个节点(数据2)的地址指向要删除节点的下一个节点(数据4

function deleteNode(rootNode, val) {
  if(!rootNode || !rootNode.nextNode) return;
  if(rootNode.nextNode.value === val) {
    return rootNode.nextNode = rootNode.nextNode.nextNode;
  }
  deleteNode(rootNode.nextNode, 2);
}
deleteNode(a, 2);
log(a);
/*
    1
    3
*/

8、链表倒序(三种情况)

  • 链表为空或只有一个数据,不需要倒序
  • 链表长度为二,将第二个数据节点地址指向第一个数据节点,第一个数据节点指向null,最后返回第二个节点
  • 链表长度大于二,分治法,头结点和剩余节点看做两个节点,这样倒序按第二种情况来就行
   function reverse (rootNode) {
     if(!rootNode || !rootNode.nextNode) return rootNode;
     if(!rootNode.nextNode.nextNode) {
       var temp = rootNode.nextNode;
       rootNode.nextNode.nextNode = rootNode;
       rootNode.nextNode = null;
       return temp;
     }
     var temp = reverse(rootNode.nextNode);
     rootNode.nextNode.nextNode = rootNode;
     rootNode.nextNode = null;
     return temp;
   }
   console.log(reverse(a));
   /*
       CreateNode {value: 3, nextNode: CreateNode}
       nextNode: CreateNode
           nextNode: CreateNode
               nextNode: null
               value: 1
               __proto__: Object
           value: 2
           __proto__: Object
       value: 3
       __proto__: Object
   */