概述
數(shù)組
????是將元素在內(nèi)存中連續(xù)存放向叉,由于每個元素占用內(nèi)存相同,可以通過下標迅速訪問數(shù)組中任何元素初坠。但是如果要在數(shù)組中增加一個元素查排,需要移動大量元素躯舔,在內(nèi)存中空出一個元素的空間驴剔,然后將要增加的元素放在其中。同樣的道理粥庄,如果想刪除一個元素丧失,同樣需要移動大量元素去填掉被移動的元素。如果應(yīng)用需要快速訪問數(shù)據(jù)飒赃,很少插入和刪除元素利花,就應(yīng)該用數(shù)組。
鏈表
????中的元素在內(nèi)存中不是順序存儲的载佳,而是通過存在元素中的指針聯(lián)系到一起,每個結(jié)點包括兩個部分:一個是存儲 數(shù)據(jù)元素 的 數(shù)據(jù)域臀栈,另一個是存儲下一個結(jié)點地址的 指針蔫慧。如果要訪問鏈表中一個元素,需要從第一個元素開始权薯,一直找到需要的元素位置姑躲。但是增加和刪除一個元素對于鏈表數(shù)據(jù)結(jié)構(gòu)就非常簡單了,只要修改元素中的指針就可以了盟蚣。如果應(yīng)用需要經(jīng)常插入和刪除元素你就需要用鏈表黍析。
內(nèi)存存儲區(qū)別
數(shù)組從棧中分配空間, 對于程序員方便快速,但自由度小。
鏈表從堆中分配空間, 自由度大但申請管理比較麻煩屎开。
總結(jié)
1阐枣、存取方式上,數(shù)組可以順序存取或者隨機存取奄抽,而鏈表只能順序存劝健;
2逞度、存儲位置上额划,數(shù)組邏輯上相鄰的元素在物理存儲位置上也相鄰,而鏈表不一定档泽;
3俊戳、存儲空間上,鏈表由于帶有指針域馆匿,存儲密度不如數(shù)組大抑胎;
4、按序號查找時甜熔,數(shù)組可以隨機訪問圆恤,時間復(fù)雜度為O(1),而鏈表不支持隨機訪問,平均需要O(n)盆昙;
5羽历、按值查找時,若數(shù)組無序淡喜,數(shù)組和鏈表時間復(fù)雜度均為O(1)秕磷,但是當數(shù)組有序時,可以采用折半查找將時間復(fù)雜度降為O(logn)炼团;
6澎嚣、插入和刪除時,數(shù)組平均需要移動n/2個元素瘟芝,而鏈表只需修改指針即可易桃;
7、空間分配方面:
數(shù)組在靜態(tài)存儲分配情形下锌俱,存儲元素數(shù)量受限制晤郑,動態(tài)存儲分配情形下,雖然存儲空間可以擴充贸宏,但需要移動大量元素造寝,導(dǎo)致操作效率降低,而且如果內(nèi)存中沒有更大塊連續(xù)存儲空間將導(dǎo)致分配失斂粤贰诫龙;
鏈表存儲的節(jié)點空間只在需要的時候申請分配,只要內(nèi)存中有空間就可以分配鲫咽,操作比較靈活高效签赃;