數據結構*集合框架順序表-ArrayList

集合框架

常見的集合框架
在這里插入圖片描述

什么是順序表

順序表是一種線性表數據結構，它借助一組連續的存儲單元來依次存儲線性表中的數據元素。一般情況下采用數組存儲。在數組上完成數據的增刪查改。

自定義簡易版的順序表

代碼展示：

public interface IArrayList {//新增元素,默認在數組最后新增void add(int data);//在 pos 位置新增元素void add(int pos, int data);//判定是否包含某個元素boolean contains(int toFind);//查找某個元素對應的位置int indexOf(int toFind);//獲取 pos 位置的元素int get(int pos);//給 pos 位置的元素設為 valuevoid set(int pos, int value);//刪除第?次出現的關鍵字keyvoid remove(int toRemove);//獲取順序表?度int size();//清空順序表void clear();
}

import java.util.Arrays;public class MyArrayList implements IArrayList {private int useSize;private int[] elem;public MyArrayList() {this.elem = new int[Constant.DEFAULT_CAPACITY];}@Override//新增元素,默認在數組最后新增public void add(int data) {//1、是否能繼續存放數據，不能就進行擴容if(isFill()) {grow();}//2、在數組末尾添加數據this.elem[useSize] = data;this.useSize++;}@Override//在 pos 位置新增元素public void add(int pos, int data) {//1、是不是滿的if(isFill()) {grow();}//2、檢查pos位置的合法性checkPosAdd(pos);//3、移動數據for (int i = useSize - 1; i >= pos ; i--) {elem[i+1] = elem[i];}/*if (useSize - pos >= 0) {System.arraycopy(elem, pos, elem, pos + 1, useSize - pos);}*/elem[pos] = data;useSize++;}private void checkPosAdd(int pos) {if(pos < 0 || pos > this.useSize) {throw new PosException(Constant.ADD_CHECK_MASSAGE);}}@Override//判定是否包含某個元素public boolean contains(int toFind) {for (int i = 0; i < this.useSize; i++) {if(elem[i] == toFind) {return true;}}return false;}@Override//查找某個元素對應的位置public int indexOf(int toFind) {for (int i = 0; i < this.useSize; i++) {if(elem[i] == toFind) {return i;}}return 0;}@Override//獲取 pos 位置的元素public int get(int pos) {//1、判斷順序表是否為空if(isEmpty()) {throw new isEmptyException(Constant.EMPTY_MASSAGE);}//2、判斷pos位置是否合法checkPos(pos);return elem[pos];}private void checkPos(int pos) {if(pos < 0 || pos >= this.useSize) {throw new PosException(Constant.GET_CHECK_MASSAGE);}}@Override//給 pos 位置的元素設為 valuepublic void set(int pos, int value) {if(isEmpty()) {throw new isEmptyException(Constant.EMPTY_MASSAGE);}checkPos(pos);elem[pos] = value;}@Override//刪除第?次出現的關鍵字keypublic void remove(int toRemove) {if(isEmpty()) {throw new isEmptyException(Constant.EMPTY_MASSAGE);}int index = indexOf(toRemove);if(index == -1) {System.out.println("沒有你要刪除的數據");return;}for (int i = index; i < this.useSize - 1; i++) {elem[i] = elem[i+1];}elem[useSize - 1] = 0;useSize--;}@Override//獲取順序表?度public int size() {return this.useSize;}@Override//清空順序表public void clear() {for (int i = 0; i < this.useSize; i++) {this.elem[i] = 0;}this.useSize = 0;}//是否為空private boolean isEmpty() {return useSize == 0;}//是否存滿private boolean isFill() {return this.useSize == this.elem.length;//判斷有效數據是否等于總數組長度}//數據擴容private void grow() {this.elem = Arrays.copyOf(this.elem,elem.length*2);}@Overridepublic String toString() {return Arrays.toString(elem);}
}

public class PosException extends RuntimeException{public PosException() {super();}public PosException(String message) {super(message);}
}

public class isEmptyException extends RuntimeException{public isEmptyException() {super();}public isEmptyException(String message) {super(message);}
}

public class Constant {public static final int DEFAULT_CAPACITY = 5;public static final String EMPTY_MASSAGE = "順序表為空";public static final String GET_CHECK_MASSAGE = "get方法的pos位置不合法";public static String ADD_CHECK_MASSAGE = "add方法的pos位置不合法";
}

