數據結構-線性表(順序表與鏈表的基本知識以及ArrayList 源碼分析)

最新 02-04

數據結構之線性表

在開始數據結構前，先了解什麼是數據結構？數據結構 + 演算法 = 程序

數據結構的定義

數據結構是對在計算機內存中的數據的一種安排。也可以理解為對計算機運算的數據單元的一個抽象。也可以理解為數據結構是指在計算機內存空間中或磁碟中的組織形式。

數據結構的定義描述的有些抽象，舉個栗子：

比如：美女和野獸，抽象的事物表示美女：頭髮長前凸後翹。。。可以表示為一個數據單元，野獸也是一個數據單元。

我們可以這樣理解，數據結構是描述個體的數據集合，包含兩者的關係，數據與數據之前的關係，邏輯的結構。

比如：在人機對弈中，棋盤、棋子、人三者的關係，棋盤存儲起來棋子是個單獨的數據人是個對象三者之間的關係，錯綜複雜的關係組合起來就是數據結構。

數據結構的邏輯結構

1. 集合結構

2. 線性結構

3. 樹形結構

4. 圖形結構

數據結構的存儲結構

1. 表

2. 堆棧

3. 隊列

4. 數據

5. 樹

6. 二叉樹

7. 圖

了解了數據結構的基本內容，我們下面開始正題。

線性表

1. 順序存儲結構

2. 鏈式存儲結構

順序存儲結構

順序存儲結構可以理解為：

種菜，比如種蘿蔔，一個蘿蔔一個坑，從第一個一直按順序種到最後一個。

再比如我們去銀行辦理業務，都要先取號排隊，一個號都對應著一個人。

前後相關聯的

如下圖所示：

圖1

a1是a2的前驅，ai+1 是ai的後繼，a1沒有前驅，an沒有後繼

n為線性表的長度，若n==0時，線性表為空表.

順序表的類模型：

class Array { arrays[40]; int size;}

順序表用數組保存一系列的數據。

順序表的特徵

刪除操作：

順序表刪除

從上圖中我們可以看出，當中間部位離去一個後，就會將該位置的後面的所有節點向前移一位。這是順序表的刪除操作。

中間插入操作：

順序表插入

如上圖所示，我們將ax 插入到 a2 - a3 之間，就需要將 a2 之後的所有數據向後移動一位。

尾部插入：將非常簡單直接在尾部插入就可以了。

優點：尾插效率高，支持隨機訪問。缺點：中間插入和刪除效率低。應用： ArrayList。 ArrayList 的底層實現便是對數組的操作。

下面我們就分析一下 ArrayList 的源碼

ArrayList 源碼分析

ArrayList 繼承結構開始分析

public class ArrayList extends AbstractListimplements List, RandomAccess, Cloneable, java.io.Serializable

1. ArrayList 是繼承於AbstractList。

AbstractList extends AbstractCollection implements List AbstractList 繼承自AbstractCollection 抽象類，實現了list 介面，是ArrayList和AbstractSequentiaList 的父類,它實現了list 的一些位置相關的操作 (add,remove,get,set) ,是第一個實現隨機訪問的集合類，但不支持添加和替換，後續我們在分析AbstractList 源碼。

2. ArrayList 實現list 介面能對它進行隊列操作

3. ArrayList 實現了Cloneable介面，覆蓋了函數clone()

4. ArrayList 實現了java.io.Serializable 介面，支持序列化，能通過序列化傳輸數據

