摘要:本系列所有文章第一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列第二篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹簡單介紹鏈表鏈表一種常見的數(shù)據(jù)結(jié)構(gòu),可
簡單介紹鏈表本系列所有文章:
第一篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列
第二篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
第三篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合
第四篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表
第五篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹
鏈表一種常見的數(shù)據(jù)結(jié)構(gòu),可以存儲有序的元素集合。不同于數(shù)組,鏈表中元素在內(nèi)存中不是連續(xù)放置,同時每一個鏈表元素中除了本身的節(jié)點還保存了指向下一個元素的引用,這些特點使得鏈表元素在動態(tài)增加和刪除時不必移動其他元素,但是訪問鏈表元素時必須從起點開始迭代列表直到找到目標(biāo)元素。
下面是兩種鏈表的JavaScript實現(xiàn):
單向鏈表下圖就是一個典型的單向鏈表,這里注意:一般鏈表中的第一個元素會有一個head指針指向它,這也是我們操作鏈表必不可少的一環(huán)。
(圖片來源谷歌,侵刪)
用JavaScript實現(xiàn)單向鏈表與之前實現(xiàn)棧和隊列一樣,這里先聲明一個構(gòu)造函數(shù):
function LinkedList () { var Node = function (element) { this.element = element // 保存指向下個元素的引用,默認(rèn)為null this.next = null } // 鏈表長度 var length = 0 // head保存指向第一個元素的引用 var head = null }
鏈表需要實現(xiàn)以下方法:
append(element):向鏈表尾部添加元素
insert(position, element):向鏈表特定位置插入元素
removeAt(position):從鏈表特定位置移除一項
remove(element):在鏈表中移除某元素
indexOf(element):返回元素在鏈表中的索引,若不存在則返回-1
isEmpty():如果鏈表不包含任何元素就返回true,否則為false
size():返回鏈表長度
toString():返回元素的值轉(zhuǎn)成字符串
實現(xiàn)append類似數(shù)組的push方法,但是只能添加一個元素。實現(xiàn)方法的時候分兩種情況考慮:1. 鏈表為空時添加第一個元素;2. 鏈表不為空時在尾部添加元素
this.append = function (element) { var node = new Node(element), current if (head === null) { // 當(dāng)鏈表為空時 // 將head指向新增的元素 head = node } else { // 鏈表不為空 // 使用一個current變量從head開始迭代鏈表 current = head // 迭代鏈表,直到找到最后一項 while (current.next) { current = current.next } // 找到最后一項,將其next賦為node,建立鏈接 current.next = node } // 更新列表長度 length++ }實現(xiàn)removeAt
在鏈表中特定位置移除元素,實現(xiàn)時也需要考慮兩種情況:1. 移除第一個元素;2. 移除其他元素(包括最后一個)
this.removeAt = function (position) { // 判斷位置是否越界 if (position > -1 && position < length) { var current = head, previous, index = 0 // 如果刪除了第一個元素,把head指向下一個元素就行了 if (position === 0) { head = current.next } else { // 根據(jù)輸入的位置查找要刪除的元素 while (index++ < position) { previous = current current = current.next } // 將上一個元素的next指向current的下一項,跳過current,實現(xiàn)移除current previous.next = current.next } // 更新列表長度 length-- // 返回刪除的元素 return current.element } else { return null } }實現(xiàn)insert
與removeAt類似的實現(xiàn),大家可以先不看源碼,自己按著removeAt的思路實現(xiàn)一遍
this.insert = function (position, element) { // 檢查位置是否越界 if (position >= 0 && position <= length) { var node = new Node(element), index = 0, previous, current = head // 在第一個位置添加 if (position === 0) { node.next = current head = node } else { while (index++ < position) { previous = current current = current.next } node.next = current previous.next = node } // 更新列表長度 length++ return true } else { return false } }實現(xiàn)indexOf
根據(jù)元素查找在鏈表中的位置,沒找到就返回-1
this.indexOf = function (element) { var current = head, index = 0 while (current) { if (element === current.element) { return index } index++ current = current.next } return -1 }實現(xiàn)其他方法
// 返回所有元素的值轉(zhuǎn)成字符串 this.toString = function () { var current = head, string = "" while (current) { string += current.element current = current.next } return string } // 移除特定元素 this.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) } // 判斷鏈表是否為空 this.isEmpty = function () { return length === 0 } // 返回鏈表長度 this.size = function () { return length } // 返回第一個元素 this.getHead = function () { return head }
以上是單向鏈表的實現(xiàn),有興趣的可以下載源碼來看:
雙向鏈表單向鏈表的實現(xiàn)-源代碼
雙向鏈表和單向鏈表的區(qū)別就是每一個元素是雙向的,一個元素中包含兩個引用:一個指向前一個元素;一個指向下一個元素。除此之外,雙向鏈表還有一個指向最后一個元素的tail指針,這使得雙向鏈表可以從頭尾兩個方向迭代鏈表,因此更加靈活。如下圖:
(圖片來源谷歌搜索,侵刪)
用JavaScript實現(xiàn)雙向鏈表同單向鏈表一樣,先聲明一個構(gòu)造函數(shù)
function DoubleLinkedList () { var Node = function (element) { this.element = element this.prev = null // 新增了一個指向前一個元素的引用 this.next = null } var length = 0 var head = null var tail = null //新增了tail指向最后一個元素 }
雙向鏈表需要有以下方法:
append(element):向鏈表尾部添加元素
insert(position, element):向鏈表特定位置插入元素
removeAt(position):從鏈表特定位置移除一項
showHead():獲取雙向鏈表的頭部
showLength():獲取雙向鏈表長度
showTail():獲取雙向鏈表尾部
實現(xiàn)insert同單向鏈表類似,只不過情況更復(fù)雜了,你不僅需要額外考慮在第一個元素的位置插入新元素,還要考慮在最后一個元素之后插入新元素的情況。此外如果在第一個元素插入時,鏈表為空的情況也需要考慮。
this.insert = function (position, element) { // 檢查是否越界 if (position >= 0 && position <= length) { var node = new Node(element), current = head, previous, index = 0 if (position === 0) { // 第一個元素的位置插入 // 如果鏈表為空 if (!head) { head = node tail = node } else { node.next = current current.prev = node head = node } } else if (position === length) { // 在最后一個元素之后插入 current = tail node.prev = current current.next = node tail = node } else { // 在中間插入 while (index++ < position) { previous = current current = current.next } node.next = current previous.next = node current.prev = node node.prev = previous } length++ return true } else { return false } }實現(xiàn)removeAt
與insert類似,這里不多解釋直接貼代碼
this.removeAt = function (position) { // 檢查是否越界 if (position > -1 && position < length) { var current = head, previous, index = 0 if (position === 0) { // 第一個元素 head = current.next // 如果只有一個元素 if (length === 1) { tail = null } else { head.prev = null } } else if (position === length - 1) { // 最后一個元素 current = tail tail = current.prev tail.next = null } else { while (index++ < position) { previous = current current = current.next } previous.next = current.next current.next.prev = previous } length-- return current.element } else { return null } }實現(xiàn)append
和單向鏈表的一樣,只不過多了tail有一些不同
this.append = function (element) { var node = new Node(element), current = tail if (head === null) { head = node tail = node } else { node.prev = current current.next = node tail = node } length++ }
其他的代碼都很簡單,我就放上源代碼地址,大家自行查閱吧~
小結(jié)雙向鏈表的實現(xiàn)-源代碼
一開始寫的時候有點不習(xí)慣,但是實現(xiàn)了一兩個方法之后發(fā)現(xiàn)很多思路是類似的,于是舉一反三地寫出來,然后跟書上對比之后,發(fā)現(xiàn)還是有點差距的。
大家有興趣也動手去實踐一下再對比源碼,可以認(rèn)識到自己有哪些地方不足。
鏈表暫時就這樣了,明天繼續(xù)攻克集合!
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/87169.html
摘要:初始化時指針走兩步,指針走一步,不停遍歷的變化最后快慢指針又相遇了,循環(huán)結(jié)束,代碼實現(xiàn)如下復(fù)雜度分析,假設(shè)鏈表長度為時間復(fù)雜度,鏈表無環(huán)時,快指針會先到達尾部,時間就是如果有環(huán),那么假設(shè)環(huán)部長度為,時間就是,也就是空間復(fù)雜度 上一篇文章我們分析了下鏈表之反轉(zhuǎn)單向鏈表,這篇文章我們來分析下另外一個關(guān)于鏈表的經(jīng)典題目。 判斷鏈表是否有環(huán)(在leetcode上的題目地址:環(huán)形鏈表) 題目描述...
摘要:一定要認(rèn)真看分析注釋題目要求題目描述輸入一個鏈表,從尾到頭打印鏈表每個節(jié)點的值。分析因為鏈表只有知道當(dāng)前結(jié)點才能知道下一結(jié)點,所以不可能直接從后往前打印。 一定要認(rèn)真看 分析 | 注釋 | 題目要求 Question 1 題目描述:輸入一個鏈表,從尾到頭打印鏈表每個節(jié)點的值。 分析:因為鏈表只有知道當(dāng)前結(jié)點才能知道下一結(jié)點,所以不可能直接從后往前打印。這種逆序的算法(策略)我們常用棧這...
摘要:劍指中鏈表相關(guān)題目俗話說光說不練假把式,既然學(xué)習(xí)了鏈表的基礎(chǔ)概念和基本操作那我們一定要找些題目鞏固下,下面來看劍指中的相關(guān)題目。題目分析合并兩個排序的鏈表,需要分別比較兩個鏈表的每個值,然后改變指針。 溫故知新 鏈表由一個一個的作為節(jié)點的對象構(gòu)成的,每一個節(jié)點都有指向下一個節(jié)點的指針,最后一個節(jié)點的指針域指向空。每個節(jié)點可以存儲任何數(shù)據(jù)類型。 根據(jù)類型可以分為單鏈表、雙鏈表、環(huán)形鏈表、...
摘要:因為涉及指針,我們用引用來模擬,所以讀者應(yīng)該有面向?qū)ο蟮闹R貯備。引文因為涉及內(nèi)存,常常會有一些程序的邊界限制,需要擁有一定嚴(yán)密的邏輯去保證代碼的魯棒性和健壯性,所以這個知識點是面試的常考點。 tips:因為涉及指針,我們用引用來模擬,所以讀者應(yīng)該有面向?qū)ο蟮闹R貯備。 引子 你可以把鏈表簡單理解為動態(tài)數(shù)組,它不需要一塊一塊的開辟空間,同時,你又要注意,它存在的主要意義或者說使用場景...
閱讀 2465·2021-09-29 09:34
閱讀 3301·2021-09-23 11:21
閱讀 2494·2021-09-06 15:00
閱讀 1123·2019-08-30 15:44
閱讀 2024·2019-08-29 17:23
閱讀 2996·2019-08-29 16:44
閱讀 3052·2019-08-29 13:13
閱讀 1932·2019-08-28 18:12