歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> Java數據結構-線性表之循環鏈表

Java數據結構-線性表之循環鏈表

日期:2017/3/1 9:27:25   编辑:Linux編程

循環鏈表的定義:將單鏈表的尾節點的空指針改為指向頭結點的指針,這樣的單鏈表就變成單循環鏈表了,也叫循環鏈表。

下面摘抄了《大話數據結構》中的一段分析。如下圖:

解釋:
循環鏈表裡面的頭結點和單鏈表裡面的頭結點是一樣的,都是為了操作統一和方便而設定的,不是必須節點。

這裡為了方便操作還會進行一種改變,就是去掉循環鏈表的頭指針,而增加一個指向循環鏈表尾部節點的尾指針。
這樣相對來說可以通過O(1)時間訪問到尾節點了,同時在進行循環鏈表合並操作時更加方便了。

舉一個在《大話數據結構》裡面的例子,如下圖

通過上述例子可以看出去掉頭結點而增加尾節點的方法確實對於某些操作而言是較好的改進。

Copyright © Linux教程網 All Rights Reserved