【数据结构】--ArrayList与顺序表

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表的底层是一个数组。顺序表是一个新的类型，最终的操作确实是在操作数组，但是它是一个新的类型。

3. ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口
【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

4. MyArrayList的实现

MyArrayList类：

public class MyArrayList implements IList{public int[] elem;public int usedSize;//记录当前的有效数据个数public MyArrayList(){this.elem = new int[10];}/*** 把data放在数组中 有效数据的最后一个位置* @param data*/@Overridepublic void add(int data) {//如果数组满了--->扩容if (ifFull()){resize();}else {elem[usedSize] = data;usedSize++;}}//扩容数组private void resize(){//二倍扩容elem = Arrays.copyOf(elem,2*elem.length);}/*** 将数据data插入到指定的pos位置* @param pos* @param data*/@Overridepublic void add(int pos, int data) {//如果输入的下标不合理if(pos<0 || pos>usedSize){throw new PosOutOfException("pos位置不合法");}//判满if(ifFull()){//扩容resize();}//将pos位置及后面的元素整体向后挪动int i = usedSize-1;while(i>=pos){elem[i+1] = elem[i];i--;}elem[pos] = data;usedSize++;}/***判断数组中是否有数据toFind* @param toFind* @return*/@Overridepublic boolean contains(int toFind) {if (isEmpty()){return false;}for (int i = 0; i < usedSize; i++) {if (elem[i]==toFind){return true;}}return false;}/*** 找到数据toFind 并返回该数据的下标* @param toFind* @return*/@Overridepublic int indexOf(int toFind) {if (isEmpty()){return -1;}for (int i = 0; i < usedSize; i++) {if (elem[i]==toFind){return i;}}return -1;}/*** 获取pos下标的数据* @param pos* @return*/@Overridepublic int get(int pos) {//考虑pos的合法性if(pos<0 || pos>=usedSize){throw new PosOutOfException("pos位置不合法！");}return elem[pos];}/*** 更新pos下标的值为value* @param pos* @param value*/@Overridepublic void set(int pos, int value) {//pos的合法性if(pos < 0 || pos >= usedSize){throw new PosOutOfException("pos位置不合法！");}elem[pos] = value;}/*** 删除数据toRemove* @param toRemove*/@Overridepublic void remove(int toRemove) {//找到toRemove数据int pos = indexOf(toRemove);if (pos>=0){//将toRemove后面的数据整体往前移动(将toRemove数据覆盖住相当于将其删除）for (int i = pos; i < usedSize-1 ; i++) {elem[i] = elem[i+1];}usedSize--;}}/***获取当前数组的有效数据个数* @return*/@Overridepublic int size() {return this.usedSize;}/***清空数组*/@Overridepublic void clear() {this.usedSize=0;}/***输出当前数据的所有数据*/@Overridepublic void display() {for (int i = 0; i < usedSize; i++) {System.out.print(elem[i] + " ");}System.out.println();}/*** 判满* @return*/@Overridepublic boolean ifFull() {return usedSize==elem.length;}/***判空* @return*/@Overridepublic boolean isEmpty() {return usedSize==0;}
}

IList接口：

public interface IList {// 新增元素,默认在数组最后新增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();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();//判断数组是不是满了boolean ifFull();//判断数组的有效数据是否为空boolean isEmpty();
}

自定义的PosOutOfException异常：

public class PosOutOfException extends RuntimeException{public PosOutOfException(){}public PosOutOfException(String msg){super(msg);}
}

Test类：

public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.add(3,4);System.out.println(myArrayList.contains(2));//trueSystem.out.println(myArrayList.indexOf(2));//1System.out.println(myArrayList.get(1));//2myArrayList.set(1,11);myArrayList.remove(11);myArrayList.display();// 1 3 4myArrayList.clear();}
}

问：如果现在usedSize是3，可以指定插入下标4位置吗？

答：不可以，插入数据时，必须要有一个唯一的前驱，不可以跳着插入。

