02-數(shù)據(jù)結(jié)構(gòu)與動(dòng)態(tài)數(shù)組

• 什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)谁撼、組織數(shù)據(jù)的方式

線(xiàn)性結(jié)構(gòu)示意圖

1566035015907.png

樹(shù)形結(jié)構(gòu)示意圖

1566035057443.png

圖形結(jié)構(gòu)示意圖

1566035090827.png

提示：在實(shí)際應(yīng)用中辩涝，根據(jù)使用場(chǎng)景來(lái)選擇最合適的數(shù)據(jù)結(jié)構(gòu)

• 線(xiàn)性表

線(xiàn)性表是具有n個(gè)相同類(lèi)型元素的有限序列（n ≥ 0）贸伐；如圖所示

1566035864320.png

其中：

a(1)是首節(jié)點(diǎn)（首元素），a(n)是尾節(jié)點(diǎn)（尾元素）

a(1)是a(2)的前驅(qū)結(jié)點(diǎn)怔揩，a(2)是a(1)的后繼節(jié)點(diǎn)

常見(jiàn)的線(xiàn)性表有

1. 數(shù)組
2. 鏈表
3. 棧
4. 隊(duì)列
5. 哈希表（散列表）

• 數(shù)組

數(shù)組是一種順序存儲(chǔ)的線(xiàn)性表捉邢，所有元素的內(nèi)存地址是連續(xù)的

例如以下代碼

int[] array = new int[]{11,22,33};

其對(duì)應(yīng)的內(nèi)存結(jié)構(gòu)示意圖如下所示

1566036738665.png

在很多編程語(yǔ)言中，數(shù)組都有一個(gè)致命的缺點(diǎn)商膊，無(wú)法動(dòng)態(tài)修改數(shù)組的容量伏伐。

在實(shí)際開(kāi)發(fā)中，我們更希望數(shù)組的容量是可以動(dòng)態(tài)改變的

• 動(dòng)態(tài)數(shù)組接口設(shè)計(jì)

接下來(lái)晕拆，我們可以自己設(shè)計(jì)一個(gè)動(dòng)態(tài)數(shù)組的類(lèi)藐翎，其中為該類(lèi)提供以下接口，供外界使用，分別為

int size();//獲取元素的數(shù)量
boolean isEmpty();//判斷數(shù)組是否為空
boolean contains(E element);//判斷數(shù)組是否包含某個(gè)元素
void add(E element); //往數(shù)組的最前面添加元素
E get(int index); //獲取數(shù)組中索引為index的元素
E set(int index吝镣，E element); //往數(shù)組的第index位設(shè)置元素
void add(int index,E element); //往數(shù)組的index位添加元素
E remove(int index); //移除數(shù)組中索引為index的元素
int indexOf(E element); //查看元素的位置
void clear(); //刪除數(shù)組中的所有元素

• • 部分重要接口解析

  • 添加元素 - add(E element)

  在添加元素時(shí)堤器，我們會(huì)講新添加的元素放到數(shù)組的最后面，因此用圖表示如下

  1566134574339.png
  1566134788687.png

  通過(guò)觀察末贾，我們可以發(fā)現(xiàn)闸溃，新增元素是，是直接往size的位置存放數(shù)據(jù)拱撵，因此就會(huì)有以下代碼

  elements[size] = element;
  size++;
  

• 刪除元素- remove(int index)

我們假設(shè)此時(shí)辉川，size = 7 ,index = 3.通過(guò)圖行表示如下

1566135655813.png

刪除第3個(gè)元素，需要對(duì)后面元素做如下的操作

1. 將55移動(dòng)到原來(lái)44的位置
   1566136152730.png

2. 講66移動(dòng)到原來(lái)55的位置
   1566136192849.png

3. 將77移動(dòng)到原來(lái)66的位置
   1566136239653.png

最后移動(dòng)完成后拴测，還需要做一個(gè)size--的操作乓旗。詳細(xì)代碼請(qǐng)通過(guò)在demo源碼中查看

??最后一個(gè)元素怎么處理呢?

• 在某個(gè)位置添加元素 - add(int index, E element)

我們假設(shè)此時(shí)size = 5 , index = 2.則我們通過(guò)圖形表示如下

1566137184817.png

同樣的，我們也需要對(duì)index = 2之后（包括）的元素進(jìn)行往后移動(dòng)昼扛，其操作如下所示

