什么是資料結構？
資料結構是計算機存盤、組織資料的方式
在實際應用中，根據使用場景來選擇最合適的資料結構
線性表
線性表是具有n個相同型別元素的有限序列（n ≥ 0）
- a1是首節點（首元素），an是尾結點（尾元素）
- a1是a2的前驅，a2是a1的后驅
常見的線性表有陣列、鏈表、堆疊、佇列、哈希表（散串列）
陣列（Array）
陣列是一種順序存盤的線性表，所有元素的記憶體地址是連續的
在很多編程語言中，陣列都有一個缺點：無法動態修改容量
在實際開發中，我們更希望陣列的容量是可以動態改變的
下面我們就來自己設計一個動態陣列
首先，我們需要確定對外的介面有哪些？
完整的設計代碼如下
public class ArrayList<E> {
/**
* 元素的數量
*/
private int size;
/**
* 所有的元素
*/
private E[] elements;
// static 修飾靜態常量
// final 常量（等同于const）
// 常量名用大寫
private static final int DEFAULT_CAPACITY = 10;
private static final int ELEMENT_NOT_FOUND = -1;
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy]; // 所有的類，最終都繼承java.lang.Object
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
/**
* 清除所有元素
*/
public void clear() {
// 防止物件在堆空間占用記憶體，所以要清空釋放所有物件
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/**
* 元素的數量
* @return
*/
public int size() {
return size;
}
/**
* 是否為空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某個元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
/**
* 獲取index位置的元素
* @param index
* @return
*/
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/**
* 設定index位置的元素
* @param index
* @param element
* @return 原來的元素?
*/
public E set(int index, E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 在index位置插入一個元素
* @param index
* @param element
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
/**
* 洗掉index位置的元素
* @param index
* @return
*/
public E remove(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
// 先減少，然后再清空最后一個位置
elements[--size] = null;
return old;
}
public E remove(E element) {
remove(indexOf(element));
return element;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) { // 判斷是否為null，容錯null呼叫函式的報錯
for (int i = 0; i < size; i++) {
// 如果為null，用陣列里的每一個元素判斷是否為空
// 而且為null的話，也不能用Object.equals來判斷，會報錯
if (elements[i] == null) return i;
}
} else {
for (int i = 0; i < size; i++) {
// 如果不為null，就可以直接用該元素和陣列里的每個元素進行比較
if (element.equals(elements[i])) return i; // n
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 保證要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
// 位運算的效率要高于賦值運算
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity + "擴容為" + newCapacity);
}
private void outOfBounds(int index) {
// 拋出例外：throw new
// IndexOutOfBoundsException：拼接字串資訊
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
設計點的詳細講解：
1.初始化陣列時可以設定開辟的存盤空間大小，只有大于默認存盤空間大小才會使用傳進來的值
private static final int DEFAULT_CAPACITY = 10;
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
2.利用泛型來接收任意型別的元素
由于所有的類，最終都繼承java.lang.Object，所以統一用基類Object初始化陣列
public class ArrayList<E> {
private E[] elements;
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
}
3.在Java中，成員變數會自動初始化
int型別自動初始化為0，物件型別自動初始化為null
public class ArrayList<E> {
private int size;
private E[] elements;
}
4.添加元素時，會先判斷存盤容量是否已滿，如果滿了需要擴容
擴容的本質就是創建新的空間，并把之前的元素重新放進去
擴容的容量為原始容量的1.5倍，采用位運算來計算新的容量，效率高于賦值運算
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
// 位運算的效率要高于賦值運算
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity + "擴容為" + newCapacity);
}
5.洗掉元素時，先將容量減少，被洗掉元素的下一個元素將其覆寫，然后將最后一位元素置空
public E remove(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
elements[--size] = null;
return old;
}
6.清空所有元素時，如果只是值型別，直接將size為0就代表不能訪問元素的位置了，而不必要真的將所有元素都置為null
但是元素為物件型別時，元素記憶體儲的只是物件在堆空間的地址值，而不被使用的元素會占據著堆空間不會釋放，只有重新添加元素時才會釋放對應位置的舊的物件參考
所以為了兼容不同型別的元素，我們要在清空陣列的時候將所有元素都置為null，然后再將size置為0
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
7.查看元素的索引，要分開判斷元素是否為null的條件
如果元素為null，那么要用陣列中的每一個元素都去判斷是不是空值，而且不可以用Object.equals來判斷，會報錯
如果元素不為null，就可以直接用作為引數的元素和陣列中的每個元素進行判斷
Java的Object.equals可以重寫來設定判斷的條件，不局限于值相等或者地址相等，如果只是用==來判斷，相對單一了
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) return i;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) return i; // n
}
}
return ELEMENT_NOT_FOUND;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271866.html
標籤：其他
上一篇：資料結構與演算法（二）復雜度