public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(4);myArrayList.add(2,10);myArrayList.add(2,10);System.out.println(myArrayList.contains(9));System.out.println(myArrayList.get(0));myArrayList.set(1,20);myArrayList.remove(10);System.out.println(myArrayList.size());System.out.println(myArrayList);myArrayList.clear();System.out.println(myArrayList);}
}

代碼解釋：

1、定義了一個IArrayList接口，里面有需要實現的方法。
2、Constant類用來存放一些常量。
3、自定義了一個MyArrayList順序表。useSize表示數據中的有效長度，elem[]表示存儲數據的數組。在構造方法中初始化了數組的默認大小。實現了如下方法：

方法	功能
void add(int data)	新增元素，默認在數組最后面新增
void add(int pos,int data)	在pos位置新增元素
boolean contains(int toFind)	判斷是否包含某個元素
int indexOf(int toFind)	查找某個元素對應的位置
int get(int pos)	獲得pos位置的元素
void set(int pos,int value)	給pos位置的元素設為value
void remove(int toRemove)	刪除第一次出現的關鍵字toRemove
int size()	獲得順序表長度
void clear()	清空順序表
4、兩個自定義異常，分別表示數組中沒有元素、pos位置不合法。
5、對于數據結構來說是很嚴謹的，需要考慮各種情況。將可能發生的情況進行書寫。

官方定義的順序表-ArrayList

類的屬性

在這里插入圖片描述

構造方法

有三種構造方法

無參構造方法

在這里插入圖片描述

public static void test1() {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add("Hello");//報錯System.out.println(arrayList);List<String> list = new ArrayList<>();//向上轉型list.add("Hello");list.add("World");System.out.println(list);
}

此時new的是一個空的列表。arrayList已經限定為Integer類型，不能接收String類型。
對于add方法，查看源碼：
在這里插入圖片描述

grow方法就是擴容操作，完成的是1.5倍擴容。

指定順序表初始容量

在這里插入圖片描述

public static void test2() {ArrayList<Integer> arrayList = new ArrayList<>(20);arrayList.add(10);arrayList.add(20);arrayList.add(30);System.out.println(arrayList);
}

利用其他Collection構建ArrayList

在這里插入圖片描述

public static void test3() {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);System.out.println(arrayList);ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);arrayList1.add(10);System.out.println(arrayList1);ArrayList<Number> arrayList2 = new ArrayList<>(arrayList);arrayList2.add(100);System.out.println(arrayList2);System.out.println(arrayList1);ArrayList<String> stringArrayList = new ArrayList<>(arrayList);//報錯
}

輸出：
[1]
[1, 10]
[1, 100]
[1, 10]

說明這種構造方法是創建一個新（單獨）的列表，并繼承傳入的列表已有的值。

ArrayList常見操作

方法	功能
boolean add(E e)	尾插e
void add(int index,E element)	將e插入到index位置
boolean addAll(Collection<? extends E> c)	尾插c中的元素
E remove(int index)	刪除index位置元素
boolean remove(Object o)	刪除遇到的第一個o
E get(int index)	獲取下標index位置元素
E set(int index,E element)	將下標index位置元素設置為element（替換）
void clear()	清空
boolean contains(Object o)	判斷o是否在線性表中
int indexOf(Object o)	返回第一個o所在下標
int lastindexOf(Object o)	返回最后一個o所在下標
List<E> subList(int fromIndex,int toIndex)	截取部分list

代碼案例：

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(4,10);System.out.println(arrayList);//arrayList.add(6,10);//報錯，IndexOutOfBoundsExceptionArrayList<Integer> arrayList1 = new ArrayList<>();arrayList1.addAll(arrayList);System.out.println(arrayList1);arrayList1.add(5);System.out.println(arrayList);System.out.println("===========");arrayList.remove(4);System.out.println(arrayList);System.out.println("===========");Integer i = 4;arrayList.remove(i);System.out.println(arrayList);System.out.println("===========");System.out.println(arrayList.get(2));System.out.println("===========");arrayList.set(1,100);System.out.println(arrayList);System.out.println("===========");System.out.println(arrayList.contains(10));System.out.println("===========");ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);list.add(8);list.add(9);list.add(10);System.out.println(list);//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]List<Integer> sublist = list.subList(2, 7);System.out.println(sublist);//[3, 4, 5, 6, 7]sublist.set(0,100);System.out.println(sublist);//[100, 4, 5, 6, 7]System.out.println(list);//[1, 2, 100, 4, 5, 6, 7, 8, 9, 10]}
}

