野生前端的資料結構基礎練習(3)——連結串列
網上的相關教程非常多,基礎知識自行搜尋即可。
習題主要選自Orelly出版的《資料結構與演算法javascript描述》一書。
參考程式碼可見: ofollow,noindex" target="_blank">https://github.com/dashnowords/blogs/tree/master/Structure/List
連結串列的基本知識
-
特點:
連結串列由節點組成,每個節點增加一個物件的引用指向它的後繼節點。
連結串列
也就是將一個線性錶轉換為一個儲存空間上不連續,而在抽象層面可連續訪問的表。 -
用途:
更快的插入和刪除,因為只需要操作插入刪除位置相鄰元素即可,如果線上性表中,操作中間位置的元素後,後續的元素位置都需要調整。javascript中的應用例如原型鏈。
-
基本屬性
element next
-
基本方法
-
insert(item, newitem)
在item後面插入一個新元素newitem插入一個元素,需要將item元素節點的
next
指向新元素,新元素的next
指向item元素的後繼元素。 -
remove(pos)
從隊頭刪除一個元素刪除一個節點時,需要將其前驅節點的
next
指向其後繼節點即可。 -
find(element)
查詢值為element的節點位置 -
findpre(element)
查詢值為element的節點的前一個節點 -
display()
顯示整個連結串列
-
基本練習
-
根據連結串列的基本特性實現一個
LinkedList
類,並在後續題目中需要用連結串列時使用它。【注意點】:刪除指定元素時,由於需要修改指定元素前一個節點的
next
指標,所以當所查詢的節點存在時,搜尋方法應當返回其前一個節點以供後續步驟使用。 -
實現一個雙向連結串列
TwoWayLinkedList
類。【注意點】:每一個例項會記錄前驅節點和後繼節點,雙向連結串列比單鏈表增加了反向遍歷的能力,並且由於所查詢節點的屬性中包含了前驅和後繼節點的資訊,故插入節點和刪除節點時使用同一個搜尋方法即可。
-
以
LinkedList
類為參考基準,實現一個迴圈連結串列CircularLinkedList
類。【注意點】:迴圈連結串列的特點是尾節點的next指標指向了頭節點。
課後習題(書中第六節習題)
Advance(n) back(n) show()
習題思路
- 向前移動
n
個位置,在位置驗證合法時相當於,從原位置刪除一個節點,在新位置插入一個節點,為操作方便直接使用雙向連結串列來實現即可。【注意點】:示例程式碼中直接以放入連結串列的值為依據進行節點查詢,故不支援重複資料,可為節點增加index
屬性來區分相同資料。
-
與上一題原理一致
-
簡單,不做贅述。
-
使用一個單鏈表來儲存輸入的成績即可,當最後一個成績節點的指標指向
null
即可。 -
用值為1-40的元素迴圈連結串列來刪除節點直到總節點數目只剩2個為止。為了方便統計剩餘元素的數量,為連結串列增加一個
count
屬性來記錄元素個數。