怎样用代码制作网站,wordpress添加文章副标题,百度上海总部,网站开发学习路线曾经我也是一枚学霸#xff0c;直到有一天想去学渣的世界看看#xff0c;结果就找不到回去的路了。 目录
1. 线性表
2.顺序表
2.1 接口的实现
3. ArrayList简介
4. ArrayList使用
4.1 ArrayList的构造 4.2 ArrayList常见操作
4.3 ArrayList的遍历
4.4 ArrayList的扩… 曾经我也是一枚学霸直到有一天想去学渣的世界看看结果就找不到回去的路了。 目录
1. 线性表
2.顺序表
2.1 接口的实现
3. ArrayList简介
4. ArrayList使用
4.1 ArrayList的构造 4.2 ArrayList常见操作
4.3 ArrayList的遍历
4.4 ArrayList的扩容机制
5. ArrayList的具体使用
5.1 简单的洗牌算法
6. 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接口具体框架图如下 【说明】 1. ArrayList是以泛型方式实现的使用时必须要先实例化 2. ArrayList实现了RandomAccess接口表明ArrayList支持随机访问 3. ArrayList实现了Cloneable接口表明ArrayList是可以clone的 4. ArrayList实现了Serializable接口表明ArrayList是支持序列化的 5. 和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayList 6. ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表 4. ArrayList使用
4.1 ArrayList的构造 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常见操作
ArrayList虽然提供的方法比较多但是常用方法如下所示需要用到其他方法时自行查看ArrayList的帮助文档即可。 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必须介于[0size)区间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);System.out.println(list.indexOf(javaSE)); //区分大小写找不到返回-1System.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) {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();
}
注意 1. ArrayList最长使用的遍历方式是for循环下标 以及 foreach 2. 迭代器是设计模式的一种后序容器接触多了再给大家铺垫 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;
} 【总结】 1. 检测是否真正需要扩容如果是调用grow准备扩容 2. 预估需要库容的大小 初步预估按照1.5倍大小扩容 如果用户所需大小超过预估1.5倍大小则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功防止太大导致扩容失败 3. 使用copyOf进行扩容 5. ArrayList的具体使用
5.1 简单的洗牌算法
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的问题及思考 1. ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬移故时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间 所以ArrayList存在缺陷而这缺陷就需要靠LinkedList解决了。 注图片来自网络如有侵权请联系删除
希望对大家有所帮助感谢观看
