2-3　新數(shù)據(jù)插入數(shù)組

數(shù)組結(jié)構(gòu)雖然好用，但是如果要將新數(shù)據(jù)插入數(shù)組或是刪除數(shù)組元素，則需要較多的時(shí)間，本節(jié)講解如何將新數(shù)據(jù)插入數(shù)組。

2-3-1　假設(shè)當(dāng)下有足夠的連續(xù)內(nèi)存空間

數(shù)組結(jié)構(gòu)雖然好用，但是如果要將新數(shù)據(jù)插入數(shù)組則需要較多的時(shí)間，下列是假設(shè)有一個(gè)內(nèi)存內(nèi)含數(shù)組x，此數(shù)組有5、3、9，3個(gè)數(shù)據(jù)。

假設(shè)現(xiàn)在想要在索引1位置插入一個(gè)數(shù)據(jù)2，數(shù)組處理步驟如下：

　步驟1

先確定數(shù)組有足夠的空間容納新元素。此時(shí)內(nèi)存空間概念圖如下：

　步驟2

由于新數(shù)據(jù)要放在x[1]索引位置，所以要先將原x[1]及以后的元素往后移動(dòng)，下列是移動(dòng)過程與結(jié)果。

下列是另一個(gè)元素3的移動(dòng)過程。

　步驟3

將數(shù)據(jù)2插入索引1位置。

上述在插入數(shù)據(jù)時(shí)，可能要移動(dòng)所有數(shù)組元素，所以時(shí)間復(fù)雜度是O（n）。

2-3-2　假設(shè)當(dāng)下沒有足夠的連續(xù)內(nèi)存空間

讀者可以想象，有幾個(gè)朋友相邀去看電影，當(dāng)坐下來后，有一位新朋友想插入一起坐下看電影，可是當(dāng)下區(qū)間座位有限，這時(shí)只好在電影院尋找其他的座位。

假設(shè)有一個(gè)數(shù)組，此數(shù)組內(nèi)含3個(gè)數(shù)據(jù)，此數(shù)組內(nèi)存空間的位置如下：

假設(shè)現(xiàn)在想要在索引1位置插入一個(gè)數(shù)據(jù)2，但數(shù)組連續(xù)空間不足，這時(shí)需要向計(jì)算機(jī)要新的可以容納數(shù)組的連續(xù)空間，然后將所有數(shù)組內(nèi)容移至新的內(nèi)存空間，下列是移動(dòng)與插入結(jié)果。

在沒有足夠內(nèi)存空間時(shí)插入數(shù)據(jù)，可能要移動(dòng)所有數(shù)組元素，所以時(shí)間復(fù)雜度是O（n）。