0x00 數(shù)組
數(shù)組時(shí)一種線性表結(jié)構(gòu)订歪，用一組連續(xù)的內(nèi)存空間务热，來存儲一組具有相同類型的數(shù)據(jù)
1、線性表
顧名思義就是數(shù)據(jù)排列成一條線一樣的結(jié)構(gòu)舵变，每個(gè)數(shù)據(jù)最多只有前和后兩個(gè)方向记焊，線性表的結(jié)構(gòu)是邏輯結(jié)構(gòu)逸月，在實(shí)際物理存儲中分為順序表和鏈表
a、順序表亚亲，例如數(shù)組彻采，在內(nèi)存中為連續(xù)空間
b、鏈表捌归，在內(nèi)存中不一定連續(xù)肛响，用指針連接，也構(gòu)成線性結(jié)構(gòu)
線性表還有隊(duì)列惜索、棧等特笋，用順序表和鏈表都可以實(shí)現(xiàn)
與之對應(yīng)的就是非線形表，比如二叉樹巾兆、堆猎物、圖等，數(shù)據(jù)之間不是簡單的前后關(guān)系
2角塑、連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)
正是因?yàn)檫@個(gè)限制蔫磨，才使數(shù)組能夠支持隨機(jī)訪問，當(dāng)然也是因?yàn)榫S護(hù)這個(gè)特性圃伶，導(dǎo)致數(shù)組的插入和刪除需要做大量的數(shù)據(jù)搬遷工作
隨機(jī)訪問指根據(jù)數(shù)組下標(biāo)訪問數(shù)組能達(dá)到O(1)堤如，不是指查找
就算是順序數(shù)組蒲列，查找時(shí)間復(fù)雜度最快也是O(lgn)，因?yàn)槭沁B續(xù)的地址搀罢，所以根據(jù)數(shù)組頭地址加上索引蝗岖，可以立刻得到索引處數(shù)據(jù)的地址
3、插入和刪除
為了位數(shù)連續(xù)的內(nèi)存空間榔至，插入和刪除都需要做大量數(shù)據(jù)搬遷工作
最好的情況抵赢，插入或刪除最后一個(gè)元素，不用搬遷數(shù)組唧取，復(fù)雜度O(1)
最壞的情況铅鲤，插入或刪除第一個(gè)元素，后面所有的元素都需要前移或后移一位兵怯，復(fù)雜度O(n)
平均復(fù)雜度O(n)
4彩匕、容器和數(shù)組
針對數(shù)組類型腔剂，很多語言提出了容器類媒区，例如java中的ArrayList
容器最大的好處是封裝了很多數(shù)組處理的細(xì)節(jié)，支持動態(tài)擴(kuò)容掸犬，動態(tài)擴(kuò)容過程中會有很多數(shù)據(jù)搬遷工作袜漩，所以在使用容器時(shí)，如果能確定大小湾碎，最好提前指定
數(shù)組相對容器來說也有一些優(yōu)勢：
- 容器只支持對象宙攻，數(shù)組支持基本類型，例如int介褥、double類型座掘，自動的裝箱拆箱有一定的性能損耗
- 如果數(shù)據(jù)大小事先已知，并且對數(shù)據(jù)的操作非常簡單柔滔，用不到ArrayList的大部分方法溢陪，也可以直接使用數(shù)組
總的來說，如果不是非常底層的開發(fā)睛廊，對性能要求特別高形真，容器更方便使用
5、為什么很多編程語言中數(shù)組都是從0開始
如果a[0]表示首地址超全，a[k]表示k位地址
0開始
a[k]_address = base_address + k * type_size
1開始
a[k]_address = base_address + (k-1)*type_size
對比可以看出咆霜，從1開始多了一次減法操作，數(shù)組時(shí)非乘恢欤基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)蛾坯，為了效率優(yōu)化做到極致，所以大部分變成語言的數(shù)組下標(biāo)都是從0開始
