一, 双向链表
在上文《JS 数据结构第二篇 --- 链表》中描述的是单向链表. 单向链表是指每个节点都存有指向下一个节点的地址, 双向链表则是在单向链表的基础上, 给每个节点增加一个指向上一个节点的地址. 然后头结点的上一个节点, 和尾结点的下一个节点都指向 null. 同时 LinkedList 类中再增加一个 last 内部属性, 一直指向链表中最后一个节点. 结构模拟如图:
同样对外暴露的方法和单向链表一样, 只是内部实现稍有变化
双向链表完整设计代码:
- /**
- * 自定义双向链表: 对外公开的方法有
- * append(element) 在链表最后追加节点
- * insert(index, element) 根据索引 index, 在索引位置插入节点
- * remove(element) 删除节点
- * removeAt(index) 删除指定索引节点
- * removeAll(element) 删除所有匹配的节点
- * set(index, element) 根据索引, 修改对应索引的节点值
- * get(index) 根据索引获取节点信息
- * indexOf(element) 获取某个节点的索引位置
- * clear() 清空所有节点
- * length() 返回节点长度
- * print() 打印所有节点信息
- * toString() 打印所有节点信息, 同 print
- * */
- const LinkedListDouble = function(){
- let head = null; // 链表中第一个 LinkNode
- let last = null; // 链表中最后一个 LinkNode
- let size = 0; // 记录链表元素个数
- //Node 模型
- function LinkNode(prev, element, next){
- this.prev = prev; // 当前节点的上一个 node
- this.element = element; // 当前节点的元素
- this.next = next; // 当前节点的下一个 node
- }
- // 元素越界检查, 越界抛出异常
- function outOfBounds(index){
- if (index <0 || index>= size){
- throw("抱歉, 目标位置不存在!");
- }
- }
- // 根据索引, 获取目标对象
- function node(index){
- outOfBounds(index);
- // 判断 index 是靠近前半部分, 还是后半部分, 以求最少次数找到目标节点
- if (index <= size>>1){
- // 说明从头往后找, 次数少一点
- let obj = head;
- for (let i = 0;i <index; i++){
- obj = obj.next;
- }
- return obj;
- }
- else{
- // 说明从后往前找, 次数少一点
- let obj = last;
- for (let i = size-1; i> index; i--){
- obj = obj.prev;
- }
- return obj;
- }
- }
- // 新增一个元素
- function append(element){
- if (size == 0){
- head = new LinkNode(null, element, null);
- last = head;
- }
- else{
- let obj = node(size-1);
- obj.next = new LinkNode(obj, element, null);
- last = obj.next;
- }
- size++;
- }
- // 插入一个元素
- function insert(index, element){
- if (index == 0){
- head = new LinkNode(null, element, head);
- if (size == 0){
- last = head;
- }
- }
- else{
- let obj = node(index-1);
- obj.next = new LinkNode(obj, element, obj.next);
- if (index == size){
- last = obj.next;
- }
- }
- size++;
- }
- // 修改元素
- function set(index, element){
- let obj = node(index);
- obj.element = element;
- }
- // 移除节点 (内部使用, 不对外暴露)
- function removeNode(node){
- let prev = node.prev, next = node.next; // 当前节点的前一个, 和后一个
- // 判断 head 临界点
- if (prev == head){
- head = next;
- }
- else{
- prev.next = next;
- }
- // 判断 last 临界点
- if (next == last){
- last = prev;
- }
- else{
- next.prev = prev;
- }
- size--;
- return node.element;
- }
- // 根据值移除节点元素
- function remove(element){
- let temp = head;
- while(temp){
- if (temp.element == element){
- return removeNode(temp);
- }
- else{
- temp = temp.next;
- }
- }
- return null;
- }
- // 根据索引移除节点
- function removeAt(index){
- return removeNode(node(index));
- }
- // 移除链表里面的所有匹配值 element 的元素
- function removeAll(element){
- let newFirst = new LinkNode(null, 0, head), ele = null;
- let virHead = newFirst;
- while(virHead.next){
- if (virHead.next.element == element){
- ele = element;
- if (virHead.next.next){
- virHead.next.next.prev = virHead.next.prev;
- }
- else{ // 删除了最后一个节点
- last = virHead.next.prev;
- }
- virHead.next = virHead.next.next;
- size--;
- }
- else{
- virHead = virHead.next;
- }
- }
- // 重新赋值
- head = newFirst.next;
- return ele;
- }
- // 获取某个元素
- function get(index){
- return node(index).element;
- }
- // 获取元素索引
- function indexOf(element){
- let obj = head, index = -1;
- for (let i = 0; i <size; i++){
- if (obj.element == element){
- index = i;
- break;
- }
- obj = obj.next;
- }
- return index;
- }
- // 清除所有元素
- function clear(){
- head = null;
- last = null;
- size = 0;
- }
- // 属性转字符串
- function getObjString(obj){
- let str = "";
- if (obj instanceof Array){
- str += "[";
- for (let i = 0; i < obj.length; i++){
- str += getObjString(obj[i]);
- }
- str = str.substring(0, str.length - 2);
- str += "],"
- }
- else if (obj instanceof Object){
- str += "{";
- for (var key in obj){
- let item = obj[key];
- str += "\"" + key + "\": " + getObjString(item);
- }
- str = str.substring(0, str.length-2);
- str += "},"
- }
- else if (typeof obj == "string"){
- str += "\"" + obj + "\"" + ",";
- }
- else{
- str += obj + ",";
- }
- return str;
- }
- function toString(){
- let str = "", obj = head;
- for (let i = 0; i < size; i++){
- str += getObjString(obj.element);
- obj = obj.next;
- }
- if (str.length> 0) str = str.substring(0, str.length -2);
- return str;
- }
- // 打印所有元素
- function print(){
- console.log(this.toString())
- }
- // 对外公开方法
- this.append = append;
- this.insert = insert;
- this.remove = remove;
- this.removeAt = removeAt;
- this.removeAll = removeAll;
- this.set = set;
- this.get = get;
- this.indexOf = indexOf;
- this.length = function(){
- return size;
- }
- this.clear = clear;
- this.print = print;
- this.toString = toString;
- }
- //// 测试
- // let obj = new LinkedListDouble();
- // let obj1 = { title: "全明星比赛", stores: [{name: "张飞 vs 岳飞", store: "2:3"}, { name: "关羽 vs 秦琼", store: "5:5"}]};
- // obj.append(99);
- // obj.append("hello")
- // obj.append(true)
- // obj.insert(3, obj1);
- // obj.insert(0, [12, false, "Good", 81]);
- // obj.print();
- // console.log("obj1.index:", obj.indexOf(obj1));
- // obj.remove(0);
- // obj.removeAll(obj1);
- // obj.print();
- //// 测试 2
- console.log("\n\n......test2.....")
- var obj2 = new LinkedListDouble();
- obj2.append(8); obj2.insert(1, 99); obj2.append('abc'); obj2.append(8); obj2.append(false);
- obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8);
- obj2.print();
- obj2.removeAll(8); // 删除所有 8
- obj2.print();
- View Code
二, 循环链表
在链表的基础上, 再稍稍修改一下, 让链表中的尾结点和头节点链接起来, 形成一个循环生生不息. 单向循环链表是尾结点的下一个地址指向头结点, 而不是 null; 双向循环链表则是 last 节点的 next 指向 head 节点, head 节点的 prev 指向 last 节点. 结构模拟如下两个图:
对于单个节点的循环链表, 头结点和尾节点为同一个节点, 则自己指向自己. 结构模拟如图:
循环链表的代码这里就不贴出来了, 代码放在 GitHub https://github.com/xiaotanit/Tan_DataStruct 那里, 有兴趣可以点进去看看.
三, 循环链表的应用 --- 约瑟夫问题模拟
据说著名犹太历史学家 Josephus 有过以下的故事: 在罗马人占领乔塔帕特后, 39 个犹太人与 Josephus 及他的朋友躲到一个洞中, 39 个犹太人决定宁愿死也不要被敌人抓到, 于是决定了一个自杀方式, 41 个人排成一个圆圈, 由第 1 个人开始报数, 每报数到第 3 人该人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止. 然而 Josephus 和他的朋友并不想遵从. 首先从一个人开始, 越过 k-2 个人 (因为第一个人已经被越过), 并杀掉第 k 个人. 接着, 再越过 k-1 个人, 并杀掉第 k 个人. 这个过程沿着圆圈一直进行, 直到最终只剩下一个人留下, 这个人就可以继续活着. 问题是, 给定了和, 一开始要站在什么地方才能避免被处决? Josephus 要他的朋友先假装遵从, 他将朋友与自己安排在第 16 个与第 31 个位置, 于是逃过了这场死亡游戏.
这里我做了一个效果图, 模拟下约瑟夫问题:
接下来我们如何用链表来模拟约瑟夫问题.
在上面循环链表的基础上, 我们给 LinkedList 再添加一个内部属性 current, 指向当前节点, 默认指向头结点; 再增加三个对外方法 next(),removeCurrent(),reset(), 分别表示当前节点指向下一个节点, 移除当前节点, 重置当前节点为头结点. 修改后, 新的 LinkedList 对外方法有:
新的循环双向链表完整设计代码:
- /**
- * 在循环双向链表的基础上, 增加 1 个属性, 3 个方法 (属性内部使用, 方法对外开放), 让循环链表发挥更大的效果:
- * current: 指向当前节点, 默认指向首节点 head
- * next(): 让 current 每次移动一次, 移上下一个节点, 返回元素
- * removeCurrent(): 每次删除当前 current 指向的节点, 删除后, current 指向下一个节点
- * reset(): 重置 current 指向首节点 head
- *
- * 自定义双向循环链表: 对外公开的方法有
- * append(element) 在链表最后追加节点
- * insert(index, element) 根据索引 index, 在索引位置插入节点
- * remove(element) 删除节点
- * removeAt(index) 删除指定索引节点
- * removeAll(element) 删除所有匹配的节点
- * set(index, element) 根据索引, 修改对应索引的节点值
- * get(index) 根据索引获取节点信息
- * indexOf(element) 获取某个节点的索引位置
- * clear() 清空所有节点
- * length() 返回节点长度
- * print() 打印所有节点信息
- * toString() 打印所有节点信息, 同 print
- * */
- const CircleLinkedListDouble = function(){
- let head = null; // 链表中第一个 LinkNode
- let last = null; // 链表中最后一个 LinkNode
- let size = 0; // 记录链表元素个数
- let current = null; // 当前指向的节点
- //Node 模型
- function LinkNode(prev, element, next){
- this.prev = prev; // 当前节点的上一个 node
- this.element = element; // 当前节点的元素
- this.next = next; // 当前节点的下一个 node
- }
- // 元素越界检查, 越界抛出异常
- function outOfBounds(index){
- if (index <0 || index>= size){
- throw("抱歉, 目标位置不存在!");
- }
- }
- // 根据索引, 获取目标对象
- function node(index){
- outOfBounds(index);
- // 判断 index 是靠近前半部分, 还是后半部分, 以求最少次数找到目标节点
- if (index <= size>>1){
- // 说明从头往后找, 次数少一点
- let obj = head;
- for (let i = 0;i <index; i++){
- obj = obj.next;
- }
- return obj;
- }
- else{
- // 说明从后往前找, 次数少一点
- let obj = last;
- for (let i = size-1; i> index; i--){
- obj = obj.prev;
- }
- return obj;
- }
- }
- // 新增一个元素
- function append(element){
- if (size == 0){
- head = new LinkNode(null, element, null);
- head.next = head;
- head.prev = head;
- last = head;
- current = head;
- }
- else{
- let obj = node(size-1);
- obj.next = new LinkNode(obj, element, head);
- last = obj.next;
- head.prev = last;
- }
- size++;
- }
- // 插入一个元素
- function insert(index, element){
- // 表示插入到第一个
- if (index == 0){
- let last = null;
- if (size> 0) last = node(size-1);
- head = new LinkNode(last, element, head);
- if (size <1){
- head.next = head;
- head.prev = head;
- last = head;
- current = head;
- }
- else{
- last.prev = head;
- }
- }
- else{
- let prev = node(index-1);
- prev.next = new LinkNode(prev, element, prev.next);
- // 表示插入到最后一个
- if (index == size){
- last = prev.next;
- head.prev = last;
- }
- }
- size++;
- }
- // 修改元素
- function set(index, element){
- let obj = node(index);
- obj.element = element;
- }
- // 移除节点 (内部使用, 不对外暴露)
- function removeNode(node){
- if (size == 1){
- current = head = last = null;
- }
- else{
- let prev = node.prev, next = node.next; // 当前节点的前一个, 和后一个
- // 判断 head 临界点
- if (prev == last){
- head = next;
- head.prev = last;
- last.next = head;
- }
- else{
- prev.next = next;
- }
- // 判断 last 临界点
- if (next == head){
- last = prev;
- last.next = head;
- head.prev = last;
- }
- else{
- next.prev = prev;
- }
- if (current == node){
- current = next;
- }
- }
- size--;
- return node.element;
- }
- // 根据值移除节点元素
- function remove(element){
- let temp = head;
- while(temp){
- if (temp.element == element){
- return removeNode(temp);
- }
- else{
- temp = temp.next;
- }
- }
- return null;
- }
- // 根据索引移除节点
- function removeAt(index){
- return removeNode(node(index));
- }
- // 移除链表里面的所有匹配值 element 的元素
- function removeAll(element){
- let newFirst = new LinkNode(null, 0, head), delNode = null;
- let virHead = newFirst;
- // 为了避免无限循环, 先把循环链表断开
- head.prev = null, last.next = null;
- while(virHead.next){
- if (virHead.next.element == element){
- delNode = virHead.next;
- if (virHead.next.next){
- virHead.next.next.prev = virHead.next.prev;
- }
- else{
- last = virHead.next.prev;
- }
- if (virHead.next == current){
- current = current.next;
- virHead.next = current;
- }
- else{
- virHead.next = virHead.next.next;
- }
- size--;
- }
- else{
- virHead = virHead.next;
- }
- }
- // 重新赋值
- head = newFirst.next;
- last = size> 0 ? node(size-1) : null;
- if (size> 0){
- last.next = head;
- head.prev = last;
- }
- else{
- current = head = last = null;
- }
- return delNode.element;
- }
- // 获取某个元素
- function get(index){
- return node(index).element;
- }
- // 获取元素索引
- function indexOf(element){
- let obj = head, index = -1;
- for (let i = 0; i <size; i++){
- if (obj.element == element){
- index = i;
- break;
- }
- obj = obj.next;
- }
- return index;
- }
- // 清除所有元素
- function clear(){
- current = head = last = null;
- size = 0;
- }
- // 这次新增加的三个方法 next, removeCurrent, reset
- // 调用重置 current 指向 head 节点
- function reset(){
- current = head;
- }
- function next(){
- if (!current) return null;
- current = current.next;
- return current.element;
- }
- // 每调用一次, 删除 current 指向的节点
- function removeCurrent(){
- if (size < 1) return null;
- return removeNode(current);
- }
- // 属性转字符串
- function getObjString(obj){
- let str = "";
- if (obj instanceof Array){
- str += "[";
- for (let i = 0; i < obj.length; i++){
- str += getObjString(obj[i]);
- }
- str = str.substring(0, str.length - 2);
- str += "],"
- }
- else if (obj instanceof Object){
- str += "{";
- for (var key in obj){
- let item = obj[key];
- str += "\"" + key + "\": " + getObjString(item);
- }
- str = str.substring(0, str.length-2);
- str += "},"
- }
- else if (typeof obj == "string"){
- str += "\"" + obj + "\"" + ",";
- }
- else{
- str += obj + ",";
- }
- return str;
- }
- function toString(){
- let str = "", obj = head;
- for (let i = 0; i < size; i++){
- str += getObjString(obj.element);
- obj = obj.next;
- }
- if (str.length> 0) str = str.substring(0, str.length -2);
- return str;
- }
- // 打印所有元素
- function print(){
- console.log(this.toString())
- }
- // 对外公开方法
- this.append = append;
- this.insert = insert;
- this.remove = remove;
- this.removeAt = removeAt;
- this.removeAll = removeAll;
- this.set = set;
- this.get = get;
- this.indexOf = indexOf;
- this.length = function(){
- return size;
- }
- this.clear = clear;
- this.print = print;
- this.toString = toString;
- // 新增加的方法
- this.next = next;
- this.removeCurrent = removeCurrent;
- this.reset = reset;
- }
- //// 测试
- // let obj = new CircleLinkedListDouble();
- // let obj1 = { title: "全明星比赛", stores: [{name: "张飞 vs 岳飞", store: "2:3"}, { name: "关羽 vs 秦琼", store: "5:5"}]};
- //
- // obj.append(99);
- // obj.append("hello")
- // obj.append(true)
- // obj.insert(3, obj1);
- // obj.insert(0, [12, false, "Good", 81]);
- // obj.print();
- // console.log("obj1.index:", obj.indexOf(obj1));
- // obj.remove(0);
- // obj.removeAll(obj1);
- // obj.print();
- //// 测试 2
- // console.log("\n\n......test2.....")
- // var obj2 = new CircleLinkedListDouble();
- // obj2.append(8); obj2.append(99); obj2.append('abc'); obj2.append(8); obj2.append(false);
- // obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8);
- // obj2.print();
- // obj2.removeAll(8); // 删除所有 8
- // obj2.print();
- /**
- * 测试 3, 来做一个有意思的题目: 约瑟夫题目
- 据说著名犹太历史学家 Josephus 有过以下的故事: 在罗马人占领乔塔帕特后, 39 个犹太人与 Josephus 及他的朋友躲到一个洞中,
- 39 个犹太人决定宁愿死也不要被敌人抓到, 于是决定了一个自杀方式, 41 个人排成一个圆圈,
- 由第 1 个人开始报数, 每报数到第 3 人该人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止.
- 然而 Josephus 和他的朋友并不想遵从.
- 首先从一个人开始, 越过 k-2 个人 (因为第一个人已经被越过), 并杀掉第 k 个人.
- 接着, 再越过 k-1 个人, 并杀掉第 k 个人. 这个过程沿着圆圈一直进行, 直到最终只剩下一个人留下, 这个人就可以继续活着.
- 问题是, 给定了和, 一开始要站在什么地方才能避免被处决?
- Josephus 要他的朋友先假装遵从, 他将朋友与自己安排在第 16 个与第 31 个位置, 于是逃过了这场死亡游戏.
- 用循环链表来模拟这个游戏
- */
- console.log("\n\n........test3 约瑟夫题目.......");
- var obj3 = new CircleLinkedListDouble();
- for (let i = 0; i < 41; i++){
- obj3.append(i+1);
- }
- obj3.print();
- console.log("************* 约瑟夫游戏开始 **********")
- for (let i = 0; i < 39; i++){
- obj3.next(); obj3.next(); // 移动两次
- obj3.removeCurrent(); // 删除当前节点
- console.log("第", (i+1), "次, 剩余的为:", obj3.toString())
- }
- console.log("***************game over***************")
- console.log("最后生存下来的是:", obj3.toString());
- View Code
看下用链表模拟约瑟夫问题过程的效果:
其余单向循环链表, 单向循环链表增强, 双向循环链表等代码 Demo 见 GitHub 地址: https://github.com/xiaotanit/Tan_DataStruct
来源: https://www.cnblogs.com/tandaxia/p/11089196.html