1.线性表线性表linear list:是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构常见的线性表顺序表、链表、栈、队列...线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。2.顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成 数据的增删查改。2.1 接口的实现public interface ioList { //在列表末尾追加元素 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); // 删除第一次出现的关键字key public void remove(int toRemove); // 获取顺序表的长度 public int size(); // 清空顺序表 public void clear(); // 打印顺序表 (不是顺序表中的方法) public void display(); boolean ifFull(); boolean isEmpty(); }import java.util.Arrays; import java.util.EmptyStackException; public class myArrayList implements ioList { public int[] element; public int useSize; // 默认的容量 public static final int DEFAULT_CAPACITY 5; public myArrayList() { element new int[DEFAULT_CAPACITY]; } /* * 添加元素 默认添加到数组的最后位置 */ Override public void add(int data) { // 1.判断是否满了,满了需要扩容 if (ifFull()) { //满了扩容自身的两倍 element Arrays.copyOf(element, 2 * element.length); } element[useSize] data; useSize; } Override public boolean ifFull() { return useSize element.length; } /* * 给pos位置 添加一个元素 * */ Override public void add(int pos, int data) { // 1.pos位置的判断 checkPosOfAdd(pos); if (ifFull()) { element Arrays.copyOf(element, 2 * element.length); } for (int i useSize; i pos; i--) { element[i 1] element[i]; } element[pos] data; useSize; } private void checkPosOfAdd(int pos) { if (pos 0 || pos useSize) { throw new PosException(pos位置为: pos); } } /* * 查找当前元素 是否存在 * */ Override public boolean contains(int toFind) { for (int i 0; i useSize; i) { if (element[i] toFind) { return true; } } return false; } /* * 查找当前元素 的下标 * */ Override public int indexOf(int toFind) { for (int i 0; i useSize; i) { if(element[i] toFind) { return i; } } return -1; } /* * 获取pos位置的值 * */ Override public int get(int pos) { // 1.pos位置不合法怎么办? checkPosOfGet(pos); // 2.为空怎么办 if (isEmpty()) { throw new EmptyException(顺序表为空); // return -1; } return element[pos]; } public boolean isEmpty() { return useSize 0; } private void checkPosOfGet(int pos) { if (pos 0 || pos useSize) { throw new PosException(pos位置不合法: pos); } } /* * 更新pos位置的值为value * */ Override public void set(int pos, int value) { checkPosOfGet(pos); if (isEmpty()) { throw new EmptyException(顺序表为空); //return -1; } this.element[pos] value; } /* * 删除toRemove这个数字 * */ Override public void remove(int toRemove) { if (isEmpty()) { throw new EmptyException(顺序表为空,不能删除); } int index indexOf(toRemove); for (int i index; i useSize - 1; i) { element[i] element[i1]; } useSize--; } Override public int size() { return this.useSize; } /* * 清空顺序表 防止内存泄漏 * */ Override public void clear() { useSize 0; } /* * 打印顺序表当中所有的元素 * */ Override public void display() { for (int i 0; i useSize; i) { System.out.print(element[i] ); } System.out.println(); } }public class PosException extends RuntimeException{ public PosException() { } public PosException(String msg) { super(msg); } }3. ArrayList简介在集合框架中ArrayList是一个普通的类实现了List接口具体框架图如下【说明】1. ArrayList是以泛型方式实现的使用时必须要先实例化2. ArrayList实现了RandomAccess接口表明ArrayList支持随机访问3. ArrayList实现了Cloneable接口表明ArrayList是可以clone的4. ArrayList实现了Serializable接口表明ArrayList是支持序列化的5. 和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者 CopyOnWriteArrayList6. ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表4. ArrayList使用4.1 ArrayList的构造方法解释ArrayList()无参构造ArrayList(Collection? extends E c)利用其他 Collection 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量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的帮助文档。方法解释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)截取部分 listimport java.util.ArrayList; import java.util.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否则返回false if(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、使用迭代器、ListItergtorimport java.util.ArrayList; import java.util.Iterator; import java.util.ListIterator; public class traverse { public static void main(String[] args) { ArrayListInteger arrayList new ArrayList(); arrayList.add(10); arrayList.add(20); arrayList.add(30); // 第一种遍历方式 System.out.println(arrayList); // 第二种遍历方式 for for (int i 0; i arrayList.size(); i) { System.out.print(arrayList.get(i) ); } System.out.println(); // 第三种遍历方式:for-each for (int x: arrayList) { System.out.print(x ); } System.out.println(); //第四种遍历方式:迭代器 IteratorInteger it arrayList.iterator(); while (it.hasNext()) { System.out.print(it.next() ); } System.out.println(); // 第五种遍历 ListIterator ListIterator Integer it2 arrayList.listIterator(); while (it2.hasNext()) { System.out.print(it2.next() ); } System.out.println(); // 第六种遍历:从前向后打印 ListIteratorInteger it3 arrayList.listIterator(arrayList.size()); while (it3.hasPrevious()) { System.out.print(it3.previous() ); } System.out.println(); /* * Iterator 是通用迭代器适用于所有集合Collection功能简单只支持正向遍历和删除。 * ListIterator 是列表专用迭代器功能更强大支持双向遍历、索引访问、修改和添加元素。 */ } }注意1. ArrayList最长使用的遍历方式是for循环下标 以及 foreach2. 迭代器是设计模式的一种4.4 ArrayList的扩容机制下面代码有缺陷吗为什么public static void main(String[] args) { ListInteger list new ArrayList(); for (int i 0; i 100; i) { list.add(i); } }有什么缺陷频繁自动扩容导致性能浪费。原因new ArrayList()默认初始容量是 10你要添加100 个元素ArrayList 满了就会自动扩容扩容规则10 → 15 → 22 → 33 → 49 → 74 → 112每次扩容都要新建数组 拷贝旧数据一共要扩容6 次结果明明可以一次搞定却做了 6 次数组拷贝效率变低。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 code if (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 简单的洗牌算法Card/** * Author 12629 * Description */ public class Card { public String suit;//花色 public int num;//数字 public Card(String suit, int num) { this.suit suit; this.num num; } Override public String toString() { /*return Card{ suit suit \ , num num };*/ //return 花色suit数字num; return suitnum; } }CardGameimport java.util.ArrayList; import java.util.List; import java.util.Random; /** * Author 12629 * Description */ public class CardGame { public static final String[] suits {♥,♣,♦,♠}; /** * 生成一副扑克牌 * 52张 4 -》 13 * return */ public ListCard buyCard() { ListCard cardList new ArrayList(); for (int i 0; i 4; i) { for (int j 1; j 13; j) { /*String suit suits[i]; Card card new Card(suit,j); cardList.add(card);*/ cardList.add(new Card(suits[i],j)); } } 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. * param cardList */ 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) { //怎么揭牌 每次相当于删除 0 下标 这个牌 Card card cardList.remove(0); //怎么放到对应人的手里面 hand.get(j).add(card); } } return hand; } }Mainimport java.util.List; /** * Author 12629 * Description */ public class Main { public static void main(String[] args) { CardGame cardGame new CardGame(); ListCard ret cardGame.buyCard(); System.out.println(买牌); System.out.println(ret); System.out.println(洗牌); cardGame.shuffle(ret); 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); } }6. ArrayList的问题及思考1. ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬 移故时间复杂度为O(N)2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继 续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。思考 如何解决以上问题呢1. 插入/删除效率低O(N)解决方案使用链表如LinkedList代替动态数组。链表的每个节点在内存中不必连续插入或删除元素时只需修改相邻节点的指针时间复杂度为 O(1)已知位置。但需注意链表在随机访问时效率低O(N)因此适用于插入删除频繁、随机访问少的场景。2. 扩容时消耗大申请、拷贝、释放解决方案预留足够容量在创建 ArrayList 时如果大致能预估元素个数直接指定初始容量避免频繁扩容。使用非连续存储的数据结构如链表、跳表等它们不需要整体搬迁。采用分块存储如LinkedArrayList或Unrolled LinkedList结合数组和链表的优点每个块内连续存储多个元素块间用指针连接。插入删除只在块内移动少量元素整体搬迁成本降低。3. 扩容导致的浪费如 2 倍增长解决方案采用更合理的增长因子例如1.5 倍或1.25 倍。研究表明1.5 倍可以在空间利用率和扩容次数之间取得较好平衡。Java 的ArrayList实际扩容逻辑为newCapacity oldCapacity (oldCapacity 1)即 1.5 倍。精确扩容若已知后续插入元素个数可调用ensureCapacity()一次性扩容到恰好所需大小避免多余空间。使用自适应策略当容器长期稳定后可调用trimToSize()将容量缩减到实际大小释放多余空间。采用块状链表每个块内部容量固定分配新块时只浪费最后一个块的部分空间整体浪费比例可控。最后的最后:总结根据场景选择合适的数据结构,没有完美的结构只有针对具体需求的最优选择!!!