pexels-photo-577585
原文鏈接：https://wangwei.one/posts/java-data-structures-and-algorithms-arraylist.html
線性表
定義
將具有線性關(guān)系的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中所使用的存儲(chǔ)結(jié)構(gòu)稱為線性表掐场。
線性慢洋，是指數(shù)據(jù)在邏輯結(jié)構(gòu)上具有線性關(guān)系斤吐。
分類
邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)在物理結(jié)構(gòu)存儲(chǔ)分兩種形式：
- 數(shù)據(jù)在內(nèi)存中集中存儲(chǔ)炊林，采用順序表示結(jié)構(gòu)包券，稱為"順序存儲(chǔ)"碴倾；
- 數(shù)據(jù)在內(nèi)存中分散存儲(chǔ)害淤，采用鏈?zhǔn)奖硎窘Y(jié)構(gòu)据块，稱為"鏈?zhǔn)酱鎯?chǔ)"；
順序表
定義
邏輯上具有線性關(guān)系的數(shù)據(jù)按照前后的次序全部存儲(chǔ)在一整塊連續(xù)的內(nèi)存空間中兽肤，之間不存在空隙套腹，這樣的存儲(chǔ)結(jié)構(gòu)稱為順序存儲(chǔ)結(jié)構(gòu)。
使用線性表的順序存儲(chǔ)結(jié)構(gòu)生成的表资铡，稱為順序表电禀。
image
實(shí)現(xiàn)
順序表的存放數(shù)據(jù)的特點(diǎn)和數(shù)組一樣，所以我們這里采用數(shù)組來(lái)實(shí)現(xiàn)笤休，這里我們來(lái)用數(shù)組來(lái)簡(jiǎn)單實(shí)現(xiàn)Java中常用的ArrayList尖飞。
接口定義：
package one.wangwei.algorithms.datastructures.list;
/**
* List Interface
*
* @param <T>
* @author https://wangwei.one/
* @date 2018/04/27
*/
public interface IList<T> {
/**
* add element
*
* @param element
* @return
*/
public boolean add(T element);
/**
* add element at index
*
* @param index
* @param element
* @return
*/
public boolean add(int index, T element);
/**
* remove element
*
* @param element
* @return
*/
public boolean remove(T element);
/**
* remove element by index
*
* @param index
* @return
*/
public T remove(int index);
/**
* set element by index
*
* @param index
* @param element
* @return old element
*/
public T set(int index, T element);
/**
* get element by index
*
* @param index
* @return
*/
public T get(int index);
/**
* clear list
*/
public void clear();
/**
* contain certain element
*
* @param element
* @return
*/
public boolean contains(T element);
/**
* get list size
*
* @return
*/
public int size();
}
接口實(shí)現(xiàn)：
package one.wangwei.algorithms.datastructures.list.impl;
import one.wangwei.algorithms.datastructures.list.IList;
import java.util.Arrays;
/**
* Array List
*
* @param <T>
* @author https://wangwei.one
* @date 2018/04/27
*/
public class MyArrayList<T> implements IList<T> {
/**
* default array size
*/
private final int DEFAULT_SIZE = 10;
/**
* array size
*/
private int size = 0;
/**
* array
*/
private T[] array = (T[]) new Object[DEFAULT_SIZE];
/**
* add element
*
* @param element
* @return
*/
@Override
public boolean add(T element) {
return add(size, element);
}
/**
* add element at index
*
* @param index
* @param element
* @return
*/
@Override
public boolean add(int index, T element) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// need grow
if (size >= array.length) {
grow();
}
// copy array element
if (index < size) {
System.arraycopy(array, index, array, index + 1, size - index);
}
array[index] = element;
size++;
return true;
}
/**
* grow 50%
*/
private void grow() {
int growSize = size + (size >> 1);
array = Arrays.copyOf(array, growSize);
}
/**
* remove element
*
* @param element
* @return
*/
@Override
public boolean remove(T element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (array[i] == null) {
remove(i);
return true;
}
} else {
if (array[i].equals(element)) {
remove(i);
return true;
}
}
}
return false;
}
/**
* remove element by index
*
* @param index
* @return
*/
@Override
public T remove(int index) {
checkPositionIndex(index);
T oldElement = array[index];
// need copy element
if (index != (size - 1)) {
System.arraycopy(array, index + 1, array, index, size - index - 1);
}
--size;
array[size] = null;
// shrink 25%
int shrinkSize = size - (size >> 2);
if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
shrink();
}
return oldElement;
}
/**
* shrink 25%
*/
private void shrink() {
int shrinkSize = size - (size >> 2);
array = Arrays.copyOf(array, shrinkSize);
}
/**
* set element by index
*
* @param index
* @param element
* @return
*/
@Override
public T set(int index, T element) {
checkPositionIndex(index);
T oldElement = array[index];
array[index] = element;
return oldElement;
}
/**
* get element by index
*
* @param index
* @return
*/
@Override
public T get(int index) {
checkPositionIndex(index);
return array[index];
}
/**
* check index
*
* @param index
*/
private void checkPositionIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
/**
* clear list
*/
@Override
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
}
/**
* contain certain element
*
* @param element
*/
@Override
public boolean contains(T element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (array[i] == null) {
return true;
}
} else {
if (array[i].equals(element)) {
return true;
}
}
}
return false;
}
/**
* get list size
*
* @return
*/
@Override
public int size() {
return size;
}
}
主要注意以下幾點(diǎn)：
- 添加元素時(shí) ，判斷是否需要對(duì)Array進(jìn)行擴(kuò)容店雅；
- 刪除元素時(shí)政基，判斷是否需要對(duì)Array進(jìn)行收縮；
- remove與contains接口闹啦，注意element為null的情況腋么；
特點(diǎn)
- 對(duì)數(shù)據(jù)進(jìn)行遍歷的時(shí)候，數(shù)據(jù)在連續(xù)的物理空間中進(jìn)行存放亥揖，CPU的內(nèi)部緩存結(jié)構(gòu)會(huì)緩存連續(xù)的內(nèi)存片段珊擂，可以大幅降低讀取內(nèi)存的性能開銷圣勒，所以查詢比較快；
- 刪除線性表中的元素的時(shí)候摧扇，后面的元素會(huì)整體向前移動(dòng)圣贸，所以刪除的效率較低，插入類似扛稽，時(shí)間復(fù)雜度為O(n)吁峻；
