循環列表是否可以通過正確的列表（由nil結尾）和循環組合來模擬？

我的直覺是，一個循環列表可以通過一個正確的列表（帶有一個結束標記）與一個循環遍歷整個列表進行模擬。我的感覺是，循環列表更清晰，因爲控制邏輯（循環）內置於結構中。另一方面，將控制邏輯從結構中分離出來似乎是一種分離的擔憂，這在某些情況下可能是有利的。我不太確定的是在什麼情況下都有用。此外，我不太確定仿真是否可能。如果沒有，請給我一個反例呢？循環列表是否可以通過正確的列表（由nil結尾）和循環組合來模擬？

來源

2014-02-26 day

是的。爲什麼這個不清楚？你爲什麼不列出你認爲是正面和負面的東西？（沒有這些，人們會認爲你沒有完成你的功課，並且你可能會得到更多的「關閉」響應） –

「具有循環的普通列表」究竟是什麼意思？ – YXD

什麼是帶有循環的「正常」列表？或者你的意思是模擬？列表是一個列表。我認爲這些定義很簡單。沒有模擬。 – luk32

是的，它總是可能的。

優點：

你有一個圓形的列表。這大概是一個專業人士，否則你不會這樣做。

缺點：

出於某種原因，你浪費時間來實現一個周圍正常名單的包裝，而不是僅僅在第一時間寫一個循環鏈表。

FWIW，我在幾年前得出結論，所有列表應該是循環的。這允許您使用單個指針，以列表中的（名義）最後一個元素使用單個指針，但您可以輕鬆地在O（1）時間的列表頭部和尾部插入。此外，使列表循環減少了列表操作代碼中的特殊情況的數量（有總是下一個指針處的有效節點）。

來源

2014-02-26 15:55:14 alastair

我沒有看到任何真正的區別。你要麼與'null'指針，特殊'Null'元素進行比較，要麼檢查下一個元素是否是'head'，以檢測結束。這是一個實現細節，我個人看不到任何優勢。如果列表單獨鏈接，也不能在O（1）末尾插入元素，除非每個列表存儲一個額外的指針，即使它是循環的。 – luk32

@ luk32如果它是單鏈和圓形的，你絕對*可以*在O（1）末尾插入一個元素;你只需要記住你指向列表的指針指向尾部而不是頭部。對於雙向鏈表，循環性的好處特別高，因爲它簡化了鏈接維護代碼。 – alastair

好吧，這是一種欺騙行爲。如果您的指針指向尾部，那麼您如何在列表中定義順序？您要麼重新定義，（或重新解釋）列表，要麼檢索第一個元素的時間爲'O（n）'。我仍然看不到如何循環簡化維護代碼。你總是有特殊情況。你可以再詳細一點嗎？我給出了3個選項，我看到，都是檢測列表末尾的邊界特殊情況，還有其他什麼。更通用？ – luk32

是的，你可以模擬它。但是你應該需要兩個指針來控制你的列表。一個用於訪問當前元素的指針和一個用於保存第一個元素的指針。您必須制定一些邏輯來檢測您的「當前元素指針」何時位於列表邊界之外並將其移至第一個元素。

來源

2014-02-26 15:55:20

循環列表是否可以通過正確的列表（由nil結尾）和循環組合來模擬？

回答

相關問題