------------恢复内容开始------------

背景

数组并不总是组织数据的最佳数据结构，原因如下。在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。

在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。

然而，JavaScript 的数组并不存在上述问题，因为使用 split() 方法不需要再访问数组中的其他元素了。

JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言（比如 C++ 和 Java）的数组相比，效率很低。

如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的集合。如下图所示：

数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。然而要标识出链表的起始节点却有点麻烦，许多链表的实现都在链表最前面有一个特殊节点，叫做头节点。如下图所示：

链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。下图演示了如何在 Tue 节点后加入 Fri 节点。

从链表中删除一个元素也很简单。将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了。下图演示了从链表中删除“Fri”节点的过程。

链表节点（Node）类实现

完整代码地址，Node类包含两个属性：

  • el 用来保存节点上的数据
  • next 用来保存指向下一个节点的链接

1. 构造函数

function Node (el) {

    this.el = el;

    this.next = null;

}

链表（Link）类实现

完整代码地址，Link类提供了以下的方法：

  • insert 插入新节点
  • remove 删除节点
  • display 显示链表元素的方法
  • 其他一些辅助方法

1. 构造函数

function Link () {

    this.head = new Node('head');

}

2. find：按节点的值查找节点

Link.prototype.find = function (el) {

    var currNode = this.head;

    while (currNode && currNode.el != el) {

        currNode = currNode.next;

    }

    return currNode;

}
find 方法展示了如何在链表上进行移动。首先，创建一个新节点，并将链表的头节点赋给这个新创建的节点。
然后在链表上进行循环，如果当前节点的 el 属性和我们要找的信息不符，就从当前节点移动到下一个节点。如果查找成功，该方法返回包含该数据的节点；否则，返回 null。
 
3. insert：插入一个节点
Link.prototype.insert = function (newEl, oldEl) {

    var newNode = new Node(newEl);

    var findNode = this.find(oldEl);

    if (findNode) {

        newNode.next = findNode.next;

        findNode.next = newNode;

    } else {

        throw new Error('找不到给定插入的节点');

    }

}

find 方法一旦找到给定的节点，就可以将新节点插入链表了。

4. display：展示链表节点元素

// 展示链表中的元素

Link.prototype.display = function () {

    var currNode = this.head.next;

    while (currNode) {

        console.log(currNode.el);

        currNode = currNode.next;

    }

}

5. findPrev：寻找给定节点的前一个节点

Link.prototype.findPrev = function (el) {

    var currNode = this.head;

    while (currNode.next && currNode.next.el !== el) {

        currNode = currNode.next;

    }

    return currNode;

}

6. remove：删除给定的节点

Link.prototype.remove = function (el) {

    var prevNode = this.findPrev (el);

    if (prevNode.next != null) {

        prevNode.next = prevNode.next.next;

    } else {

        throw new Error('找不到要删除的节点');

    }

}

链表（Link）类测试

var link = new Link();

link.append(1);

link.append(3);

link.display();

console.log('------------');

link.insert(2, 1);

link.display();

console.log('------------');

link.remove(1);

link.display();

运行结果：

1

3

------------

1

2

3

------------

2

3

上面介绍的链表我们称作：单向链表（单链表），其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。下面我们介绍另一种链表：双向链表（双链表）。

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。如下图所示：

双向链表节点（DNode）类实现

完整代码地址，相比于单向链表节点（Node）类，我们只需新增一个 prev 属性，指向之前一个链表节点的引用即可。

function DNode (el) {

    this.el = el;

    this.prev = null;

    this.next = null;

}

双向链表（DLink）类实现

完整代码地址，相比于单链表，双链表的操作会复杂一点。

1. 构造函数

function DLink () {

    this.head = new DNode('head');

}

2. append：向链表结尾添加一个节点

CLink.prototype.append = function (el) {

    var currNode = this.head;

    while (currNode.next != null) {

        currNode = currNode.next;

    }

    var newNode = new Node(el);

    newNode.next = currNode.next;

    currNode.next = newNode;

}

3. find：查找给定的节点

DLink.prototype.find = function (el) {

    var currNode = this.head;

    while (currNode && currNode.el != el) {

        currNode = currNode.next;

    }

    return currNode;

}

4. insert：插入一个节点

DLink.prototype.insert = function (newEl, oldEl) {

    var newNode = new DNode(newEl);

    var currNode = this.find(oldEl);

    if (currNode) {

        newNode.next = currNode.next;

        newNode.prev = currNode;

        currNode.next = newNode;

    } else {

        throw new Error('未找到指定要插入节点位置对应的值！')

    }

}

5. display：顺序展示链表节点

DLink.prototype.display = function () {

    var currNode = this.head.next;

    while (currNode) {

        console.log(currNode.el);

        currNode = currNode.next;

    }

}

6. findLast：查找最后一个节点

DLink.prototype.findLast = function () {

    var currNode = this.head;

    while (currNode.next != null) {

        currNode = currNode.next;

    }

    return currNode;

}

7. dispReverse：逆序展示链表元素

DLink.prototype.dispReverse = function () {

    var currNode = this.head;

    currNode = this.findLast();

    while (currNode.prev != null) {

        console(currNode.el);

        currNode = currNode.prev;

    }

}

8. remove：删除节点

DLink.prototype.remove = function (el) {

    var currNode = this.find(el);

    if (currNode && currNode.next != null) {

        currNode.prev.next = currNode.next;

        currNode.next.prev = currNode.prev;

        currNode.next = null;

        currNode.previous = null;

    } else {

        throw new Error('找不到要删除对应的节点');

    }

}

双向链表（DLink）类测试

// 实例化