5. ArrayList使用

---

5.1 ArrayList的构造

方法	解释
ArrayList()	无参构造
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

public static void main(String[] args) {// ArrayList创建，推荐写法// 构造一个空的列表List<Integer> list1 = new ArrayList<>();// 构造一个具有10个容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hello");  // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素// list3构造好之后，与list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难List list4 = new ArrayList();list4.add("111");list4.add(100);}

5.2 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 subList(int fromIndex, int toIndex)	截取部分 list

上面是我们自己实现的一个ArrayList，在Java中有现成的ArrayList，可以直接拿来使用。

Mian类：

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);ArrayList<Integer> list1 = new ArrayList<>();list1.add(111);list1.add(222);list1.add(333);list.addAll(list1);//表示将list1中的所有数据都添加在list上System.out.println(list);//[11, 22, 33, 111, 222, 333]}
}

方法boolean addAll(Collection<? extends E> c)中的Collection<? extends E> 是参数c的类型，可以看出来这个类型是一个泛型类，这个泛型类的上界E指的是当前的List所指定的类型（Interger），？表示当前List1的类型，用Collection类型来接收，因为所有的泛型类都继承Collection。这里就表示传入的参数c的类型是不是E的类型或者E的类型的子类（List1的类型是不是List的类型，或者List类型的子类）。

这里的List1的类型是Integer，是List的类型，所以能够传入成功。

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);ArrayList<String> list2 = new ArrayList<>();list2.add("hello");list2.add("world");list.addAll(list2);//报错System.out.println(list);}
}

输出结果：

java: 不兼容的类型: java.util.ArrayList<java.lang.String>无法转换为java.util.Collection<? extends java.lang.Integer>

这里传入失败的原因就是因为List2的类型是String，它不是List类型Integer，也不是Interger的子类。

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);list.add(44);list.remove(1);//删除1下标的值System.out.println(list);}
}

输出结果：

[11, 33, 44]

---

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);list.add(44);list.remove(new Integer(11));//删除数据11，相当于传的是一个对象System.out.println(list);}
}

输出结果：

[22, 33, 44]

在list.remove(new Integer(11));中Integer下面会画红线。

---

Main类：

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);list.add(44);System.out.println(list);List<Integer> listTemp = list.subList(1,3);//表示截取List中的[1,3)下标的数据System.out.println(listTemp);}
}

输出结果：

[11, 22, 33, 44]
[22, 33]

---

Main类：

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);list.add(44);System.out.println(list);List<Integer> listTemp = list.subList(1,3);//表示截取List中的[1,3)下标的数据System.out.println(listTemp);System.out.println("==============================");listTemp.set(1,222);//表示将listTemp中1下标的值修改为222listTemp.set(0,99);System.out.println("list: "+list);System.out.println("listTemp: " + listTemp);}
}

输出结果：

[11, 22, 33, 44]
[22, 33]
==============================
list: [11, 99, 222, 44]
listTemp: [99, 222]

subList()方法并不是把相应的数据截取出来产生新的对象，而是返回了list 中1下标数据的地址，所以修改listTemp也会影响到list

5.3 ArrayList的遍历

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22);list.add(33);list.add(44);System.out.println("=========sout直接输出=========");System.out.println(list);System.out.println("========for循环遍历===========");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();System.out.println("=========for each循环遍历===========");for (Integer x:list) {System.out.print(x +" ");}System.out.println();System.out.println("===========迭代器遍历1==========");Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()){System.out.print(iterator.next()+ " ");}System.out.println();System.out.println("===========迭代器遍历2==========");ListIterator<Integer> listIterator = list.listIterator();//默认从下标0开始打印while (listIterator.hasNext()){System.out.print(listIterator.next() + " ");}System.out.println();}
}

输出结果：

=========sout直接输出=========
[11, 22, 33, 44]
========for循环遍历===========
11 22 33 44 
=========for each循环遍历===========
11 22 33 44 
===========迭代器遍历1==========
11 22 33 44 
===========迭代器遍历2==========
11 22 33 44 

