數組與鏈接列表
數組是存儲元素集合的最常用的數據結構。大多數編程語言都提供了方法來輕鬆地聲明數組和訪問數組中的元素。鏈表,更確切地說是單鏈表,也是一種可以用來存儲元素集合的數據結構。它由一系列節點組成,每個節點都有對序列中下一個節點的引用。
如圖1所示,是一段代碼,通常用於聲明並向數組賦值。圖2描述了數組在內存中的樣子。
上面的代碼定義了一個可以存儲5個整數的數組,並使用索引0到4訪問它們。數組的一個重要屬性是整個數組被分配為一個內存塊,每個元素在數組中都有自己的空間。一旦定義了數組,它的大小就固定了。因此,如果在編譯時不確定數組的大小,那麼就必須定義一個足夠大的數組來保證安全。但是,在大多數情況下,我們實際使用的元素數量少於我們分配的數量。所以相當多的內存實際上被浪費了。另一方面,如果“足夠大的數組”實際上不夠大,程序就會崩潰。
鏈表在它自己的內存塊中將內存分別分配給它的元素,通過將這些元素作為鏈中的鏈接鏈接來獲得整體結構。圖3中的每個字段都有兩個鏈接的列表元素。數據字段保存存儲的實際數據,下一個字段保存對鏈中下一個元素的引用。鏈接列表的第一個元素存儲為鏈接列表的頭。
數據 | 下一個 |
圖3:鏈表的元素
圖4描述了一個包含三個元素的鏈表。每個元素存儲其數據,除最後一個元素外的所有元素都存儲對下一個元素的引用。最後一個元素的下一個字段中包含一個空值。列表中的任何元素都可以通過從開頭開始並跟隨下一個指針來訪問,直到滿足所需的元素為止。