当前位置：首页 > news >正文

ArrayList与顺序表

news 2025/11/29 13:57:43

1. 线性表

2. 顺序表

3. ArrayList

3.1 subList方法

3.2 ArrayList的遍历

3.3 ArrayList的扩容机制

4. 删除两字符串重复部分

5. 杨辉三角

6. 简单的洗牌算法

7. ArrayList的问题及思考

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就是说是连续的一条直线，但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

2. 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删改查

3. ArrayList

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

3.1 subList方法

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {ArrayList<String> list = new ArrayList<String>();//通过list这个引用可以调用当前类的所有可以被调用的方法List<String> list1 = new ArrayList<String>();//只要实现这个接口的都能引用，向上转型//通过这个接口，只能调用这个接口当中的方法list.add("a");list.add("b");list.add("c");list.add("d");list.add("e");list.add("f");list.add("g");List<String> list2=list.subList(1,3);System.out.println(list2);//[b, c]System.out.println("==============");list2.set(0,"y");System.out.println(list2);//[y, c]System.out.println(list);//[a, y, c, d, e, f, g]（这里强调没有创建新的对象，而是对原本对象直接进行修改）}
}

3.2 ArrayList的遍历

使用迭代器输出元素：

        Iterator<String> iterator = list.iterator();while (iterator.hasNext()) {System.out.print(iterator.next()+" ");//a y c d e f g }System.out.println();

使用迭代器逆向输出元素：

        ListIterator<String> listIterator = list.listIterator(list.size());while (listIterator.hasPrevious()) {System.out.print(listIterator.previous() + " ");//g f e d c y a (倒着打印)}System.out.println();

3.3 ArrayList的扩容机制

检测是否真正需要扩容，如果是调用grow准备扩容
预估需要库容的大小：初步预估按照1.5倍大小扩容，如果所需大小超过1.5倍，则按照实际大小扩容，扩容之前检测是否能扩容成功，防止太大导致扩容失败
使用copyOf进行扩容

4. 删除两字符串重复部分

import java.util.ArrayList;public class Test {public static void main(String[] args) {String list1 = "welcome to bit";String list2 = "come";ArrayList<Character> ret = new ArrayList<>();for (int i = 0; i < list1.length(); i++) {char c = list1.charAt(i);if (!list2.contains(c + "")) {//此处为字符串ret.add(c);}}for (Character c : ret) {System.out.print(c + "");//wl t bit}}
}

5. 杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<>();for (int j = 0; j < i + 1; j++) {int val = (j == 0 || j == i) ? 1 : (ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));row.add(val);}ret.add(row);}return ret;}
}

6. 简单的洗牌算法

Card类：

public class Card {private String suit;private 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;}
}

CardDemo类：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class CardDemo {public static final String[] suits = {"♦", "♥", "♠", "♣"};public List<Card> buyCard() {List<Card> cards = new ArrayList<Card>();for (int i = 1; i < 13; i++) {for (int j = 0; j < 4; j++) {int rank = i;String suit = suits[j];Card card = new Card(suit, rank);cards.add(card);}}return cards;}public void shuffle(List<Card> cards) {Random random = new Random();for (int i = cards.size() - 1; i > 0; i--) {int index = random.nextInt(i);swap(cards, index, i);}}private void swap(List<Card> cards, int i, int j) {Card temp = cards.get(i);cards.set(i, cards.get(j));cards.set(j, temp);}public List<List<Card>> play(List<Card> cards) {List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> hand = new ArrayList<>();hand.add(hand0);hand.add(hand1);hand.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cards.remove(0);hand.get(j).add(card);}}return hand;}
}

Test类：

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();List<Card> cardList = cardDemo.buyCard();//买牌System.out.println(cardList);cardDemo.shuffle(cardList);//洗牌System.out.println(cardList);List<List<Card>> ret = cardDemo.play(cardList);for (int i = 0; i < ret.size(); i++) {System.out.print("  NO" + (i + 1) + ":" + ret.get(i));}}public static void main1(String[] args) {String list1 = "welcome to bit";String list2 = "come";ArrayList<Character> ret = new ArrayList<>();for (int i = 0; i < list1.length(); i++) {char c = list1.charAt(i);if (!list2.contains(c + "")) {//此处为字符串ret.add(c);}}for (Character c : ret) {System.out.print(c + "");//wl t bit}}
}