1. 先將55往后挪動(dòng)到下一個(gè)元素的位置
   1566137399761.png

2. 然后再將44挪動(dòng)到原來(lái)55的位置
   1566137441884.png

3. 再然后將33挪動(dòng)到原來(lái)44的位置
   1566137491839.png

4. 最后寸齐，將空出來(lái)的位置，用來(lái)存放新的元素
   1566137540105.png

5. 最后將size++

?對(duì)數(shù)據(jù)的挪動(dòng)要講究順序抄谐，否則會(huì)出現(xiàn)下圖這種異常的情況

1566137709352.png

1566137737543.png

1566137758293.png

• 如何擴(kuò)容

1. 假設(shè)當(dāng)前數(shù)組的容量為4渺鹦，并且該數(shù)組已經(jīng)全部存滿(mǎn)了元素，如以下圖形所示
   1566139803985.png

2. 則如果還需要往該數(shù)組中存放元素蛹含，則需要重新申請(qǐng)一塊更大的連續(xù)內(nèi)存毅厚，來(lái)保存數(shù)組中的元素，如下圖所示
   1566140258724.png

3. 將原來(lái)數(shù)組中的元素浦箱，對(duì)應(yīng)拷貝到新的存儲(chǔ)空間中
   1566140524043.png

4. ArrayList指向新申請(qǐng)的存儲(chǔ)空間地址
   1566140595759.png

5. 最后吸耿，原來(lái)的數(shù)組，由于沒(méi)有任何引用指向該存儲(chǔ)空間酷窥，則該存儲(chǔ)空間的內(nèi)存會(huì)被系統(tǒng)回收掉
   1566140678916.png

詳細(xì)與擴(kuò)容相關(guān)的代碼咽安，請(qǐng)查閱demo文件中ArrayList類(lèi)中的ensureCapacity(int capacity)方法實(shí)現(xiàn)

• 對(duì)象數(shù)組

在前面的例子中，我們?cè)跀?shù)組中存放的數(shù)據(jù)都是int類(lèi)型蓬推，因此在數(shù)組指向的存儲(chǔ)空間中妆棒，是直接存放在其中的，但是在實(shí)際情況中沸伏，可能存放的是各種各樣的類(lèi)型糕珊，因此，在實(shí)際情況下毅糟，對(duì)象是通過(guò)下面的方式進(jìn)行存儲(chǔ)的

創(chuàng)建一個(gè)能存放7個(gè)Object對(duì)象的數(shù)組

Object[] objects = new Object[7]

1566214957377.png

通過(guò)內(nèi)存布局圖红选，我們可以清楚的知道，數(shù)組中每個(gè)元素實(shí)際存儲(chǔ)的是Object對(duì)象的內(nèi)存地址姆另，其內(nèi)存地址指向該Object對(duì)象喇肋。由于在實(shí)際開(kāi)發(fā)中坟乾，每個(gè)object所占用的存儲(chǔ)空間可能并不一樣，為了統(tǒng)一數(shù)組中每個(gè)元素所占用的空間都一樣苟蹈，因此采用存儲(chǔ)對(duì)象地址的方式糊渊，來(lái)進(jìn)行存儲(chǔ)，從而達(dá)到可以存放不同類(lèi)型對(duì)象的效果慧脱。

對(duì)象數(shù)組內(nèi)存管理細(xì)節(jié)

在前面 刪除元素- remove(int index)部分，我們是直接將元素往前挪動(dòng)贺喝，后面空出來(lái)的空間菱鸥，不做處理，不會(huì)有問(wèn)題躏鱼，但是當(dāng)我們?cè)跀?shù)組中存入對(duì)象的時(shí)候氮采，就不能這樣做了，因?yàn)椴蛔鎏幚淼脑?huà)染苛，會(huì)導(dǎo)致看似被刪掉的對(duì)象鹊漠，實(shí)際并沒(méi)有銷(xiāo)毀，因?yàn)閿?shù)組中的元素茶行，仍然引用的該對(duì)象躯概，使其不會(huì)被銷(xiāo)毀，因此我們應(yīng)該做如下的操作

    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
    return old;
    }

同樣的畔师，清空數(shù)組中說(shuō)有元素時(shí)娶靡，也需要做清空對(duì)象操作

    public void clear () {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
         size = 0;
    }

demo下載地址

文章完！