沈阳建设厅网站首页,网络广告名词解释,精神文明建设网站专栏,小型项目外包网站目录 一、List及其使用 1.1 List的概念 1.2 常见接口的介绍 1.3 List的使用
二、线性表和顺序表 2.1 线性表 2.2 顺序表
三、ArrayList介绍
四、ArrayList的使用 4.1 ArrayList构造 4.2 ArrayList的常用方法 4.3 ArrayList的遍历 4.4 ArrayList的扩容机制
五、ArrayList的具…目录 一、List及其使用 1.1 List的概念 1.2 常见接口的介绍 1.3 List的使用
二、线性表和顺序表 2.1 线性表 2.2 顺序表
三、ArrayList介绍
四、ArrayList的使用 4.1 ArrayList构造 4.2 ArrayList的常用方法 4.3 ArrayList的遍历 4.4 ArrayList的扩容机制
五、ArrayList的具体使用 5.1 简单洗牌算法 5.2 杨辉三角
六、ArrayList的问题 一、List及其使用 1.1 List的概念 在集合框架中List是一个接口继承自Collection。 Collection也是一个接口该接口中规范了后序容器中常用的一些方法 Iterable也是一个接口表示实现该接口的类是可以逐个元素进行遍历的 从数据结构角度看List就是一个线性表即n个具有相同类型元素的有限序列在该序列上可以执行增删改查以及变量等操作。 1.2 常见接口的介绍 List中有许多方法 虽然方法多但常用方法如下
方法解释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 的下标ListE subList(int fromIndex, int toIndex)截取部分list 1.3 List的使用 List是个接口并不能直接用来实例化。如果要使用必须去实例化List的实现类。在集合框架中ArrayList和LinkedList都实现了List接口。
二、线性表和顺序表 2.1 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种广泛使用的数据结构常见线性表有顺序表、链表、栈、队列...... 2.2 顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储在数组上完成数据的增删查改。 模拟实现顺序表中的常用函数 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 位置的元素设为 value 更新public void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove) ;// 获取顺序表长度public int size();// 清空顺序表public void clear() ;// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的public void display();boolean isFull();public boolean isEmpty();
} public class MyArrayList implements IList{private int[] elem;private int usedSize;//顺序表默认大小private static int DEFAULT_Size10;public MyArrayList(){elemnew int[DEFAULT_Size];}public MyArrayList(int capacity){elemnew int[capacity];DEFAULT_Sizecapacity;}//添加一个数据Overridepublic void add(int data) {chackCapacity();this.elem[usedSize]data;this.usedSize;}//检查容量private void chackCapacity(){if(isFull()){elem Arrays.copyOf(elem,elem.length*2);}}//在pos插入一个数据Overridepublic void add(int pos, int data) {try {chackPosOnAddOrGetOrSet(pos);}catch (PosError e){e.printStackTrace();return;}chackCapacity();for (int i usedSize; i pos ; i) {elem[i]elem[i-1];}elem[pos]data;usedSize;}/*检查pos的合法性*/private void chackPosOnAddOrGetOrSet(int pos) throws PosError{if(pos0||posthis.usedSize)throw new PosError(下标异常pos);}//判断顺序表是否包含toFindOverridepublic boolean contains(int toFind) {if(isEmpty())return false;for (int x:elem) {if(xtoFind)return true;}return false;}//获取toFing对应的下标Overridepublic int indexOf(int toFind) {for (int i 0; i this.usedSize; i) {if(elem[i]toFind)return i;}return -1;}//获取pos下标对应的元素值Overridepublic int get(int pos) {if(isEmpty())return -1;chackPosOnAddOrGetOrSet(pos);return this.elem[pos];}//设置下标为pos的元素值为valueOverridepublic void set(int pos, int value) {chackPosOnAddOrGetOrSet(pos);elem[pos]value;}//删除toRemoveOverridepublic void remove(int toRemove) {int indexindexOf(toRemove);if(index0){System.out.println(要删除的数不存在);return;}for(int iindex;ithis.usedSize-1;i){this.elem[i]this.elem[i1];}this.usedSize--;}//获取当前顺序表的大小Overridepublic int size() {return this.usedSize;}//清空Overridepublic void clear() {for (int i 0; i usedSize; i) {set(i,0);}}/*遍历顺序表当中的元素*/Overridepublic void display() {if(isEmpty()){throw new MyArrayIsEmpty(顺序表是空的);}for(int i0;ielem.length;i){System.out.println(this.elem[i] );}System.out.println();}/*判断顺序表是否已满*/Overridepublic boolean isFull() {/*if(usedSizeDEFAULT_Size)return true;elsereturn false;*/return usedSizeDEFAULT_Size;}Overridepublic boolean isEmpty() {return elem.length0;}
} public class MyArrayIsEmpty extends RuntimeException{public MyArrayIsEmpty(String massage){super(massage);}
} public class PosError extends RuntimeException{public PosError(String massage){super(massage);}
} 三、ArrayList介绍 在集合框架中ArrayList是一个普通的类实现了List接口具体框架如下 ArrayList是以泛型方式实现的使用时必须要先实例化ArrayList实现了RandomAccess接口表明ArrayList支持随机访问ArrayList实现了Cloneable接口表明ArrayList是可以clone的ArrayList实现了Serializable接口表明ArrayList是支持序列化的ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayListArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表。
四、ArrayList的使用 4.1 ArrayList构造
方法解释ArrayList()无参构造ArrayList(Collection? extends E c)利用其他 Collection 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量 public static void main(String[] args) {//创建一个空列表 ArrayList() 默认size为0ArrayListInteger list1new ArrayList();//创建一个容量为10的列表 ArrayList(int initialCapacity)创建指定容量的列表//ArrayListInteger 指定存放的元素类型为IntegerArrayListInteger list2new ArrayList(10);list1.add(1);//第一次add时底层数组size为10list1.add(2);list1.add(3);//ArrayList(Collection? extends E c)//参数c必须实现了Collection接口是E的子类或E本身类型//list3的元素与list2相同ArrayListInteger list3new ArrayList(list2);
}使用不带参数newArrayList对象时默认size为0当第一次add时底层数组size为10当数组需要扩容时是以当前数组size的1.5倍进行扩容。 4.2 ArrayList的常用方法 ArrayList提供方法比较多但常用方法如下所示
方法解释boolean add(E e)尾插 evoid add(int index, E e)将 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 e)将下标 index位置元素设为 evoid clear()清空boolean contains(Object o)判断 o是否在线性表中int indexOf(Object o)返回第一个 o所在下标int lastIndexOf(Object o)返回最后一个 o所在下标ListE subList(int fromIndex, int toIndex)截取部分list public static void main(String[] args) {ArrayListInteger list1new ArrayList(10);list1.add(1);list1.add(2);list1.add(3);list1.add(4);System.out.println(list1);// 1 2 3 4//获取list1中有效元素的个数并打印System.out.println(list1.size());//4System.out.println();//获取和设置index位置的元素System.out.println(list1.get(2));//3list1.set(2,99);System.out.println(list1.get(2));//99System.out.println();//在index位置插入valuelist1.add(2,88);System.out.println(list1);//1 2 88 99 4System.out.println();//删除指定元素list1.remove(new Integer(88));System.out.println(list1);//1 2 99 4//删除index位置的元素 index不能超过list1的有效元素个数list1.remove(2);System.out.println(list1);// 1 2 4System.out.println();//检查list1中是否包含valueSystem.out.println(list1.contains(99));//falseSystem.out.println(list1.contains(2));//trueSystem.out.println();list1.add(2);list1.add(1);System.out.println(list1);//1 2 4 2 1//获取第一次出现value的下标System.out.println(list1.indexOf(1));//0//获取最后一次出现value的下标System.out.println(list1.lastIndexOf(1));//4System.out.println();//截取list1 ListE subList(int fromIndex, int toIndex)ListInteger list2list1.subList(1,3);System.out.println(list2);//2 4//截取的list2并没有分配内存只是list2这个引用指向下标为1~2的元素list2.set(0,10);System.out.println(list1);// 1 10 4 2 1System.out.println(list2);//10 4
}4.3 ArrayList的遍历 ArrayList 可以使用三方方式遍历for循环下标、foreach、使用迭代器。 public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);//for循环遍历for(int i0;ilist.size();i){System.out.print(list.get(i) );}System.out.println();//foreach遍历for (Integer x:list){System.out.print(x );}System.out.println();//迭代器遍历IteratorInteger itlist.iterator();while (it.hasNext()){System.out.print(it.next() );}
} 4.4 ArrayList的扩容机制 ArrayList是一个动态类型的顺序表即在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式 检测是否需要扩容如果需要调用grow函数估计容量大小初步估计按1.5倍扩容若用户所需超过估计的1.5倍大小按用户所需大小扩容扩容前进行检测是否能扩容使用copyOf进行扩容。
五、ArrayList的具体使用 5.1 简单洗牌算法 public class Card {//花色private String design_and_color;//数值private int value;public Card(String design_and_color, int value) {this.design_and_color design_and_color;this.value value;}Overridepublic String toString() {return 花色design_and_color 数值value;}public String getDesign_and_color() {return design_and_color;}public void setDesign_and_color(String design_and_color) {this.design_and_color design_and_color;}public int getValue() {return value;}public void setValue(int value) {this.value value;}
} public class CardText {//花色集合 红桃 ♥ 黑桃 ♠ 方块♦ 梅花 ♣public static final String[] design_and_colors {♥, ♣, ♠, ♦};//买一副牌public static ListCard buyCard(){/*没有大小王共52张牌J Q K 分别用11 12 13代替*/ListCard cardnew ArrayList(52);for (int i 0; i 4; i) {for(int j1;j13;j){Card card1new Card(design_and_colors[i],j);card.add(card1);}}return card;}//洗牌public static void brushCard(ListCard cards){for (int i 51; i 0 ; i--) {Random randomnew Random(i);int jrandom.nextInt(i);swap(cards,i,j);}}//交换两张牌public static j void swap(ListCard cards, int i,int j){Card tmpcards.get(i);cards.set( i,cards.get(j));cards.set( j,tmp);}public static void main(String[] args) {//取一副牌ListCard cardbuyCard();System.out.println(拿到一副牌);System.out.println(card);//洗牌brushCard(card);System.out.println(洗牌后);System.out.println(card);//发牌 三人轮流拿牌每人五张ListListCard handsnew ArrayList();//hands代表三人各自取的牌hands.add(new ArrayList());//new ArrayList()代表每人手中的牌的集合hands.add(new ArrayList());hands.add(new ArrayList());for(int i0;i5;i){for(int j0;j3;j){hands.get(j).add(card.remove(0));}}System.out.println(第一个人手中的牌);System.out.println(hands.get(0));System.out.println(第二个人手中的牌);System.out.println(hands.get(1));System.out.println(第三个人手中的牌);System.out.println(hands.get(2));System.out.println(剩余的牌);System.out.println(card);}
} 5.2 杨辉三角 杨辉三角题目链接 public ListListInteger generate(int numRows) {ListListInteger listnew ArrayList();//设置第一行ListInteger list2new ArrayList();list2.add(1);list.add(list2);//设置剩余行for(int i1;inumRows;i){//设置当前行ListInteger tmpnew ArrayList();//设置当前行第一个数tmp.add(1);//获取前一行ListInteger preRowlist.get(i-1);//设置当前行其他数for(int j1;ji;j){int apreRow.get(j-1)preRow.get(j);tmp.add(a);}//设置当前行最后一个数tmp.add(1);list.add(tmp);}return list;
} 六、ArrayList的问题 1. ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后移动时间复杂度为O(N)。 2. 增容需要申请新空间拷贝数据释放旧空间有不小的消耗。 3. 增容一般是呈1.5倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到150我们再继续插入了5个数据后面没有数据插入了那么就浪费了45个数据空间。
