跳到主要内容Java 数据结构:ArrayList 与顺序表详解 | 极客日志Javajava算法
Java 数据结构:ArrayList 与顺序表详解
介绍 Java 中 ArrayList 与顺序表的基础知识。涵盖 ArrayList 的构造方式、常见操作(增删改查、遍历)、扩容机制,并通过洗牌算法和杨辉三角实例演示具体应用。重点讲解 List 接口实现、迭代器原理及动态数组特性。
橘子海25K 浏览 一、顺序表
顺序表本质上和数组是差不多的,只不过数组只能访问或修改某个元素,而作为顺序表,需要实现更多的功能。
1.1. 接口的实现
public void add(int data) { }
public void add(int pos, int data) { }
public boolean contains(int toFind) { return true; }
public int indexOf(int toFind) { return -1; }
public int get(int pos) { return -1; }
public void set(int pos, int value) { }
public void remove(int toRemove) { }
public { ; }
{ }
int
size
()
return
0
public
void
clear
()
二、ArrayList 简介
2.1. ArrayList 的构造
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
ArrayList<String> arrayList1 = new ArrayList<>();
List<String> list = new ArrayList<>();
}
}
其中 ArrayList 里面,也是实现了 List 的接口。也就是说,我们完全可以通过向上转型,把 List 引用指向 ArrayList 的实例。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
我们来看下面两段代码,两个都是构造空的顺序表,二者有什么区别呢?第一个是创建了一个盒子,盒子里面为空,而第二个却连盒子都没有。
ArrayList<String> arrayList1 = new ArrayList<>();
ArrayList<String> arrayList2 = null;
ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);
ArrayList<String> arrayList4 = new ArrayList<>(10);
当前构造出来的 ArrayList 初始容量为 10,这里与数组的区别是:数组我们在一开始就规定好了它的容量,不能在进行修改了;而 ArrayList 的容量可以进行动态扩容,只要机器内存允许,就能一直扩容,把想要的元素容纳进去。
2.2. ArrayList 的常见操作
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
System.out.println(list);
}
}
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
System.out.println(list.size());
}
}
事实上,不仅是 List,只要是集合类,都可以通过.size 来获取长度。
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(3));
}
}
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
list.set(0,"eee");
System.out.println(list);
}
}
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
for (String s : list) {
System.out.print(s+" ");
}
}
}
并不是所有的类都能写进 for-each 里面,要求这个类必须能够实现 Iterable 接口。实现 Iterable 接口中的 iterator 方法,得到一个迭代器对象,进行进一步循环遍历。
public interface List<E> extends Collection<E>
public interface Collection<E> extends Iterable<E>
迭代也是计算机中的专业术语,可以理解成'逐渐接近目标'。集合类中用到迭代。上面的 for-each 循环,我们可以看作是以下代码的简化。
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
hasNext 用于判断有没有下一个元素,iterator.next 用于取出当前元素,并准备下一个元素。
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ccc");
list1.add("ccc");
list1.add("ddd");
System.out.println(list1.contains("aaa"));
System.out.println(list1.indexOf("ccc"));
list1.lastIndexOf("ccc");
removeByElement(args);
removeByIndex(args);
addAtPosition(args);
}
public static void removeByElement(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ddd");
list1.remove("ddd");
System.out.println(list1);
}
public static void removeByIndex(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ddd");
list1.remove(2);
System.out.println(list1);
}
public static void addAtPosition(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ddd");
list1.add(1,"eee");
System.out.println(list1);
}
}
2.3. ArrayList 的扩容机制
当 ArrayList 内存不够时,就会自动申请额外的内存空间。ArrayList 内部持有一个数组,设置的初始容量相当于数组的大小。比如说我们初始容量为 10,当循环到第 11 次的时候,发现元素已经满了;add 真正写进元素之前,就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来,新的元素也要添加进新的数组里面,原来旧的数组要进行释放。
三、ArrayList 的具体使用
3.1. 洗牌算法
我们先来定义一个 Card 类,用来表示一张扑克牌。
class Card {
public String suit;
public String rank;
public Card(String suit, String rank) {
this.suit = suit;
this.rank = rank;
}
public String getSuit() { return suit; }
public void setSuit(String suit) { this.suit = suit; }
public String getRank() { return rank; }
public void setRank(String rank) { this.rank = rank; }
@Override
public String toString() { return this.suit+this.rank; }
}
接下来要先把 Card 这个对象实例化,并用 ArrayList 把所有的牌添加进去。
public class Main {
public static void main(String[] args) {
}
public static ArrayList<Card> CreateDeck() {
ArrayList<Card> deck = new ArrayList<>();
String[] suits = {"♠","♦","♥","♣"};
for (String suit:suits){
for (int i = 2; i <= 10; i++) {
Card cardNum = new Card(suit,""+i);
deck.add(cardNum);
}
Card cardJ = new Card(suit,"J");
Card cardQ = new Card(suit,"Q");
Card cardK = new Card(suit,"K");
Card cardA = new Card(suit,"A");
deck.add(cardJ);
deck.add(cardQ);
deck.add(cardK);
deck.add(cardA);
}
return deck;
}
}
然后我们调用 CreateDeck 方法,对这副牌进行一个打印。
public class Main {
public static void main(String[] args) {
ArrayList<Card> deck = CreateDeck();
System.out.println(deck);
}
}
接下来是进行洗牌的操作,在 Java 标准库中,提供了进行洗牌的方法 shuffle。
import java.util.Collections;
public class Main {
public static void main(String[] args) {
ArrayList<Card> deck = CreateDeck();
System.out.println("原始牌组:"+deck);
Collections.shuffle(deck);
System.out.println("洗牌之后:"+deck);
}
}
public static void shuffle(ArrayList<Card> deck){
Random random = new Random();
for (int i = deck.size() - 1; i >0 ; i--) {
int j = random.nextInt(deck.size());
Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());
deck.set(i, deck.get(j));
deck.set(j, tmp);
}
}
下面是发牌,一共有 3 个人,每个人发 5 张牌。我们可以看成一个 3 行 5 列的一个二维数组。
ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();
for (int i = 0; i < 3; i++) {
ArrayList<Card> hand = new ArrayList<>();
hands.add(hand);
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
ArrayList<Card> currentHand = hands.get(j);
Card card = deck.remove(0);
currentHand.add(card);
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
class Card {
public String suit;
public String rank;
public Card(String suit, String rank) {
this.suit = suit;
this.rank = rank;
}
public String getSuit() { return suit; }
public void setSuit(String suit) { this.suit = suit; }
public String getRank() { return rank; }
public void setRank(String rank) { this.rank = rank; }
@Override
public String toString() { return this.suit+this.rank; }
}
public class Main {
public static void main(String[] args) {
ArrayList<Card> deck = CreateDeck();
System.out.println("原始牌组:"+deck);
System.out.println("洗牌之后:"+deck);
ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();
for (int i = 0; i < 3; i++) {
ArrayList<Card> hand = new ArrayList<>();
hands.add(hand);
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
ArrayList<Card> currentHand = hands.get(j);
Card card = deck.remove(0);
currentHand.add(card);
}
}
for (int i = 0; i < 3; i++) {
System.out.println("第"+i+"个人的手牌"+hands.get(i));
}
}
public static void shuffle(ArrayList<Card> deck){
Random random = new Random();
for (int i = deck.size(); i >0 ; i--) {
int j = random.nextInt(deck.size());
Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());
deck.set(i, deck.get(j));
deck.set(j, tmp);
}
}
public static ArrayList<Card> CreateDeck() {
ArrayList<Card> deck = new ArrayList<>();
String[] suits = {"♠","♦","♥","♣"};
for (String suit:suits){
for (int i = 2; i <= 10; i++) {
Card cardNum = new Card(suit,""+i);
deck.add(cardNum);
}
Card cardJ = new Card(suit,"J");
Card cardQ = new Card(suit,"Q");
Card cardK = new Card(suit,"K");
Card cardA = new Card(suit,"A");
deck.add(cardJ);
deck.add(cardQ);
deck.add(cardK);
deck.add(cardA);
}
return deck;
}
}
3.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.第 i 行有 i+1 个列 (因为要用二维数组解决,所以把第一行定义第 0 行);2.每一行的第一列和最后一列都是 1;3.第 i 行第 j 列的元素 = 第 i-1 行第 j-1 列的元素 + 第 i-1 行第 j 列的元素。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i = 0; i < numRows; i++) {
List<Integer> rows = new ArrayList<>();
for (int j = 0; j < i+1; j++) {
if (j==0 || j==i){
rows.add(1);
} else {
List<Integer> prevRow = result.get(i - 1);
int current = prevRow.get(j - 1) + prevRow.get(j);
rows.add(current);
}
}
result.add(rows);
}
return result;
}
public static void main(String[] args) {
Main m = new Main();
Scanner num = new Scanner(System.in);
int b = num.nextInt();
List<List<Integer>> result = m.generate(b);
System.out.println(result);
}
}
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online