1.定義
1.一種線性表數(shù)據(jù)結(jié)構(gòu);
-
2.連續(xù)的內(nèi)存空間存儲相同類型的數(shù)據(jù);
1. 隨機(jī)訪問
2.讓數(shù)組的很多操作變得非常低效代箭，比如要想在數(shù)組中刪除羡铲、插入一個數(shù)據(jù)嫩与，為了保證連續(xù)性寝姿，就需要做大量的數(shù)據(jù)搬移工作
2.基本方法解讀
-
1. 插入: 向數(shù)組array的第k個位置插入一個新元素
1. 如果數(shù)組中的數(shù)據(jù)有序: 插入新元素之后,需要搬移k之后的數(shù)據(jù)
2. 如果數(shù)組中的數(shù)據(jù)無序: 直接將第k位數(shù)據(jù)搬移到數(shù)組最后,把新的元素直接放入第k個位置
-
2. 刪除: 刪除數(shù)組array的第k個元素
1.刪除第k個元素之后,需要將k后面的元素往前順移一位
2.優(yōu)化(JVM標(biāo)記清除垃圾回收算法核心思想): 每次的刪除操作,并不是真正的搬移數(shù)據(jù),而是標(biāo)記數(shù)據(jù),當(dāng)數(shù)組沒有更多的空間存儲數(shù)據(jù)的時(shí)候,集中執(zhí)行一次真正的刪除操作(搬移數(shù)據(jù))
-
3. 查找
- 1.公式 array[k]=array[0]+k*size_type
3.應(yīng)用
1. 容器類: ArrayList, Vector, CopyOnWriteArrayList
2. 垃圾回收: 標(biāo)記清除算法
4.問題探究
1. 容器類 vs 數(shù)組 選擇.
2.為什么大多數(shù)變成語言中,數(shù)組要從0開始,而不是從1開始?
3.ArrayList,Vector,CopyOnWriteArrayList的區(qū)別.
5.拓展
-
1.標(biāo)記清除算法的缺點(diǎn)
1.效率問題: 標(biāo)記和清理的效率都不高,但只有少量垃圾產(chǎn)生時(shí)會很高效
2.空間問題: 會產(chǎn)生不連續(xù)的內(nèi)存空間碎片
