目录
1.前言
通过上篇博客的介绍，我们初步认识数据结构的基本知识，接下来与大家分享关于ArrayList与顺序表的相关知识。ArrayList是数组链表，也就是我们经常所说的顺序表。它是Java内置的，让我们更加方便地编写代码，下面我们就一起来了解ArrayList与顺序表的相关知识。
2.顺序表
顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。2.1定义一个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位置的元素设为value，相当于更新
void set(int pos, int value);
//删除第一次出现的关键字key
void remove(int toRemove);
//，获取顺序表的长度
int size();
//清空顺序表
void clear();
//打印顺序表，注意：该方法不是顺序表中的方法，为了方便看测试结果
void display();
//判断数组是否已满
boolean isFull();
}
上面就是我们自己写的一个简单ArrayList的接口。
2.2实现接口功能
package arraylist;
import java.util.Arrays;
public class MyArrayList implements IList {
public int[] elem;
public int usedSize;
public MyArrayList() {
this.elem = new int[10];
}
@Override
public void add (int data) {
if (isFull()) {
//数组满了对数组进行扩容
elem = Arrays.copyOf(elem, 2 * elem.length);
}
this.elem[usedSize] = data;
this.usedSize++;
}
@Override
public void add(int pos, int data) {
try {
checkPos(pos);
} catch (PosNotLegalException e) {
e.printStackTrace();
}
if (isFull()) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
//移到元素
for (int i = usedSize - 1; i >= pos; i--) {
elem[i + 1] = elem[i];
}
//插入元素
elem[pos] = data;
usedSize++;
}
//判断添加元素时pos是否合法
private void checkPos(int pos) throws PosNotLegalException {
if (pos < 0 || pos > usedSize) {
throw new PosNotLegalException("add插入元素时，pos位置不合法！");
}
}
//需要寻找usedSize次
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (elem[i] == toFind) {
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (elem[i] == toFind) {
return i;
}
}
return -1;
}
@Override
public int get(int pos) {
try {
checkPosOfGetAndSet(pos);
} catch (PosNotLegalException e) {
e.printStackTrace();
}
return elem[pos];
}
private void checkPosOfGetAndSet(int pos) throws PosNotLegalException {
if (pos < 0 || pos >= usedSize) {
throw new PosNotLegalException("get或者set获取元素时，pos位置不合法！");
}
}
@Override
public void set(int pos, int value) {
try {
checkPosOfGetAndSet(pos);
} catch (PosNotLegalException e) {
e.printStackTrace();
}
elem[pos] = value;
}
@Override
public void remove(int toRemove) {
//1.要检查是否存在要删除的关键字 toRemove
int pos = indexOf(toRemove);
if (pos == -1) {
System.out.println("没有要删除的数字！");
return;
}
for (int i = pos; i < usedSize - 1; i++) {
elem[i] = elem[i + 1];
}
usedSize--;
}
@Override
public int size() {
return usedSize;
}
@Override
public void clear() {
usedSize = 0;
}
@Override
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
@Override
public boolean isFull() {
return this.usedSize == elem.length;
}
}
2.3自定义异常类
package arraylist;
public class PosNotLegalException extends RuntimeException {
public PosNotLegalException() {
}
public PosNotLegalException(String msg) {
super(msg);
}
}
2.4主程序代码
package arraylist;
import java.util.List;
public class Test {
public static void main(String[] args) {
//两种实例化
IList iList = new MyArrayList();
//MyArrayList myArrayList = new MyArrayList();
iList.add(1);
iList.add(2);
iList.add(30);
//iList.add(1,88);
iList.display();
iList.remove(2);
iList.display();
}
}运行结果：
这就是我们自己写的一个简单的顺序表功能，在Java中内置了ArrayList，具有我们刚刚写的顺序表的功能，而且还为我们提供其他更加强大的功能。
3.ArrayList
3.1ArrayList简介
在集合框架中， ArrayList 是一个普通的类，实现了 List 接口，具体框架图如下：
Tips：
1. ArrayList 是以泛型方式实现的，使用时必须要先 实例化 ； 2. ArrayList 实现了 RandomAccess 接口，表明 ArrayList支持随机访问 ； 3. ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的； 4. ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的； 5. 和 Vector 不同， ArrayList 不是线程安全的，在 单线程下可以使用 ，在多线程中可以选择 Vector 或者CopyOnWriteArrayList； 6. ArrayList 底层是一段连续的空间，并且可以 动态扩容 ，是一个动态类型的顺序表。
3.2ArrayList的构造
| 方法 | 解释 |
| 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);3.3ArrayList常见操作
| 方法 | 解释 |
| 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 |
3.4ArrayList的遍历
ArrayList 可以使用三方方式遍历： for循环+ 下标、 foreach 、使用迭代器。import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
System.out.println(list);
//使用for循环遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
//使用foreach遍历
for (Integer x:list) {
System.out.print(x + " ");
}
System.out.println();
//使用迭代器遍历
Iterator<Integer> l = list.listIterator();
while(l.hasNext()) {
System.out.print(l.next() + " ");
}
System.out.println();
}
}
运行结果如下：
4.ArrayList的具体使用
4.1简单的洗牌算法
public class Card {
public int rank;//数字
public String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
@Override
public String toString() {
return "{" + suit + " " + rank + "}";
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Cards {
public static final String[] suits = {"♥", "♠", "♣", "♦"};
//4个花色 13张牌
public List<Card> buyCard() {
List<Card> cardList = new ArrayList<>();
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= 13; j++) {
int rank = j;
String suit = suits[i];
Card card = new Card(rank, suit);
cardList.add(card);
}
}
return 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);
swap(cardList, i, randIndex);
}
}
private void swap(List<Card> cardList, int i, int j) {
//Card tmp =cardList[i];
Card tmp = cardList.get(i);
//cardList[i]=cardList[j];
cardList.set(i, cardList.get(j));
//cardList[j]=tmp;
cardList.set(j, tmp);
}
//3个人，每次轮流抓5张牌
public void drawCard(List<Card> cardList) {
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
List<Card> hand3 = new ArrayList<>();
List<List<Card>> hands = new ArrayList<>();
hands.add(hand1);
hands.add(hand2);
hands.add(hand3);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
Card card = cardList.remove(0);
List<Card> tmpHand = hands.get(j);
tmpHand.add(card);
}
}
System.out.println("小明抓的牌" + hand1);
System.out.println("小欣抓的牌" + hand2);
System.out.println("小美抓的牌" + hand3);
}
}import java.util.List;
public class TestCard {
public static void main(String[] args) {
Cards cards = new Cards();
List<Card> cardList = cards.buyCard();
System.out.println("刚买回来的牌");
System.out.println(cardList);
cards.Shuffle(cardList);
System.out.println("洗牌之后：");
System.out.println(cardList);
System.out.println("抓牌：");
cards.drawCard(cardList);
System.out.println("剩下的牌：");
System.out.println(cardList);
}
}
运行结果如下：
4.2杨辉三角
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> generate1(int numRows) {
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<Integer>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(list.get(i - 1).get(j - 1)
+ list.get(i - 1).get(j));
}
}
list.add(row);
}
return list;
}
public List<List<Integer>> generate2(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
//第一行数据为1
List<Integer> list =new ArrayList<>();
list.add(1);
ret.add(list);
//从第2行开始，计算每个list当中的数据
for (int i = 1; i < numRows; i++) {
List<Integer> curRow =new ArrayList<>();
//每一行第一个数据都为1
curRow.add(1);
for (int j = 1; j < i; j++) {
//获取上一行的数据
List<Integer> preRow = ret.get(i-1);
int x1 = preRow.get(j);
int x2 =preRow.get(j-1);
curRow.add(x1+x2);
}
//当前行最后一个数据为1
curRow.add(1);
ret.add(curRow);
}
return ret;
}
}
public class Demo1_10 {
//杨辉三角
//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
public static void main(String[] args) {
Solution solution =new Solution();
//System.out.println(solution.generate2(5));
List<List<Integer>> lst = solution.generate1(5);
for (int i = 0; i < lst.size(); i++) {
for (int j = 0; j < lst.get(i).size(); j++) {
System.out.print(lst.get(i).get(j) + " ");
}
System.out.println();
}
}
}运行结果如下：
5.总结
ArrayList具有以下的优缺点：
优点：根据指定下标去查找元素或更新元素的效率很高，时间复杂度为O(1)。
缺点：在插入或删除数据时，不仅每一次都需要移动数据，如果要把数据插到0下标位置或删除0下标的数据，时间复杂度为O(n)，而且在扩容的时候，默认是扩容1.5倍，当扩容空间只使用了一点时，会白白浪费许多空间。
如果经常要进行查找元素或更新元素，顺序表便能大展身手，若在任意位置插入和删除比较多的场景下，ArrayList效率比较低，这时候就需要用到链表。
标签：顺序,int,ArrayList,List,pos,add,数据结构,public From： https://blog.csdn.net/m0_74336101/article/details/140557197