資料結構（一）：陣列-有解無憂

一、概述

定義：陣列（Array）是一種線性表資料結構，它用一組連續的記憶體空間來存盤一組具有相同型別的資料
- 線性表資料結構：資料排成像一條線那樣的線性結構
- 連續的記憶體空間：資料在記憶體里面的存盤空間是連續的一塊記憶體
- 具有相同型別：陣列里面的所有資料的資料型別是相同的
示例代碼
- ```
int[] array = new int[3];
```
- 由上述代碼我們可以看出來，使用陣列我們需要指定陣列的長度
- Array陣列是無法動態擴容的，我們需要預先指定它的長度

二、圖示結構

三、操作陣列的時間復雜度

查詢
- 我們可以直接通過array[index]的方式來訪問陣列，所以來說，陣列支持隨機訪問，根據下標隨機訪問的時間復雜度為O(1)
- 注意：我們并不能籠統的來說陣列的查詢復雜度為O(1)
插入
- 由上圖我們可以看出來，在陣列指定位置插入一個元素，這個位置之后的所有資料都要往后挪一個位置，所以這種情況的時間復雜度為O(n)；
- 最理想的狀態下是在該陣列的尾部插入一個元素，這樣一個元素都不用挪動，這時的時間復雜度為O(1)
- 綜上，陣列插入的時間復雜度為：O(n)
洗掉
- 洗掉陣列中指定位置的一個元素，洗掉之后，這個位置之后的所有資料都要向前挪動一個位置，這時時間復雜度為O(n)
- 如果是洗掉陣列尾部的元素的話，陣列中元素都不用挪動，這個時候時間復雜度為O(1)
- 綜上，在陣列中洗掉一個元素的時間復雜度為O(n)

四、動態陣列（ArrayList）

基本概念和用法：
- ArrayList可以動態的進行擴容，我們在宣告時不需要指定它的長度
- ArrayList不存盤基本資料型別，它存盤的是基本資料型別的封裝型別
- 如果宣告的時候不指定型別的話，它是可以存盤多種型別的資料的

ArrayList list = new ArrayList();
list.add(1 );
list.add("元素");

轉載請注明出處：https://www.cnblogs.com/Infancy/p/12591445.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69656.html

標籤：其他