您好,登錄后才能下訂單哦!
網(wǎng)上的相關(guān)教程非常多,基礎(chǔ)知識自行搜索即可。
習(xí)題主要選自O(shè)relly出版的《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》一書。
參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/List
特點:
鏈表由節(jié)點組成,每個節(jié)點增加一個對象的引用指向它的后繼節(jié)點。鏈表
也就是將一個線性表轉(zhuǎn)換為一個存儲空間上不連續(xù),而在抽象層面可連續(xù)訪問的表。
用途:
更快的插入和刪除,因為只需要操作插入刪除位置相鄰元素即可,如果在線性表中,操作中間位置的元素后,后續(xù)的元素位置都需要調(diào)整。javascript中的應(yīng)用例如原型鏈。
基本屬性
element
當前節(jié)點的值next
下一個節(jié)點基本方法
insert(item, newitem)
在item后面插入一個新元素newitem插入一個元素,需要將item元素節(jié)點的next
指向新元素,新元素的next
指向item元素的后繼元素。
remove(pos)
從隊頭刪除一個元素刪除一個節(jié)點時,需要將其前驅(qū)節(jié)點的next
指向其后繼節(jié)點即可。
find(element)
查詢值為element的節(jié)點位置
findpre(element)
查詢值為element的節(jié)點的前一個節(jié)點
display()
顯示整個鏈表根據(jù)鏈表的基本特性實現(xiàn)一個LinkedList
類,并在后續(xù)題目中需要用鏈表時使用它。
【注意點】:刪除指定元素時,由于需要修改指定元素前一個節(jié)點的next
指針,所以當所查找的節(jié)點存在時,搜索方法應(yīng)當返回其前一個節(jié)點以供后續(xù)步驟使用。
實現(xiàn)一個雙向鏈表TwoWayLinkedList
類。
【注意點】:每一個實例會記錄前驅(qū)節(jié)點和后繼節(jié)點,雙向鏈表比單鏈表增加了反向遍歷的能力,并且由于所查找節(jié)點的屬性中包含了前驅(qū)和后繼節(jié)點的信息,故插入節(jié)點和刪除節(jié)點時使用同一個搜索方法即可。
以LinkedList
類為參考基準,實現(xiàn)一個循環(huán)鏈表CircularLinkedList
類。
【注意點】:循環(huán)鏈表的特點是尾節(jié)點的next指針指向了頭節(jié)點。
Advance(n)
方法,使節(jié)點向前移動n個節(jié)點。back(n)
方法,使節(jié)點向后移動n個節(jié)點。show()
方法,只顯示當前節(jié)點上的數(shù)據(jù)。向前移動n
個位置,在位置驗證合法時相當于,從原位置刪除一個節(jié)點,在新位置插入一個節(jié)點,為操作方便直接使用雙向鏈表來實現(xiàn)即可。【注意點】:示例代碼中直接以放入鏈表的值為依據(jù)進行節(jié)點查找,故不支持重復(fù)數(shù)據(jù),可為節(jié)點增加index
屬性來區(qū)分相同數(shù)據(jù)。
與上一題同理。
很好實現(xiàn)。
使用一個單鏈表來存儲輸入的成績即可,當最后一個成績節(jié)點的指針指向null
即可。
count
屬性來記錄元素個數(shù)。免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。