排序鏈表的目的是什麼？

Question

我想知道排序鏈接列表的目的是什麼。因爲如果您需要在未排序的鏈接列表和已排序的鏈接列表中查找元素，則必須執行O（n）。 請原諒我的問題是否愚蠢

Answer 1

排序的目的並不總是在對數時間搜索。很顯然，有很多其他的排序數據應用程序。

假設您必須從大鏈接列表中去除重複（刪除重複元素），並且您沒有足夠的空間將列表項加載到哈希表中，因爲列表非常大。在這種情況下，您可以對列表進行排序並刪除連續的元素（如果它們相同），從而對列表進行重複刪除。

如果要將元素插入已排序容器中的適當位置，排序鏈接列表非常方便，這將保證線性時間和恆定的空間複雜度。但是對於數組，您需要使用臨時數組，然後逐個移動所有元素。 Infact LRU緩存是一個雙向鏈接列表，並根據最近擊中的項目進行排序。新近使用的項目和舊項目再次被訪問，插入前面以保持已排序的列表排序。如果在這裏使用類似於結構的陣列，則LRU緩存不能提供恆定的複雜性。這只是一些經典的應用。你可以找到很多其他的應用程序。

Answer 2

讓我們考慮一個鏈表用於實現優先級隊列。我們可以隨機添加不同優先級的元素，但是我們希望根據優先級處理隊列的元素，維護排序後的鏈接列表會很有用，以便優先級最高的項目出現在開頭，並將它們從隊列是一個簡單的操作。這不是完全排序列表，而是插入項目時，它將根據優先級放置在正確的位置。這與數組的插入排序類似。