揭阳手机网站建设,福州seo排名收费,成都人高清影院品牌加盟,万网域名证书List和ArrayList与顺序表 一. List1.1 List介绍2.1 常见接口介绍3.1 List的使用 二. ArrayList与顺序表1.线性表2.顺序表2.1 接口的实现2.2 顺序表的创建2.3 顺序表的打印2.4 顺序表的插入2.5 顺序表的按索引位置插入数据2.6 判断顺序表是否包含某个数2.7 返回顺序表某个数的索… List和ArrayList与顺序表 一. List1.1 List介绍2.1 常见接口介绍3.1 List的使用 二. ArrayList与顺序表1.线性表2.顺序表2.1 接口的实现2.2 顺序表的创建2.3 顺序表的打印2.4 顺序表的插入2.5 顺序表的按索引位置插入数据2.6 判断顺序表是否包含某个数2.7 返回顺序表某个数的索引2.8 获取顺序表pos位置的值2.9 更新顺序表pos位置的值2.10 顺序表删除元素2.11 顺序表的大小2.12 清空顺序表 3.ArrayList简介4. ArrayList使用4.1 ArrayList的构造 4.2 ArrayList常见操作4.3 ArrayList的遍历4.4 ArrayList的扩容机制5. ArrayList的具体使用5.1 简单的洗牌算法5.2 杨辉三角的实现 6 面试题 一. List
1.1 List介绍
在集合框架中List是一个接口继承Collection。 Iterable -- Collection -- List。
Collection也是一个接口该接口中规范了后序容器中常用的一些方法
Iterable也是一个接口表示实现该接口的类是可以逐个元素进行遍历的
站在数据结构的角度来看List就是一个线性表即n个具有相同类型元素的有限序列在该序列上可以执行增删改查以及变量等操作。
2.1 常见接口介绍
List中提供了很多方法具体的常用方法如下 方法 ---- 解释 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.1 List的使用
List是一个接口并不是直接用来实例化。 如果要使用的话必须先去实例化List的实现类ArrayLsit和LinkedList都实现了List接口。
二. ArrayList与顺序表
1.线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列等等。
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
2.1 接口的实现
IList接口
public interface IList {// 新增元素,默认在数组最后新增public void add(int data);// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某个元素public boolean contains(int toFind);// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size();// 清空顺序表public void clear();// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的public void display();Boolean isFull();Boolean isEmpty();
}2.2 顺序表的创建
把顺序表封装成一个类定义数组 elem大小 usedSize、默认容量和顺序表MyArrayList。
public class MyArrayList implements IList{public int[] elem;public int usedSize;public static final int DEFAULT_CAPACITY 5;public MyArrayList() {elem new int[DEFAULT_CAPACITY];}
}2.3 顺序表的打印 Overridepublic void display() {for (int i 0; i this.usedSize; i) {System.out.println(elem[i] );}System.out.println();}2.4 顺序表的插入
写一个判断是否满了的方法先要判断是否满了满了就要扩容扩容是使用Arrays.copyOf方法来进行扩容 Overridepublic void add(int data) {// 判断是否满了 满了就要扩容if (isFull()) {elem Arrays.copyOf(elem,elem.length*2);}this.elem[usedSize] data;this.usedSize;}Overridepublic Boolean isFull() {return this.usedSize DEFAULT_CAPACITY;}2.5 顺序表的按索引位置插入数据
在插入数据之前我们需要检查插入的位置是否合法如果小于0或者大于usedSize就抛出位置不合法的异常如果位置合法还需要判断顺序表是否满了满了就需要扩容在pos位置插入data时从this.usedSize-1开始遍历到pos位置也就是大于等于pos把元素一个一个往后挪即elem[i1] elem[i];然后插入数据usedSize。 Overridepublic void add(int pos, int data) {// pos位置的判断checkPosOfAdd(pos);if (isFull()) {elem Arrays.copyOf(elem,elem.length*2);}for (int i this.usedSize-1; i pos; i--) {this.elem[i1] elem[i];}this.elem[pos] data;this.usedSize;System.out.println();}private void checkPosOfAdd(int pos) {if (pos0 || pos this.usedSize) {throw new PosException(Pos位置为 pos);}}2.6 判断顺序表是否包含某个数 Overridepublic boolean contains(int toFind) {for (int i 0; i this.usedSize; i) {if (elem[i] toFind){return true;}}return false;}2.7 返回顺序表某个数的索引 Overridepublic int indexOf(int toFind) {for (int i 0; i this.usedSize; i) {if (elem[i] toFind) {return i;}}return -1;}2.8 获取顺序表pos位置的值
在这里也需要写一个**checkPosOfGet(pos)方法来判断位置是否合法注意还要检查顺序表是否为空写一个判断是否为空的isEmpty()**方法 public int get(int pos) {// 判断pos位置checkPosOfGet(pos);// 为空if (isEmpty()) {throw new EmptyException(顺序表为空);//return -1;}return this.elem[pos];}public Boolean isEmpty() {return usedSize 0;}private void checkPosOfGet(int pos){if (pos 0 || pos this.usedSize) {throw new PosException(Pos位置不合法pos);}}2.9 更新顺序表pos位置的值
同样也需要获取到pos的位置并检查是否合法判断顺序表是否为空不为空直接修改 Overridepublic void set(int pos, int value) {checkPosOfGet(pos);if (isEmpty()) {System.out.println(顺序表为空);}this.elem[pos] value;}2.10 顺序表删除元素
判断顺序表是否为空获取到要删除的元素索引位置然后从该位置index开始遍历把该删除的后一个元素往前覆盖然后usedSize–。 Overridepublic void remove(int toRemove) {if (isEmpty()) {throw new EmptyException(顺序表为空);}int indexindexOf(toRemove);for (int i index; i this.usedSize-1; i) {this.elem[i] this.elem[i1];}this.usedSize--;}2.11 顺序表的大小 Overridepublic int size() {return this.usedSize;}2.12 清空顺序表
为了防止数据泄露需要情况顺序表。 Overridepublic void clear() {this.usedSize 0;}注意
在定义了一个空顺序表的时候第一次add分配了默认的内存大小在扩容的时候是以1.5倍扩容
3.ArrayList简介
在集合框架中ArrayList是一个普通的类实现了List接口具体框架图如下 注意
ArrayList是以泛型方式实现的使用时必须要先实例化ArrayList实现了RandomAccess接口表明ArrayList支持随机访问ArrayList实现了Cloneable接口表明ArrayList是可以clone的ArrayList实现了Serializable接口表明ArrayList是支持序列化的和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayListArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表
4. ArrayList使用
4.1 ArrayList的构造 注意在这里的extends E 传入的是E类型或者是E的子类型
public static void main(String[] args) {// ArrayList创建推荐写法// 构造一个空的列表ListInteger list1 new ArrayList();// 构造一个具有10个容量的列表ListInteger list2 new ArrayList(10);list2.add(1);list2.add(2);list2.add(3);// list2.add(hello); // 编译失败ListInteger已经限定了list2中只能存储整形元素// list3构造好之后与list中的元素一致ArrayListInteger list3 new ArrayList(list2);// 避免省略类型否则任意类型的元素都可以存放使用时将是一场灾难List list4 new ArrayList();list4.add(111);list4.add(100);
}4.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 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());}4.3 ArrayList的遍历
ArrayList 可以使用三方方式遍历for循环下标、foreach、使用迭代器 public static void main(String[] args) {ArrayListInteger arrayList new ArrayList();arrayList.add(10);arrayList.add(20);arrayList.add(30);//ArrayList的遍历//第一种遍历方式 重写了toString方法System.out.println(arrayList);//第二种遍历方式for (int i 0; i arrayList.size(); i) {System.out.print(arrayList.get(i) );}System.out.println();//3.for-eachfor (int x:arrayList) {System.out.print(x );}System.out.println();// 4. 迭代器IteratorInteger it arrayList.iterator();while (it.hasNext()) {System.out.print(it.next() );}System.out.println();//5. ListIterator 是 Iterator的子类ListIteratorInteger it2 arrayList.listIterator();while (it2.hasNext()) {System.out.print(it2.next() );}System.out.println();//6. 从后往前打印ListIteratorInteger it3 arrayList.listIterator();while (it2.hasPrevious()) {System.out.print(it2.previous() );}System.out.println();}4.4 ArrayList的扩容机制
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 简单的洗牌算法
Card
public class Card {public String suit;public int num;public Card(String suit, int num) {this.suit suit;this.num num;}Overridepublic String toString() {/*return Card{ suit suit \ , num num };*/return suit num;}
}Cardgame:
import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class Cardgame {public static final String[] suits {♥,♣,♦,♠};// 买牌 创建牌public ListCard buyCard() {ListCard cardList new ArrayList();for (int i 0; i 4; i) {for (int j 0; j 13; j) {cardList.add(new Card(suits[i],j));//相当于下面代码/*String suit suits[i];Card card new Card(suit,j)cardList.add(card);*/}}return cardList;}// 洗牌public void shuffle(ListCard cardList) {Random random new Random();for (int i cardList.size()-1; i 0; i--) {int index random.nextInt(i);swap(cardList,i,index);}}private static void swap(ListCard cardList,int i,int j) {Card tmp cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}// 发牌 3个人每个人轮流抓5张牌// 思路1.每个人拿到牌 放到哪// 2. l轮流怎么抓5张牌public ListListCard getCard(ListCard cardList) {ListCard hand1 new ArrayList();ListCard hand2 new ArrayList();ListCard hand3 new ArrayList();ListListCard hand new ArrayList();hand.add(hand1);hand.add(hand2);hand.add(hand3);for (int i 0; i 5; i) { // 拿五次牌for (int j 0; j 3; j) { // 3个人//怎么揭牌? 每次相当于 删除下0标这个牌Card card cardList.remove(0);// 怎么放到对应人的手里面?hand.get(j).add(card);}}return hand;}
}
Main测试
import java.util.List;public class Main {public static void main(String[] args) {Cardgame cardgame new Cardgame();ListCard ret cardgame.buyCard();System.out.println(买牌);System.out.println(ret);cardgame.shuffle(ret);System.out.println(洗牌:);System.out.println(ret);System.out.println(揭牌);ListListCard hand cardgame.getCard(ret);for (int i 0; i hand.size(); i) {System.out.println(第(i1)个人的牌hand.get(i));}System.out.println(剩下的牌);System.out.println(ret);}}5.2 杨辉三角的实现
具体要求 ** 实现这个杨辉三角得需要定义一个二维数组每个一维数组的第一个和最后一个都为1中间的数字就是上一行的j位置的元素j-1也就是前一个元素所以需要定义一个preRow来获取上一行的数据即preRow ret.get(i-1)然后再用preRow去调用get方法得到该位置的上面需要相加的两个元素即preRow.get(j)preRow.get(j-1)然后再用add插入数据**。 public ListListInteger generate(int numRows) {// 定义一个二维数组ListListInteger ret new ArrayList();ListInteger list new ArrayList();list.add(1);ret.add(list);for (int i 1; i numRows; i) {//每循环一次 就是一行ListInteger curRow new ArrayList();curRow.add(1); //每行的第一个元素//处理中间的数字ListInteger preRow ret.get(i-1);for (int j 1; j i; j) {int x preRow.get(j)preRow.get(j-1);curRow.add(x);}//处理最后一个数字curRow.add(1);ret.add(curRow);}return ret;}6 面试题
CVTE面试题 str1“welcome to cvte” str2: “come” 删除字符串1当中出现的所有字符串2当中的字符 即结果为 “wl t vt”
public class Test {public static ListCharacter func(String str1,String str2) {ListCharacter list new ArrayList();for (int i 0; i str1.length(); i) {char ch str1.charAt(i);if(!str2.contains(ch)) { //contains接收的是字符串 所以字符ch list.add(ch);}}return list;}public static void main(String[] args) {ListCharacter ret func(welcome to cvte,come);for (Character ch:ret) {System.out.print(ch);}}
}
