[js] 請使用 js 實現(xiàn)一個雙向鏈表

鏈表結(jié)構(gòu)是我們在面試中經(jīng)常會被問起的較為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)問題，起初學習數(shù)據(jù)結(jié)構(gòu)使用的是C++語言，最近在做前端面試題的過程中沒碰到了需要用js實現(xiàn)雙鏈表的需求，百度出來的文章發(fā)現(xiàn)可很多錯誤，于是索性自己重新寫了，并且列出了一些錯誤點，這里給大家較為詳細的一步步看一下實現(xiàn)思想和步驟，相較于C++語言，js的實現(xiàn)可以說是很簡單了，不需要創(chuàng)建繁瑣的對象，更加直觀易懂；
首先我們來看一下雙向鏈表的結(jié)構(gòu)圖：
在這里插入圖片描述
每個結(jié)點包含三部分，指向前一個結(jié)點的指針（pre），指向后一個節(jié)點的指針（next），以及自己的數(shù)據(jù)部分（element）,于是我們就可以先寫出結(jié)點對象

function Node:定義結(jié)點對象

function Node(element) {this.element = elementthis.next = nullthis.previous = null }

然后我們開始實現(xiàn)插入鏈表的算法
在這里插入圖片描述

（聲明）下面函數(shù)中的this是我們最后初始化鏈表的實例，這里大家不要疑惑。可以拉到最下面我們初始化鏈表那里，相信你會明白呦

**`function insert`:插入節(jié)點**function insert(newelement, currentelement) {var newNode = new Node(newelement)var currentNode = this.find(currentelement)if (currentNode === 'error') {console.log('無法插入，要插入節(jié)點不存在')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) {/*如果找到最后一個節(jié)點還沒有找到我們的插入點，那么我們就會返回錯誤*/if (currentNode.next == null) {console.log('can not find this node; maybe not have this node')return 'error'}currentNode = currentNode.next}return currentNode }

接下來是移除結(jié)點的實現(xiàn)，如果看懂了插入節(jié)點的實現(xiàn)，那么移除就會很簡單了，相信大家都可以很快明白，這里就直接貼出實現(xiàn)代碼；

function remove:移除一個結(jié)點function remove(element) {var currentNode = this.find(element)if (currentNode === 'error') {console.log('要移除節(jié)點不存在')return}/*首先是不是頭尾節(jié)點的情況*/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) {/*當是頭節(jié)點的時候*/this.head = currentNode.nextcurrentNode.next.previous = nullcurrentNode.next = null} else if (currentNode.next == null) {/*當是尾節(jié)點的時候 */currentNode.previous.next = nullcurrentNode.previous = null} }

截止到這里我們基本功能已經(jīng)有了，下面使我們根據(jù)自己需要可以自定義一些其他函數(shù)

function lastNode：找到最后一個節(jié)點function lastNode() {var head = this.headwhile (head.next != null) {head = head.next}return head //這里head在尾節(jié)點的位置 } function append:將要添加的結(jié)點放在鏈表末尾function append(element) {var lastnode = this.lastNode()var newNode = new Node(element)lastnode.next = newNodenewNode.previous = lastnode } function showlist：將鏈表所有的結(jié)點打印出來function showlist() {var head = this.headdo {console.log(head.element)head = head.next} while (head != null)// 大家可以看一下下面注釋內(nèi)容存在什么問題，留給大家思考一下// while (head.next != null) {// console.log(head.element)// head = head.next// } }

接下來是對鏈表進行初始化，這也是上述函數(shù)中所有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)

下面是運行結(jié)果：
在這里插入圖片描述
源碼：

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('無法插入，要插入節(jié)點不存在')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('要移除節(jié)點不存在')return}/*首先是不是頭尾節(jié)點的情況*/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) {/*當是頭節(jié)點的時候*/this.head = currentNode.nextcurrentNode.next.previous = nullcurrentNode.next = null} else if (currentNode.next == null) {/*當是尾節(jié)點的時候 */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)

個人簡介

我是歌謠，歡迎和大家一起交流前后端知識。放棄很容易，
但堅持一定很酷。歡迎大家一起討論

主目錄

與歌謠一起通關(guān)前端面試題

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的[js] 请使用 js 实现一个双向链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。