重庆可作为推广的网站,wordpress 分享后阅读,河南郑州事件,购物网站asp源码[js] 请使用 js 实现一个双向链表
链表结构是我们在面试中经常会被问起的较为基础的数据结构问题#xff0c;起初学习数据结构使用的是C语言#xff0c;最近在做前端面试题的过程中没碰到了需要用js实现双链表的需求#xff0c;百度出来的文章发现可很多错误#xff0c;于…[js] 请使用 js 实现一个双向链表
链表结构是我们在面试中经常会被问起的较为基础的数据结构问题起初学习数据结构使用的是C语言最近在做前端面试题的过程中没碰到了需要用js实现双链表的需求百度出来的文章发现可很多错误于是索性自己重新写了并且列出了一些错误点这里给大家较为详细的一步步看一下实现思想和步骤相较于C语言js的实现可以说是很简单了不需要创建繁琐的对象更加直观易懂 首先我们来看一下双向链表的结构图 在这里插入图片描述 每个结点包含三部分指向前一个结点的指针pre指向后一个节点的指针next以及自己的数据部分element,于是我们就可以先写出结点对象
function Node:定义结点对象
function Node(element) {this.element elementthis.next nullthis.previous null
}然后我们开始实现插入链表的算法 在这里插入图片描述
声明下面函数中的this是我们最后初始化链表的实例这里大家不要疑惑。可以拉到最下面我们初始化链表那里相信你会明白呦
**function insert:插入节点**function insert(newelement, currentelement) {var newNode new Node(newelement)var currentNode this.find(currentelement)if (currentNode error) {console.log(无法插入要插入节点不存在)return}if (currentNode.next ! null) {newNode.next currentNode.nextcurrentNode.next newNodenewNode.previous currentNodenewNode.next.previous newNode} else {currentNode.next newNodenewNode.previous currentNode}
}function find:找到插入位置
function find(element) {var currentNode this.headwhile (currentNode.element ! element) {/*如果找到最后一个节点还没有找到我们的插入点那么我们就会返回错误*/if (currentNode.next null) {console.log(can not find this node; maybe not have this node)return error}currentNode currentNode.next}return currentNode
}接下来是移除结点的实现如果看懂了插入节点的实现那么移除就会很简单了相信大家都可以很快明白这里就直接贴出实现代码
function remove:移除一个结点function remove(element) {var currentNode this.find(element)if (currentNode error) {console.log(要移除节点不存在)return}/*首先是不是头尾节点的情况*/if (currentNode.next ! null currentNode.previous ! null) {currentNode.previous.next currentNode.nextcurrentNode.next.previous currentNode.previouscurrentNode.next nullcurrentNode.previous null} else if (currentNode.previous null) {/*当是头节点的时候*/this.head currentNode.nextcurrentNode.next.previous nullcurrentNode.next null} else if (currentNode.next null) {/*当是尾节点的时候 */currentNode.previous.next nullcurrentNode.previous null}
}
截止到这里我们基本功能已经有了下面使我们根据自己需要可以自定义一些其他函数
function lastNode找到最后一个节点function lastNode() {var head this.headwhile (head.next ! null) {head head.next}return head //这里head在尾节点的位置
}function append:将要添加的结点放在链表末尾function append(element) {var lastnode this.lastNode()var newNode new Node(element)lastnode.next newNodenewNode.previous lastnode
}function showlist将链表所有的结点打印出来function showlist() {var head this.headdo {console.log(head.element)head head.next} while (head ! null)// 大家可以看一下下面注释内容存在什么问题留给大家思考一下// while (head.next ! null) {// console.log(head.element)// head head.next// }
}接下来是对链表进行初始化这也是上述函数中所有this所代表的实例
function initlist:初始化链表并将所有方法注册到链表中
function initlist() {this.head new Node(one)this.find findthis.insert insertthis.remove removethis.showlist showlistthis.lastNode lastNodethis.append append
}var list new initlist()
list.insert(two, one)
list.insert(four, two)
list.insert(three, two)// console.log(list.head.next)
list.showlist()
list.append(A)
list.append(B)
list.insert(B2, B)
list.showlist()
console.log(list.lastNode())
// list.remove(one)
// list.showlist()
console.log(list.find(A).previous)
// console.log(list.find(four).previous)
// console.log(list.head.element)
下面是运行结果 在这里插入图片描述 源码
function Node(element) {this.element elementthis.next nullthis.previous null
}
function find(element) {var currentNode this.headwhile (currentNode.element ! element) {if (currentNode.next null) {console.log(can not find this node; maybe not have this node)return error}currentNode currentNode.next}return currentNode
}
function insert(newelement, currentelement) {var newNode new Node(newelement)var currentNode this.find(currentelement)if (currentNode error) {console.log(无法插入要插入节点不存在)return}if (currentNode.next ! null) {newNode.next currentNode.nextcurrentNode.next newNodenewNode.previous currentNodenewNode.next.previous newNode} else {currentNode.next newNodenewNode.previous currentNode}
}
function remove(element) {var currentNode this.find(element)if (currentNode error) {console.log(要移除节点不存在)return}/*首先是不是头尾节点的情况*/if (currentNode.next ! null currentNode.previous ! null) {currentNode.previous.next currentNode.nextcurrentNode.next.previous currentNode.previouscurrentNode.next nullcurrentNode.previous null} else if (currentNode.previous null) {/*当是头节点的时候*/this.head currentNode.nextcurrentNode.next.previous nullcurrentNode.next null} else if (currentNode.next null) {/*当是尾节点的时候 */currentNode.previous.next nullcurrentNode.previous null}
}
function showlist() {var head this.headdo {console.log(head.element)head head.next} while (head ! null)// while (head.next ! null) {// console.log(head.element)// head head.next// }
}
function initlist() {this.head new Node(one)this.find findthis.insert insertthis.remove removethis.showlist showlistthis.lastNode lastNodethis.append append
}
function append(element) {var lastnode this.lastNode()var newNode new Node(element)lastnode.next newNodenewNode.previous lastnode
}
function lastNode() {var head this.headwhile (head.next ! null) {head head.next}return head
}
var list new initlist()
list.insert(two, one)
list.insert(four, two)
list.insert(three, two)// console.log(list.head.next)
list.showlist()
list.append(A)
list.append(B)
list.insert(B2, B)
list.showlist()
console.log(list.lastNode())
// list.remove(one)
// list.showlist()
console.log(list.find(A).previous)
// console.log(list.find(four).previous)
// console.log(list.head.element)
个人简介
我是歌谣欢迎和大家一起交流前后端知识。放弃很容易 但坚持一定很酷。欢迎大家一起讨论
主目录
与歌谣一起通关前端面试题