返回值是一个Iterator对象。

相当于iteerator这个迭代器对象去判断有没有下一个，如果有就去打印，iterator.next()，有两个动作，打印下一个的同时让iterator走到下一个。

ListIterator是Interator的子类，ListIterator只能用来接收List。相当于ListIterator是List相关的迭代器。

ListIterator是Interator的子类，ListIterator拓展了一些功能：从后往前打印。

public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(11);list.add(22); list.add(33);list.add(44);System.out.println("===========迭代器遍历3=========");ListIterator<Integer> listIterator1 = list.listIterator(list.size());//从最后一个有效数据开始打印while (listIterator1.hasPrevious()){System.out.print(listIterator1.previous() + " ");}System.out.println();}
}

输出结果：

===========迭代器遍历3=========
44 33 22 11 

5.4 ArrayList的扩容机制

下面代码有缺陷吗？为什么？

public static void main(String[] args) {List<Integer> list = new ArrayList<>();for (int i = 0; i < 100; i++) {list.add(i);}
}

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

Object[] elementData;   // 存放元素的空间private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认空间private static final int DEFAULT_CAPACITY = 10;  // 默认容量大小public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// 获取旧空间大小int oldCapacity = elementData.length;// 预计按照1.5倍方式扩容int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 调用copyOf扩容elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0，抛出OutOfMemoryError异常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

当我们调用不带参数的构造方法时，第一次进行add元素的时候，会为底层的数组进行内存的分配，此时的大小为10。

6. ArrayList的具体使用

---

6.1 简单的洗牌算法

Card类：

public class Card {public String suit;//花色public int rank;//牌面值public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {/*return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return "{ "+suit + rank + " }";}
}