var doubleLink = new DLink();

doubleLink.append(1);

doubleLink.append(2);

doubleLink.append(4);

doubleLink.display();

console.log('-------------------------');

doubleLink.dispReverse();

console.log('-------------------------');

doubleLink.insert(3, 2);

doubleLink.display();

doubleLink.remove(1);

console.log('-------------------------');

doubleLink.display();

运行结果：

1

2

4

-------------------------

4

2

1

-------------------------

1

2

3

4

-------------------------

2

3

4

循环链表

循环链表和单向链表相似，节点类型都是一样的。

唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即：this.head.next = this.head，并保证链表中最后一个节点的 next 属性，始终指向 head，如下图所示：

循环链表（CLink）实现

1. 构造函数

完整代码地址，这里，我们沿用单链表中的节点（Node）类，做为循环链表的节点类。不同的是，我们在 CLink 构造函数阶段，就要把 this.head 赋值给 this.head.next。

function CLink () {

    this.head = new Node('head');

    this.head.next = this.head;

}

2. append: 向链表节点增加一个元素

DLink.prototype.append = function (el) {

    var currNode = this.head;

    while (currNode.next != null && currNode.next != this.head) {

        currNode = currNode.next;

    }

    var newNode = new Node(el);

    newNode.next = currNode.next;

    newNode.prev = currNode;

    currNode.next = newNode;

}

3. find：根据节点的值查找链表节点

CLink.prototype.find = function (el) {

    var currNode = this.head;

    while (currNode && currNode.el != el) {

        currNode = currNode.next;

    }

    return currNode;

}

4. insert：插入一个节点

CLink.prototype.insert = function (newEl, oldEl) {

    var newNode = new Node(newEl);

    var currNode = this.find(oldEl);

    if (currNode) {

        newNode.next = currNode.next;

        currNode.next = newNode;

    } else {

        throw new Error('未找到指定要插入节点位置对应的值！');

    }

}

5. display：展示链表元素节点

CLink.prototype.display = function () {

    var currNode = this.head.next;

    while (currNode && currNode != this.head) {

        console.log(currNode.el);

        currNode = currNode.next;

    }

}

6. 根据给定值寻找前一个节点

CLink.prototype.findPrev = function (el) {

    var currNode = this.head;

    while (currNode.next && currNode.next.el !== el) {

        currNode = currNode.next;

    }

    return currNode;

}

7. 删除给定值对应的节点

CLink.prototype.remove = function (el) {

    var prevNode = this.findPrev(el);

    if (prevNode.next != null) {

        prevNode.next = prevNode.next.next;

        prevNode.next.next = null;

    } else {

        throw new Error('找不到要删除的节点');

    }

}

循环链表（CLink）类测试

var circleLink = new CLink ();

circleLink.append(1);

circleLink.append(2);

circleLink.append(4);

circleLink.display();

console.log('---------------------------');

circleLink.insert(3, 2);

circleLink.display();

console.log('---------------------------');

circleLink.remove(4);

circleLink.display();

运行结果：

1

2

4

---------------------------

1

2

3

4

---------------------------

1

2

3

链表实战

题目：

传说在公元 1 世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的 40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将 n 个人围成一圈，并且第 m 个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。

题解：

function survival (n, m) {

    if (n <= 2) {

        return;

    }

    var clink = new CLink();

    for (var i = 1; i <= n; i++) {

        clink.append(i);

    }

    var p = clink.head,

        count = 0;

    while (n > 2) {

        p = p.next;

        if (p === clink.head) {

            continue;

        }

        count++;

        if (count === m) {

            clink.remove(p.el);

            count = 0;

            n--;

        }

    }

    console.log('幸存者：');

    clink.display();

}

测试：

survival(10, 3);

运行结果：

幸存者：

4

10

解析：

首先，我们把 n 个人按1-n的序号排好，然后按照每第 m 个人死亡来循环遍历循环链表，直到剩下两个人为止。

1 2 3 4 5 6 7 8 9 10

    x     x     x

  x         x

x             x

        x

最新文章

  1. Baseadapter与Simpleadapter之争
  2. IplImage, CvMat, Mat 的关系和相互转换(转)
  3. Linux网络栈下两层实现
  4. 使用python做科学计算
  5. OAF_EO系列3 - Initialize详解和实现（案例）
  6. [Java] HashMap详解
  7. MongoDB 快速入门--高级
  8. 如何使用jQuery设置背景的透明度
  9. CSS浏览器兼容性----Hack
  10. flash player over linux
  11. 遍历（二）javascript的Foreach语法
  12. 九度OJ 1013 开门人和关门人
  13. bug 对应
  14. Unity MMORPG游戏开发教程（一）——初识Unity
  15. Redis的使用原理
  16. windowNoTitle 无效
  17. dskinlite(uieasy mfc界面库)使用记录2:绘制动态元素（按钮控件绘制元素动态控制，改变图片和文字）
  18. C# DataTable 操作
  19. React Router 4.0 ---- 嵌套路由和动态路由
  20. LVS(IPVS)了解

热门文章

  1. 30分钟通过Kong实现.NET网关
  2. You (oracle) are not allowed to access to (crontab) because of pam configura
  3. SpringMVC配置版到注解版
  4. springcloud优雅停止上下线与熔断
  5. 【java+selenium3】特殊元素iframe的定位及详解(三)
  6. 1组-Alpha冲刺-1/6
  7. ajax的get方法获取豆瓣电影前10页的数据
  8. 菜鸡的Java笔记 comparator 比较器
  9. php 递推 递归
  10. vite2 + vite.config.js 比较坑的环境变量，vite2模式的使用