Yahoo奇摩知識+將於 2021 年 5 月 4 日 (美國東部時間) 終止服務。自 2021 年 4 月 20 日 (美國東部時間) 起,Yahoo奇摩知識+服務將會轉為唯讀模式。其他Yahoo奇摩產品與服務或您的Yahoo奇摩帳號都不會受影響。如需關於Yahoo奇摩知識+ 停止服務以及下載您個人資料的資訊,請參閱說明網頁。

資料結構題目的問題

Please give a discussion to compare the running situation of “Sequential List” and “Linked List” data structures in aspects of: (1)memory space, and (2)insert/delete data items

請問這題要怎麼解答?

1 個解答

評分
  • 6 年前
    最佳解答

    Sequential List = 一般的陣列

    Linked List = 鏈結串列

    一般的陣列,是申請一個連續區間的記憶體,之所以會連續是因為這麼一來只要記得第一個元素的記憶體位址,便可以在常數時間到達該陣列裡任一元素。假設是宣告int a[10],且一個int佔4bytes的記憶體,則a[0]的位址+4*n = a[n]的位址。由於它是連續的,所以進行新增的時候,必須將所有插入的位址以後的元素往後移,在加新元素插入,此時支付的時間是線性的。刪除也是同理,刪除該元素後,也需要將後面的所有元素往前移。因此查詢複雜度O(1), 新增/刪除O(n)。

    鏈結串列,是在隨意的位址(不需連續)申請記憶體,支付額外的空間,使每個元素都記得下一個元素的位址為何,如此一來,假設有三個元素,1, 2, 3,1指到2,2指到3,當2要被刪除的時候,只需要把1紀錄的"下個元素位址"改成3的位址即可,也就時能夠在常數時間完成新增/刪除的動作。反觀,查詢的時候,假如要查詢第n個元素,就必須從頭一個一個問,問n-1次才能達到該元素。因此查詢複雜度O(n),新增/刪除O(1)。

    記憶體消耗來說,如果都有優化,鏈接串列還是會消耗比較多記憶體,畢竟鏈接串列需要額外支付紀錄"下個元素位址"的記憶體。

    另外有種東西叫做"塊狀鏈表",查詢/新增/刪除複雜度都能做到O(√n),有興趣可以去看看。

還有問題?馬上發問,尋求解答。