JavaScript链表结构——双向链表

JavaScript链表结构——双向链表

//双向链表类 function DoublyLinkList(){ //节点类 function Node(data){ this.data = data this.pre = null this.next = null } //初始化属性 this.head = null this.tail = null this.length = 0 /* * * 1.append方法,在双链表尾部添加新节点 * */ DoublyLinkList.prototype.append = function(data){ let node = new Node(data) //判断当前链表是否为空 if (this.length == 0){ this.head = node this.tail = node } else{ node.prev = this.tail this.tail.next = node this.tail = node } //链表长度+1 this.length += 1 } /* * * 2.1 toString方法 * */ DoublyLinkList.prototype.toString = function(){ return this.backwardString() } /* * * 2.2 forwardString方法,从后向前返回字符串形式的数据 * */ DoublyLinkList.prototype.forwardString = function(){ let listString = '' let current = this.tail while(current != null){ listString += current.data + ' ' current = current.prev } return listString } /* * * 2.3 backwardString方法，从前向后返回字符串形式的数据 * */ DoublyLinkList.prototype.backwardString = function(){ let listString = '' let current = this.head while(current != null){ listString += current.data + ' ' current = current.next } return listString } /* * * 3. insert方法，指定位置插入节点 * */ DoublyLinkList.prototype.insert = function(data, position){ //判断position是否越界 if (position < 0 || position > this.length){ return false } //新建节点对象 let node = new Node(data) //1.判断插入位置是否为头部 if (position == 0){ //1.1判断当前链表是否为空 if (this.length == 0){ this.tail = node } //1.2当前链表不为空时 else{ this.head.prev = node node.next = this.head } //无论当前链表是否为空,head都重新指向新节点 this.head = node } //2.判断插入位置是否为尾部 else if (position == this.length){ this.append(data) } //3.插入的位置既不是头部也不是尾部 else{ let current = null //3.1 插入的位置离头部比较近 if (position <= this.length/2 - 1){ current = this.head let index = 0 //找到要插入的位置 while (index < position){ current = current.next index ++ } } //3.2 插入的位置离尾部比较近 else { current = this.tail let index = this.length - 1 //找到要插入的位置 while (index > position){ current = current.prev index -- } } //改变指针指向 node.next = current node.prev = current.prev current.prev.next = node current.prev = node } //链表长度+1 this.length += 1 } /* * * 4. get方法，查找指定位置的节点的数据 * */ DoublyLinkList.prototype.get = function(position){ //越界判断 if (position < 0 || position >= this.length){ return null } let current = null //查找的位置离头部比较近 if (position <= this.length/2 -1){ current = this.head let index = 0 while (index < position){ current = current.next index ++ } } //查找的位置离尾部比较近 else { current = this.tail let index = this.length - 1 while (index > position){ current = current.prev index -- } } return current.data } /* * * 5. indexOf方法,通过数据查找对应的索引 * */ DoublyLinkList.prototype.indexOf = function(data){ let current = this.head let index = 0 while (current != null){ if (current.data == data){ //找到返回index return index } current = current.next index ++ } //没找到返回-1 return -1 } /* * * 6. update方法，更新指定位置的节点的数据 * */ DoublyLinkList.prototype.update = function(newData, position){ if (position < 0 || position >= this.length){ return false } let current = null if (position <= this.length/2 -1){ current = this.head let index = 0 while (index < position){ current = current.next index ++ } } else { current = this.tail let index = this.length - 1 while (index > position){ current = current.prev index -- } } //打印数据变化 console.log(current.data + '=>' + newData) current.data = newData } /* * * 7. removeAt方法,移除指定位置的节点 * */ DoublyLinkList.prototype.removeAt = function(position){ if (position < 0 || position >= this.length){ return null } let current = this.head //1. 移除的位置为头部 if (position == 0){ //1.1 链表的长度为1 if (this.length == 1){ this.head = null this.tail = null } //1.2 链表的长度不为1 else { this.head.next.prev = null this.head = this.head.next } } //2. 移除的位置为尾部 else if (position == this.length -1){ current = this.tail this.tail.prev.next = null this.tail = this.tail.prev } //3. 移除的位置不是头部或尾部 else { //3.1 从头部开始寻找 if (position <= this.length -1){ current = this.head let index = 0 while (index < position){ current = current.next index ++ } } //3.2 从尾部开始寻找 else { current = this.tail let index = this.length -1 while (index > position){ current = current.prev index -- } } //改变指针指向 current.prev.next = current.next current.next.prev = current.prev } //链表长度-1 this.length -= 1 //返回删除的数据 return current.data } /* * * 8. remove方法，移除指定数据的节点 * */ DoublyLinkList.prototype.remove = function(data){ let index = this.indexOf(data) return this.removeAt(index) } }