Game类：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;/*** Created with IntelliJ IDEA.* Description:* User: Lenovo* Date: 2024-11-25* Time: 20:56*/
public class Game {public static final String[] SUITS = {"♥","♠","♦","♣"};/*** 生成52张牌，每一种花色有13张牌* @return*/public List<Card> creatCards(){ArrayList<Card> cardsList = new ArrayList<>();for (int i = 0; i < SUITS.length; i++) {for (int j = 1; j <= 13; j++) {String suit = SUITS[i];int rank = j;Card card = new Card(suit, rank);cardsList.add(card);}}return cardsList;}/*** 洗牌* 下标之间随机进行交换* @param cardList*/public void shuffle(List<Card> cardList){Random random = new Random();for (int i = cardList.size()-1; i > 0 ; i--) {int randIndex = random.nextInt(i);//生成[0,i)的随机数swap(cardList, i, randIndex);}}/*** 交换两张牌* @param cardList* @param i* @param j*/private void swap(List<Card> cardList, int i, int j){Card temp = cardList.get(i);cardList.set(i, cardList.get(j));cardList.set(j, temp);}/*** 玩牌* 三个人，每个人轮流抓，一共抓5张牌，相当于每个人共5张牌* @param cardList*/public List<List<Card>> play(List<Card> cardList){List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> handList = new ArrayList<>();handList.add(hand0);handList.add(hand1);handList.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < handList.size(); j++) {Card card = cardList.remove(0);handList.get(j).add(card);}}return handList;}
}

Test类：

import java.util.List;
import java.util.ListIterator;/*** Created with IntelliJ IDEA.* Description:* User: Lenovo* Date: 2024-11-25* Time: 20:55*/
public class Test {public static void main(String[] args) {Game game = new Game();List<Card> cardList = game.creatCards();System.out.println(cardList);System.out.println("=============================================================================================");game.shuffle(cardList);System.out.println(cardList);System.out.println("=============================================================================================");List<List<Card>> handList = game.play(cardList);for (int i = 0; i < handList.size(); i++) {System.out.println("第" +(i+1) + "个人的牌是：" + handList.get(i));}System.out.println("=============================================================================================");System.out.println("剩下的牌:" + cardList);}
}

输出结果：

[{ ♥1 }, { ♥2 }, { ♥3 }, { ♥4 }, { ♥5 }, { ♥6 }, { ♥7 }, { ♥8 }, { ♥9 }, { ♥10 }, { ♥11 }, { ♥12 }, { ♥13 }, { ♠1 }, { ♠2 }, { ♠3 }, { ♠4 }, { ♠5 }, { ♠6 }, { ♠7 }, { ♠8 }, { ♠9 }, { ♠10 }, { ♠11 }, { ♠12 }, { ♠13 }, { ♦1 }, { ♦2 }, { ♦3 }, { ♦4 }, { ♦5 }, { ♦6 }, { ♦7 }, { ♦8 }, { ♦9 }, { ♦10 }, { ♦11 }, { ♦12 }, { ♦13 }, { ♣1 }, { ♣2 }, { ♣3 }, { ♣4 }, { ♣5 }, { ♣6 }, { ♣7 }, { ♣8 }, { ♣9 }, { ♣10 }, { ♣11 }, { ♣12 }, { ♣13 }]
=============================================================================================
[{ ♥13 }, { ♥5 }, { ♠6 }, { ♥2 }, { ♥11 }, { ♦4 }, { ♦11 }, { ♦12 }, { ♥3 }, { ♣10 }, { ♠13 }, { ♦8 }, { ♦6 }, { ♥12 }, { ♣5 }, { ♠2 }, { ♦3 }, { ♠8 }, { ♠5 }, { ♣11 }, { ♥6 }, { ♥1 }, { ♣3 }, { ♦5 }, { ♣8 }, { ♣12 }, { ♠11 }, { ♥8 }, { ♣6 }, { ♥4 }, { ♦10 }, { ♠4 }, { ♦1 }, { ♦9 }, { ♠10 }, { ♣9 }, { ♣4 }, { ♠9 }, { ♥9 }, { ♥7 }, { ♠3 }, { ♣1 }, { ♦7 }, { ♠7 }, { ♦13 }, { ♦2 }, { ♣2 }, { ♣7 }, { ♣13 }, { ♠1 }, { ♥10 }, { ♠12 }]
=============================================================================================
第1个人的牌是：[{ ♥13 }, { ♥2 }, { ♦11 }, { ♣10 }, { ♦6 }]
第2个人的牌是：[{ ♥5 }, { ♥11 }, { ♦12 }, { ♠13 }, { ♥12 }]
第3个人的牌是：[{ ♠6 }, { ♦4 }, { ♥3 }, { ♦8 }, { ♣5 }]
=============================================================================================
剩下的牌:[{ ♠2 }, { ♦3 }, { ♠8 }, { ♠5 }, { ♣11 }, { ♥6 }, { ♥1 }, { ♣3 }, { ♦5 }, { ♣8 }, { ♣12 }, { ♠11 }, { ♥8 }, { ♣6 }, { ♥4 }, { ♦10 }, { ♠4 }, { ♦1 }, { ♦9 }, { ♠10 }, { ♣9 }, { ♣4 }, { ♠9 }, { ♥9 }, { ♥7 }, { ♠3 }, { ♣1 }, { ♦7 }, { ♠7 }, { ♦13 }, { ♦2 }, { ♣2 }, { ♣7 }, { ♣13 }, { ♠1 }, { ♥10 }, { ♠12 }]

6.2 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:
输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

OJ链接

示例：

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<>();//第一行List<Integer> ret0 = new ArrayList<>();ret0.add(1);list.add(ret0);//每一行for (int i = 1; i < numRows; i++) {List<Integer> ret = new ArrayList<>();//每一行的第一个数据ret.add(1);//每一行中的中间数据for (int j = 1; j <= i-1; j++) {ret.add(list.get(i-1).get(j)+list.get(i-1).get(j-1));}//每一行的最后一个数据ret.add(1);list.add(ret);}return list;}
}