中英网站模板,上海网站制作服务,东莞人才市场招聘会,在线商城系统平台ArrayList与顺序表 1.线性表2.顺序表2.1 接口的实现 3. ArrayList简介4. ArrayList使用4.2 ArrayList常见操作4.3 ArrayList的遍历4.4 ArrayList的扩容机制 5. ArrayList的具体使用5.1 杨辉三角5.2 简单的洗牌算法 6. ArrayList的问题及思考 【本节目标】 线性表顺序表ArrayLis… ArrayList与顺序表 1.线性表2.顺序表2.1 接口的实现 3. ArrayList简介4. ArrayList使用4.2 ArrayList常见操作4.3 ArrayList的遍历4.4 ArrayList的扩容机制 5. ArrayList的具体使用5.1 杨辉三角5.2 简单的洗牌算法 6. ArrayList的问题及思考 【本节目标】 线性表顺序表ArrayList的简介ArrayList使用ArrayList的扩容机制扑克牌
1.线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
2.1 接口的实现
public class SeqList {private int[] array;private int size;// 默认构造方法SeqList(){ }// 将顺序表的底层容量设置为initcapacitySeqList(int initcapacity){ }// 新增元素,默认在数组最后新增public void add(int data) { }// 在 pos 位置新增元素public void add(int pos, int data) { }// 判定是否包含某个元素public boolean contains(int toFind) { return true; }// 查找某个元素对应的位置public int indexOf(int toFind) { return -1; }// 获取 pos 位置的元素public int get(int pos) { return -1; }// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) { }//删除第一次出现的关键字keypublic void remove(int toRemove) { }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() { }// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的public void display() { }
}3. ArrayList简介
在集合框架中ArrayList是一个普通的类实现了List接口具体框架图如下 【说明】
ArrayList是以泛型方式实现的使用时必须要先实例化ArrayList实现了RandomAccess接口表明ArrayList支持随机访问ArrayList实现了Cloneable接口表明ArrayList是可以clone的ArrayList实现了Serializable接口表明ArrayList是支持序列化的和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayListArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表
4. ArrayList使用
4.1 ArrayList的构造
public static void main(String[] args) {// ArrayList创建推荐写法// 构造一个空的列表ListInteger list1 new ArrayList();// 构造一个具有10个容量的列表ListInteger list2 new ArrayList(10);list2.a dd(1);list2.add(2);list2.add(3);// list2.add(hello); // 编译失败ListInteger已经限定了list2中只能存储整形元素结论: 当我们 调用不带参数的构造方法的时候默认在第一次add的时候才会分配大小为10的内存!!!// list3构造好之后与list中的元素一致ArrayListInteger list3 new ArrayList(list2);// 避免省略类型否则任意类型的元素都可以存放使用时将是一场灾难List list4 new ArrayList();list4.add(111);list4.add(100);
}4.2 ArrayList常见操作
ArrayList虽然提供的方法比较多但是常用方法如下所示需要用到其他方法时同学们自行查看ArrayList的帮助文档。
方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标List subList(int fromIndex, int toIndex)截取部分 list
subList一般是左闭右开 有个小坑 set List3为什么List2也被改变了呢 因为没有拷贝只是拿了个地址
public static void main(String[] args) {ListString list new ArrayList();list.add(JavaSE);list.add(JavaWeb);list.add(JavaEE);list.add(JVM);list.add(测试课程);System.out.println(list);// 获取list中有效元素个数System.out.println(list.size());// 获取和设置index位置上的元素注意index必须介于[0, size)间System.out.println(list.get(1));list.set(1, JavaWEB);System.out.println(list.get(1));// 在list的index位置插入指定元素index及后续的元素统一往后搬移一个位置list.add(1, Java数据结构);System.out.println(list);// 删除指定元素找到了就删除该元素之后的元素统一往前搬移一个位置list.remove(JVM);System.out.println(list);// 删除list中index位置上的元素注意index不要超过list中有效元素个数,否则会抛出下标越界异常list.remove(list.size()-1);System.out.println(list);// 检测list中是否包含指定元素包含返回true否则返回falseif(list.contains(测试课程)){list.add(测试课程);}// 查找指定元素第一次出现的位置indexOf从前往后找lastIndexOf从后往前找list.add(JavaSE);System.out.println(list.indexOf(JavaSE));System.out.println(list.lastIndexOf(JavaSE));// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组ListString ret list.subList(0, 4);System.out.println(ret);list.clear();System.out.println(list.size());
}以为2是下标不是要移除的值怎么办如下
4.3 ArrayList的遍历
ArrayList 可以使用三方方式遍历for循环下标、foreach、使用迭代器
public static void main(String[] args) {ListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);// 使用下标for遍历for (int i 0; i list.size(); i) {System.out.print(list.get(i) );}System.out.println();// 借助foreach遍历for (Integer integer : list) {System.out.print(integer );}System.out.println();IteratorInteger it list.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();
}注意
ArrayList最长使用的遍历方式是for循环下标 以及 foreach迭代器是设计模式的一种后序容器接触多了再给大家铺垫
4.4 ArrayList的扩容机制
下面代码有缺陷吗为什么
public static void main(String[] args) {ListInteger 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;
}【总结】
检测是否真正需要扩容如果是调用grow准备扩容预估需要库容的大小 初步预估按照1.5倍大小扩容 如果用户所需大小超过预估1.5倍大小则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功防止太大导致扩容失败使用copyOf进行扩容
5. ArrayList的具体使用 运行结果
5.1 杨辉三角
杨辉三角
5.2 简单的洗牌算法
public class Card {public int rank; // 牌面值public String suit; // 花色Overridepublic String toString() {return String.format([%s %d], suit, rank);}
}import java.util.List;
import java.util.ArrayList;
import java.util.Random;
public class CardDemo {public static final String[] SUITS {♠, ♥, ♣, ♦};// 买一副牌private static ListCard buyDeck() {ListCard deck new ArrayList(52);for (int i 0; i 4; i) {for (int j 1; j 13; j) {String suit SUITS[i];int rank j;Card card new Card();card.rank rank;card.suit suit;deck.add(card);}}return deck;}private static void swap(ListCard deck, int i, int j) {Card t deck.get(i);deck.set(i, deck.get(j));deck.set(j, t);}private static void shuffle(ListCard deck) {Random random new Random(20190905);for (int i deck.size() - 1; i 0; i--) {int r random.nextInt(i);swap(deck, i, r);}}public static void main(String[] args) {ListCard deck buyDeck();System.out.println(刚买回来的牌:);System.out.println(deck);shuffle(deck);System.out.println(洗过的牌:);System.out.println(deck);// 三个人每个人轮流抓 5 张牌ListListCard hands new ArrayList();hands.add(new ArrayList());hands.add(new ArrayList());hands.add(new ArrayList());for (int i 0; i 5; i) {for (int j 0; j 3; j) {hands.get(j).add(deck.remove(0));}}System.out.println(剩余的牌:);System.out.println(deck);System.out.println(A 手中的牌:);System.out.println(hands.get(0));System.out.println(B 手中的牌:);System.out.println(hands.get(1));System.out.println(C 手中的牌:);System.out.println(hands.get(2));}
}运行结果 刚买回来的牌: [[♠ 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]] 洗过的牌: [[♥ 11], [♥ 6], [♣ 13], [♣ 10], [♥ 13], [♠ 2], [♦ 1], [♥ 9], [♥ 12], [♦ 5], [♥ 8], [♠ 6], [♠ 3], [♥ 5], [♥ 1], [♦ 6], [♦ 13], [♣ 12], [♦ 12],[♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦ 4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠ 12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]] 剩余的牌: [[♦ 6], [♦ 13], [♣ 12], [♦ 12], [♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦ 4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠ 12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]] A 手中的牌: [[♥ 11], [♣ 10], [♦ 1], [♦ 5], [♠ 3]] B 手中的牌: [[♥ 6], [♥ 13], [♥ 9], [♥ 8], [♥ 5]] C 手中的牌: [[♣ 13], [♠ 2], [♥ 12], [♠ 6], [♥ 1]] 6. ArrayList的问题及思考
ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬移故时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考 如何解决以上问题呢
