資料結構與演算法系列2 線性表 使用java實作動態陣列+ArrayList原始碼詳解
對陣列有不了解的可以先看看我的另一篇文章，那篇文章對陣列有很多詳細的決議，而本篇文章則著重講動態陣列，另一篇文章鏈接如下，可點擊跳轉：
鏈接：https://blog.csdn.net/pjh88/article/details/107166950
什么是陣列與動態陣列？
陣列
陣列是相同資料型別的元素按照一定的順序排列的集合，若將有限個型別相同的變數的集合命名，那么這個名稱稱為陣列名，組成陣列的各個變數稱為陣列的分量，也稱為陣列的元素，有時爺稱為下標變數，用于區分陣列的各個元素的陣列編號稱為下標，數是程式設計中，為了處理方便把具有相同型別的若干變數按有序的形式組織起來的一種形式，這些按序排序的同類元素的集合稱為陣列
動態陣列
顧名思義，動態陣列即可以動態擴容的陣列，一般的陣列是不能擴容的，及在創建陣列物件的時候就規定了陣列的大小，規定陣列是多大就是多大，后期不可以存盤多余的元素
動態陣列的好處也顯而易見：
1.動態的增加和減少元素
2.實作collection和list介面
3.靈活設定陣列的大小
java中已經給我們封裝好了一個動態陣列Arraylist的類，我們可以直接使用，其內部有許多方法，我們先來看看有什么方法，下面僅僅講我們經常使用到的方法那些不怎么使用的我們在這就不講了：
int size（）；元素的數量
boolean isEmpty（）；是否為空
boolean contains（E element); 判斷是否包含某個元素
void add（E element） ；添加元素到最后
E get（int index）；回傳index對應位置的元素
E set（int index，E element）；往index位置添加元素
void add（int index，E element）；往index位置添加元素
E remove（int index）； 洗掉index位置對應的元素
int indexOf（E element）； 查看元素的位置
void clear（）；清除所有元素
接下來我們逐一講解這些方法
定義的變數
//元素的數量
private int size;
//存盤元素
private E[] elements;
//初始化大小
private static final int DEFAULT_CAPACITY=16;
//元素沒有找到時的放回值
private static final int ELEMENT_NOT_FOUND=-1;
構造方法
//自定義大小
public ArrayList(int capacity){
//如果傳入的大小小于默認陣列的大小，則使用默認的大下
capacity= (capacity<DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;
elements=(E[])new Object[capacity];
}
//默認大小的構造方法
public ArrayList(){
this(DEFAULT_CAPACITY);
}
判斷index的范圍有沒有越界
public void rangeCheak(int index){
if (index<0||index>size){
outofBounds(index);
}
}
獲取指定位置的元素
public E get(int index){
rangeCheak(index);
return elements[index];
}
重新設定指定位置的元素
public E set(int index,E element){
//檢查插入位置是否合法
rangeCheak(index);
//回傳原來的元素
E oldelement1 = elements[index];
//插入新的元素
elements[index]=element;
return oldelement1;
}
判斷是否為空
public boolean isEmpty(){
return size==0;
}
回傳元素的數量
public int size(){
return size;
}
判斷是否包含某個指定元素
public boolean contains(E element){
return indexOf(element)!=ELEMENT_NOT_FOUND;
}
回傳指定元素的位置
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;
}
}
}
return ELEMENT_NOT_FOUND;
}
在末尾插入元素
public void add(E element){
add(size,element);}
在指定位置插入元素
public void add(int index,E element){
//檢查范圍
rangeCheakForadd(index);
//判斷容量是否足夠
ensureCapacity(size+1);
for (int i = size; i > index; i--) {
elements[i]=elements[i-1];
}
elements[index]=element;
size++;
}
檢查插入范圍
public void rangeCheakForadd(int index){
if (index<0||index>size){
outofBounds(index);
}
}
移除指定位置的元素
public E remove(int index){
//檢查范圍
rangeCheak(index);
E removeElement = elements[index];
for (int i=index+1;i<size;i++) {
elements[i-1]=elements[i];
}
elements[--size]=null;
return removeElement;
}
清除所有元素
public void clear(){
for (int i = 0; i < size; i++) {
elements[i]=null;
}
}
其實動態陣列最重要的一個方法就是擴容，下面來重點講解
public void ensureCapacity(int capacity){
int oldcapacity = elements.length;
//如果比原來小則不做改變
if (oldcapacity>= capacity){
return;
}
//使用位運算，速度更快
//我這里用的是二倍擴容，這里的擴容大小可以自己來設定，以達到最高的使用率
int newCapacity=oldcapacity+(oldcapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i]=elements[i];
}
//將elements的地址賦值新的地址
elements=newElements;
System.out.println(oldcapacity+"擴容為："+newCapacity);
}
復寫toString（)方法
@Override
public String toString(){
//使用StringBuilder
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append('[');
for (int i = 0; i < size; i++) {
if (i!=0){
stringBuilder.append(",");
}
stringBuilder.append(elements[i]);
}
stringBuilder.append(']');
return stringBuilder.toString();
}
以上就是對java動態陣列原始碼的決議，后面我會繼續更新其他知識，寫作不易，請各位老鐵點個贊支持一下，覺得有幫助的也可以收藏呀，我會經常更新文章，也可以關注我呀
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144610.html
標籤：其他
下一篇：MySql優化(二)范式與反范式