线性结构是数据结构中的一种分类，用于表示一系列的元素形成的有序集合。

常见的线性结构包括：数组、链表、栈、队列

数组

特别注意：这里所说的数组是数据结构中的数组，和JS中的数组不一样

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

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

2019-11-21-15-06-05.png
根据数组的基本特征，我们可以推导出数组具有以下特点：

  1. 通过下标寻找对应的元素效率极高，因此遍历速度快
  2. 无法添加和删除数据，虽然可以通过某种算法完成类似操作，但会增加额外的内存开销或时间开销
  3. 如果数组需要的空间很大，可能一时无法找到足够大的连续内存

JS中的数组

在ES6之前，JS没有真正意义的数组，所谓的Array，实际上底层实现是链表。

ES6之后，出现真正的数组（类型化数组），但是由于只能存储数字，因此功能有限

目前来讲，JS语言只具备不完善的数组（类型化数组）

链表

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

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

2019-11-21-15-19-23.png
根据链表的基本特征，我们可以推导出它具有以下特点：

  1. 长度是可变的，随时可以增加和删除元素
  2. 插入和删除元素的效率极高
  3. 由于要存储下一个元素的地址，会增加额外的内存开销
  4. 通过下标查询链表中的某个节点，效率很低，因此链表的下标遍历效率低

手动用代码实现链表

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

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

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

  1. 遍历打印
  2. 获取链表的长度
  3. 通过下标获取链表中的某个数据
  4. 通过下标设置链表中的某个数据
  5. 在链表某一个节点之后加入一个新节点
  6. 在链表末尾加入一个新节点
  7. 删除一个链表节点
  8. 链表倒序 ```javascript /**
    • 构造函数，表示链表的一个节点 */ function Node(value) { this.value = value; //节点的数据 this.next = null; //下一个节点的地址 }

/**

  • 遍历一个链表，打印每个节点的数据

  • @param root 链表的根节点 */ function print(root) { // var node = root; // while (node) { // //如果node有值，打印 // console.log(node.value); // node = node.next; // }

    // 分治法 if (root) {

    1.  console.log(root.value); //打印自己
    2.  print(root.next);

    } }

/**

  • 计算链表的长度
  • @param {} root / function count(root) { if (!root) return 0; //链表没有节点 return 1 + count(root.next); //1表示根节点占用一个数量 }

/**

  • 得到链表某个下标的数据
  • @param {*} root
  • @param {} index / function getNode(root, index) { /**
    • 判断某个节点是否是我要查找的节点
    • @param {*} node 表示某个节点
    • @param {} i 该节点是第几个节点 / function _getValue(node, i) { if (!node) return null; if (i === index) return node; return _getValue(node.next, i + 1); } return _getValue(root, 0); }

/**

  • 设置链表某个位置的数据 */ function setValue(root, index, value) { function _setValue(node, i) {
     if (!node) return;
 if (i === index) {
     node.value = value
 }
 else {
     _setValue(node.next, i + 1);
 }
    } _setValue(root, 0); }

/**

  • 在某个链表节点之后加入一个新节点
  • @param node 在哪个节点之后加入

  • @param newValue 新节点的数据 */ function insertAfter(node, newValue) { var newNode = new Node(newValue); //构建新节点

    node.next = newNode; newNode.next = node.next; }

/**

  • 在链表的末尾加入新节点 */ function push(root, newValue) { //判断root是不是最后一个节点 if (!root.next) {
     //最后一个节点
 var newNode = new Node(newValue);
 root.next = newNode;
    } else {
     push(root.next, newValue); //自己不是最后一个，看下一个
    } }

/**

  • 根据给定的链表，和 给定的要删除的值，删除对应节点
  • @param {*} root
  • @param {} nodeValue / function removeNode(root, nodeValue) { if (!root || !root.next) return; //无法删除的情况 if (root.next.value === nodeValue) {
     //下一个节点就是要找的节点
 root.next = root.next.next;
    } else {
     //下一个节点还不是
 removeNode(root.next, nodeValue);
    } }

/**

  • 给定一个链表，返回一个倒序后的根节点
  • @param {} root / function reverse(root) { if (!root || !root.next) return root; if (!root.next.next) {
     var temp = root.next; //保存返回的节点
 //有两个节点的链表
 root.next.next = root;
 root.next = null;
 return temp;
    } else {
     var temp = reverse(root.next); //后续节点倒序
 root.next.next = root;
 root.next = null;
 return temp;
    } }

var a = new Node(“a”); var b = new Node(“b”); var c = new Node(“c”);

a.next = b; b.next = c;

// insertAfter(b, “d”);

var temp = reverse(a);

print(temp); ```