5. ArrayList 實現了RandomAccess介面是List 實現所使用的標記介面，用來表明其支持快速（通常是固定時間）隨機訪問。此介面的主要目的是允許一般的演算法更改其行為，從而在將其應用到隨機或連續訪問列表時能提供良好的性能。在對List特別的遍歷演算法中，要盡量來判斷是屬於RandomAccess(如ArrayList)還是SequenceAccess(如LinkedList），因為適合RandomAccess List的遍歷演算法，用在SequenceAccess List上就差別很大。

ArrayList 屬性

關鍵字transient 標識的欄位的生命周期僅存於調用者的內存中而不會寫到磁碟里持久化。

我們都知道一個對象只要實現了Serilizable介面，這個對象就可以被序列化，java的這種序列化模式為開發者提供了很多便利，我們可以不必關係具體序列化的過程，只要這個類實現了Serilizable介面，這個類的所有屬性和方法都會自動序列化。

然而在實際開發過程中，我們常常會遇到這樣的問題，這個類的有些屬性需要序列化，而其他屬性不需要被序列化，打個比方，如果一個用戶有一些敏感信息（如密碼，銀行卡號等），為了安全起見，不希望在網路操作（主要涉及到序列化操作，本地序列化緩存也適用）中被傳輸，這些信息對應的變數就可以加上transient關鍵字。換句話說，這個欄位的生命周期僅存於調用者的內存中而不會寫到磁碟里持久化。

總之，java 的transient關鍵字為我們提供了便利，你只需要實現Serilizable介面，將不需要序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。

/** * ArrayList的元素存儲在其中的數組緩衝區。 ArrayList的容量是這個數組緩衝區的長度。當添加第一個元素時，任何具有elementData == EMPTY_ELEMENTDATA的空ArrayList將展開為DEFAULT_CAPACITY。私有包允許從java.util.Collections訪問。 */ transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size; /** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {};

ArrayList 就是對數組進行添加刪除修改操作的，默認初始的容量 DEFAULT_CAPACITY = 10

ArrayList 的構造函數

// 定義容量也就是數組的大小public ArrayList(int initialCapacity) { super(); // 若傳入的值小於0 拋出異常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); //初始化數組 this.elementData = new Object[initialCapacity]; } /** * 默認構造函數初始化一個空的數組 */ public ArrayList() { super(); // private static final Object[] EMPTY_ELEMENTDATA = {}; this.elementData = EMPTY_ELEMENTDATA; } /** * 構造一個含有元素的列表 * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection

ArrayList 添加元素

尾部添加

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! //進行完數組的自增長後才向數組中添加元素 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { //如果elementData 是個空數組沒有元素 if (elementData == EMPTY_ELEMENTDATA) { //minCapacity 取DEFAULT_CAPACITY 和 minCapacity 的最大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } // 確保顯式容量 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code minCapacity 必須大於數組的長度才可自增長 if (minCapacity - elementData.length > 0) grow(minCapacity); } // 實現數組的自增長 private void grow(int minCapacity) { // overflow-conscious code 添加元素之前的數組長度 int oldCapacity = elementData.length; // 新的數組長度 int newCapacity = oldCapacity + (oldCapacity >> 1); // 若新的數組長度小於最小增長的數組長度,則 newCapacity = minCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //數組長度達到最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) //數組的最大長度 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // 對數組進行copy 擴大數組的長度 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

中間插入元素

public void add(int index, E element) { if (index > size index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); ensureCapacityInternal(size + 1); // Increments modCount!! // 將插入元素之後的數組後移一位其實就是對數組的copy src:源數組； srcPos:源數組要複製的起始位置； dest:目的數組； destPos:目的數組放置的起始位置； l ength:複製的長度。 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 向數組中添加元素 elementData[index] = element; size++; }

> 不管是尾部插入還是中間插入都會對數組進行copy 效率不高。

查找元素

非常簡單並且效率非常高

public E get(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); return (E) elementData[index]; }

替換元素

非常簡單並且效率非常高

public E set(int index, E element) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue; }

刪除元素

刪除某個位置的元素效率低

```public E remove(int index) { // 刪除元素的位置必須大於或等於數組的大小 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); modCount++; // 獲取要刪除的元素 E oldValue = (E) elementData[index]; //數據移動 int numMoved = size - index - 1; // 若刪除的不是最後一個 if (numMoved > 0) //對數組進行copy src:源數組； srcPos:源數組要複製的起始位置； dest:目的數組； destPos:目的數組放置的起始位置； l ength:複製的長度。 System.arraycopy(elementData, index+1, elementData, index, numMoved); // size - 1 前一位置空 elementData[--size] = null; // clear to let GC do its work // 返回刪除的元素 return oldValue; }```

同理刪除元素效率低

```public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) // 找到這個位置的元素 if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }```

以上就是ArrayList 的核心方法，由此我們可以得出結論，順序表最大的優點支持隨機訪問效率很快，而最大的缺點就是當數據量很大時，如果進行頻繁的刪除和中間插入操作將會非常慢效率很低。在項目中要謹慎使用ArrayList

鏈式存儲結構

定義: 線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素，這組數據元素可以是連續的，也可以是不連續的。

分類： 1：單鏈表 2：單循環鏈表 3：雙鏈表 4：雙向循環鏈表

鏈表的模型類

```class Node{ Object data; Node next;}```

單鏈表

如圖所示: 每個節點都有一個數據域P->data 一個指針域 P-> next -> data 指針域指向的當前節點的下一個節點。

單鏈表增加元素 --> 中間插入