代碼解釋：

需要注意的是：
1、subList()方法截取的范圍是 [ fromeIndex,toIndex )
2、這里的截取并不是創建一個新的順序表，而是獲取原表上fromeIndex的地址。所以修改的是原表上的值。

ArrayList的遍歷

代碼案例：

public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println("--------for循環遍歷--------");for(int i = 0; i < list.size();i++) {System.out.print(list.get(i)+" ");}System.out.println();System.out.println("--------foreach循環遍歷--------");for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();System.out.println("--------迭代器正序輸出1--------");Iterator<Integer> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();System.out.println("--------迭代器正序輸出2--------");ListIterator<Integer> its = list.listIterator();while (its.hasNext()) {System.out.print(its.next()+" ");}System.out.println();System.out.println("--------迭代器正序輸出3（從指定下標位置輸出）--------");ListIterator<Integer> itss = list.listIterator(2);while (itss.hasNext()) {System.out.print(itss.next()+" ");}System.out.println();System.out.println("--------迭代器逆序輸出--------");ListIterator<Integer> reits = list.listIterator(list.size());while (reits.hasPrevious()) {System.out.print(reits.previous()+" ");}
}

輸出：
--------for循環遍歷--------
1 2 3 4 5 6 7
--------foreach循環遍歷--------
1 2 3 4 5 6 7
--------迭代器正序輸出1--------
1 2 3 4 5 6 7
--------迭代器正序輸出2--------
1 2 3 4 5 6 7
--------迭代器正序輸出3從指定下標位置輸出--------
3 4 5 6 7
--------迭代器逆序輸出--------
7 6 5 4 3 2 1

代碼解釋：

1、list.listIterator() 是調用 list 對象的方法來獲取一個列表迭代器。it.hasNext() 是判斷迭代器 it 是否還有下一個元素。it.next() 方法會返回迭代器指向的下一個元素（即列表中的下一個 Integer 元素）。
2、實現了Iterator接口就能使用迭代器進行打印。
3、ListIterator接口繼承了Iterator接口，也就是說有更多的方法。

嵌套列表

代碼案例

1、

public static void test() {List<List<Integer>> list = new ArrayList<>();List<Integer> list0 = new ArrayList<>();list0.add(10);list0.add(100);list0.add(1000);List<Integer> list1 = new ArrayList<>();list1.add(20);list1.add(200);List<Integer> list2 = new ArrayList<>();list2.add(30);list2.add(300);List<Integer> list3 = new ArrayList<>();list3.add(40);list3.add(400);list3.add(4000);List<Integer> list4 = new ArrayList<>();list4.add(50);list4.add(500);list.add(list0);list.add(list1);list.add(list2);list.add(list3);list.add(list4);for(int i = 0; i < list.size();i++) {for (int j = 0; j < list.get(i).size(); j++) {System.out.print(list.get(i).get(j)+" ");}System.out.println();}System.out.println();
}

輸出：
10 100 1000
20 200
30 300
40 400 4000
50 500

關系大致如圖所示：
在這里插入圖片描述
2、

public static List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();//定義起始行List<Integer> list0 = new ArrayList<>();list0.add(1);ret.add(list0);//定義后面的行for (int i = 1; i < numRows; i++) {//定義每行列表List<Integer> currentRow = new ArrayList<>();//第一個元素都是1currentRow.add(1);//中間操作List<Integer> preRow = ret.get(i - 1);for (int j = 1; j < i; j++) {//按照規律添加元素currentRow.add(preRow.get(j) + preRow.get(j-1));}//每行最后一個元素都是1currentRow.add(1);//currentRow行存儲到ret中ret.add(currentRow);}return ret;
}public static void main(String[] args) {List<List<Integer>> list = generate(5);for (List<Integer> integers : list) {for (Integer integer : integers) {System.out.print(integer + " ");}System.out.println();}System.out.println();
}