做网站送的小程序有什么用,做宠物网站心得,公司建设网站公司,wordpress明星资讯主题我的个人主页 我的专栏#xff1a;Java-数据结构#xff0c;希望能帮助到大家#xff01;#xff01;#xff01;点赞❤ 收藏❤ 前言#xff1a;在 Java编程的广袤世界里#xff0c;数据结构犹如精巧的建筑蓝图#xff0c;决定着程序在数据处理与存储时的效率、灵活性以…
我的个人主页 我的专栏Java-数据结构希望能帮助到大家点赞❤ 收藏❤ 前言在 Java编程的广袤世界里数据结构犹如精巧的建筑蓝图决定着程序在数据处理与存储时的效率、灵活性以及可扩展性。其中ArrayList和顺序表作为线性数据结构的典型代表犹如两颗璀璨的明星在众多数据处理场景中熠熠生辉。 顺序表以其简洁而直观的连续内存存储方式为数据的快速随机访问提供了可能。它犹如一位严谨的管家将数据元素有条不紊地排列在连续的内存空间中使得我们能够通过精确的索引迅速定位到所需的数据就像在一本精心编排索引的书籍中快速找到特定章节一样高效。这种特性在一些对数据访问速度有严格要求且数据量相对固定或可预知的场景中展现出了无与伦比的优势。 而 ArrayList则是 Java 集合框架中备受瞩目的一员。它基于数组实现却又巧妙地融入了动态扩容机制如同一位富有弹性的艺术家能够根据创作需求灵活调整画布的大小。这种动态性使得 ArrayList在应对数据量不确定、频繁增删元素的复杂情况时游刃有余。它为开发者提供了丰富便捷的方法库极大地简化了数据操作的流程仿佛一把瑞士军刀在各种数据处理任务中都能发挥出色的作用。 在实际的编程旅程中深入理解 ArrayList 和顺序表的特性、性能表现以及适用场景就如同掌握了两门精湛的技艺。无论是构建高效的数据库管理系统、开发复杂的算法还是打造用户友好的图形界面应用都离不开对这两种数据结构的精准运用。本博客将深入剖析 Java ArrayList 和顺序表从原理到实现从性能对比到应用场景分析为你揭开它们神秘的面纱引领你在 Java编程的数据结构之路上稳步前行帮助你在面对各种数据处理挑战时做出明智而高效的抉择。 一线性表
二顺序表
三ArrayList的简介
四ArrayList使用 五ArrayList的扩容机制
一线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 在 Java 编程领域线性表是一种极为基础且关键的数据结构它犹如大厦的基石支撑起众多复杂算法与程序功能的实现。线性表从直观上理解是由一系列具有相同类型的数据元素按照特定的顺序依次排列而成的集合其元素之间存在着一对一的线性关系。 1.1线性表的基本特性: 一有限性 线性表中的元素数量是有限的。无论是空表不包含任何元素还是包含大量元素的表其元素个数总能确定。例如一个班级的学生名单无论班级规模大小学生人数总归是可以明确统计的。 二有序性 元素在表中的排列具有确定的顺序。每个元素都有其特定的位置除了第一个元素无前驱最后一个元素无后继外其他元素都有且仅有一个直接前驱和一个直接后继。就像电影院里的座位号每个座位都有其固定的前后顺序。 三同一性 表中的所有元素都属于同一数据类型。这一特性使得对线性表的操作能够具有一致性和规范性。例如一个存储整数的线性表其中所有元素都为整型这样在进行数学运算或数据比较等操作时就可以按照统一的整型规则进行。 1.2线性表在 Java 中的常见实现方式 存储结构 顺序表利用数组来存储线性表中的元素。在 Java 中可以声明一个数组来容纳这些元素例如 Object[] data或指定具体类型如 int[] data 等。数组在内存中是连续分配空间的这使得顺序表在随机访问元素时具有极高的效率。通过元素的索引可以直接计算出其在内存中的存储地址从而快速获取到该元素时间复杂度为 O(1)。 操作实现 插入操作当向顺序表中插入一个元素时如果插入位置不是在表尾需要将插入位置之后的所有元素依次向后移动一位为新元素腾出空间然后再将新元素放入指定位置。这种移动操作在元素数量较多时可能会耗费较多时间平均时间复杂度为O(n) 其中 为线性表的长度。例如在一个长度为 100 的顺序表中如果要在第 50 个位置插入一个元素就需要将第 50 个到第 100 个元素向后移动一位。 删除操作类似地删除操作如果不是删除表尾元素需要将删除位置之后的元素依次向前移动一位以填补删除元素后留下的空位。其平均时间复杂度也为O(n) 。比如删除一个长度为 80 的顺序表中的第 30 个元素就需要将第 31 个到第 80 个元素向前移动一位。 查询操作由于可以直接通过索引访问数组元素所以查询指定位置元素的时间复杂度为O(1) 。而查询某个特定值的元素时可能需要遍历整个顺序表在最坏情况下时间复杂度为O(n) 。例如在一个存储学生成绩的顺序表中如果要查找成绩为 90 分的学生可能需要逐个比较所有学生的成绩。 二顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成 数据的增删查改。 1.1定义一个类来表示顺序表
class ArrayListE {// 存储数据的数组private E[] data;// 记录当前顺序表中元素的个数private int size;// 构造函数初始化数组容量public ArrayList(int capacity) {data (E[]) new Object[capacity];size 0;}
}这里的 data 数组就是用来存放顺序表元素的核心容器而 size 则用于追踪实际存储的元素数量。 2.1 接口的实现
public class SeqList {
private int[] array;
private int size;
// 默认构造方法
SeqList(){ }
// 将顺序表的底层容量设置为initcapacity
SeqList(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 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的
public void display() { }
}插入操作 当向顺序表中插入一个元素时情况会相对复杂一些。如果是在顺序表的末尾插入元素操作较为简单只需将元素放入 data[size] 的位置并将 size 加 1 即可。但如果是在中间位置插入例如在索引 k 处插入元素 e则需要将索引 k 及之后的元素依次向后移动一位为新元素腾出空间然后再将新元素放入索引 k 处。
public void add(int index, E e) {if (index 0 || index size) {throw new IllegalArgumentException(Add failed. Illegal index.);}if (size data.length) {resize(2 * data.length);}for (int i size - 1; i index; i--) {data[i 1] data[i];}data[index] e;size;
}删除操作 删除顺序表中的元素同样需要考虑多种情况。如果删除的是末尾元素直接将 size 减 1 即可。若删除索引为 k 的元素则需要将索引 k 之后的元素依次向前移动一位覆盖掉要删除的元素。
public E remove(int index) {if (index 0 || index size) {throw new IllegalArgumentException(Remove failed. Illegal index.);}E ret data[index];for (int i index 1; i size; i) {data[i - 1] data[i];}size--;data[size] null;if (size data.length / 4 data.length / 2! 0) {resize(data.length / 2);}return ret;
}三ArrayList的简介
ArrayList是 Java 集合框架中的一个重要类它位于java.util包中。它实现了List接口这意味着它是一个有序的集合允许存储重复的元素。它的底层数据结构是一个动态大小的数组这使得它可以根据需要自动调整大小。
与普通数组相比ArrayList更加灵活。普通数组在创建时就确定了大小之后很难改变其容量而ArrayList可以方便地添加或删除元素并且会自动处理数组容量的扩展和收缩。 说明 1. ArrayList是以泛型⽅式实现的使⽤时必须要先实例化 2. ArrayList实现了RandomAccess接⼝表明ArrayList⽀持随机访问 3. ArrayList实现了Cloneable接⼝表明ArrayList是可以clone的 4. ArrayList实现了Serializable接⼝表明ArrayList是⽀持序列化的 5. 和Vector不同ArrayList不是线程安全的在单线程下可以使⽤在多线程中可以选择Vector或者 CopyOnWriteArrayList 6. ArrayList底层是⼀段连续的空间并且可以动态扩容是⼀个动态类型的顺序表 创建ArrayList对象 要使用ArrayList首先需要导入java.util.ArrayList类。
import java.util.ArrayList;
public class ArrayListExample {public static void main(String[] args) {ArrayListString list new ArrayListString();}
}创建了一个可以存储String类型元素的ArrayList。其中是泛型参数用于指定列表中元素的类型。除了String还可以是其他基本数据类型对应的包装类如Integer、Double等或自定义的类类型。
四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常⻅操作
4.2.1添加元素
add(E e)方法用于在ArrayList末尾添加元素。
import java.util.ArrayList;
public class ArrayListAddExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);System.out.println(fruits); }
}首先创建了一个ArrayList对象fruits用于存储String类型的元素。然后通过add方法添加了两个水果名称最后打印出ArrayList输出结果为[Apple, Banana]。 add(int index, E e)方法用于在指定索引index处插入元素e。
import java.util.ArrayList;
public class ArrayListAddAtIndexExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);fruits.add(1, Cherry);System.out.println(fruits); }
}这里在索引为1的位置插入了Cherry原来索引为1即Banana及其后面的元素会向后移动一位。输出结果为[Apple, Cherry, Banana]。 4.2.2获取元素
get(int index)方法用于获取ArrayList中指定索引index处的元素。
import java.util.ArrayList;
public class ArrayListGetExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);String secondFruit fruits.get(1);System.out.println(secondFruit); }
}通过get(1)获取了索引为1的元素即Banana并将其存储在secondFruit变量中最后打印输出。 4.2.3修改元素
直接通过索引赋值可以像操作数组一样通过指定索引来修改ArrayList中的元素。
import java.util.ArrayList;
public class ArrayListSetExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);fruits.set(1, Orange);System.out.println(fruits); }
}通过set(1, “Orange”)将索引为1的元素原来为Banana修改为Orange输出结果为[Apple, Orange]。 4.2.4删除元素
remove(int index)方法用于删除指定索引index处的元素。
import java.util.ArrayList;
public class ArrayListRemoveByIndexExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);fruits.remove(0);System.out.println(fruits); }
}通过remove(0)删除了索引为0的元素即Apple输出结果为[Banana]。 remove(Object o)方法用于删除指定的对象o。
import java.util.ArrayList;
public class ArrayListRemoveByObjectExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);fruits.remove(Apple);System.out.println(fruits); }
}通过remove(“Apple”)删除了ArrayList中值为Apple的元素输出结果为[Banana]。 4.2.5遍历ArrayList
使用普通for循环
import java.util.ArrayList;
public class ArrayListForLoopExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);for (int i 0; i fruits.size(); i) {System.out.println(fruits.get(i));}}
}在这个循环中i从0开始每次循环增加1直到i小于ArrayList的大小通过size()方法获取。在循环体内部通过get(i)方法获取当前索引的元素并打印输出。 使用增强for循环for - each循环
import java.util.ArrayList;
public class ArrayListForEachLoopExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);for (String fruit : fruits) {System.out.println(fruit);}}
}fruit变量会依次获取ArrayList中的每个元素循环会自动遍历整个ArrayList直到所有元素都被访问。 使用迭代器Iterator
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListIteratorExample {public static void main(String[] args) {ArrayListString fruits new ArrayList();fruits.add(Apple);fruits.add(Banana);IteratorString iterator fruits.iterator();while (iterator.hasNext()) {System.out.println(iterator.next());}}
}通过iterator()方法获取ArrayList的迭代器。然后通过hasNext()方法检查是否还有下一个元素如果有则通过next()方法获取并打印下一个元素直到没有更多元素为止。 五ArrayList的扩容机制 ArrayList是⼀个动态类型的顺序表即在插⼊元素的过程中会⾃动扩容。 public boolean add(E e) {modCount;add(e, elementData, size);return true;
}
private void add(E e, Object[] elementData, int s) {if (s elementData.length) //第⼀次存储的时候 elementData.length0s 0elementData grow();elementData[s] e;size s 1;
}
private Object[] grow() {return grow(size 1);
}
private Object[] grow(int minCapacity) {int oldCapacity elementData.length;if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity 1 /* preferred growth */);return elementData Arrays.copyOf(elementData, newCapacity);} else {return elementData new Object[Math.max(DEFAULT_CAPACITY,minCapacity)];}
}
//oldLength: 当前数组的⻓度
//minGrowth: 最⼩需要增加的⻓度
//prefGrowth: ⾸选的增⻓ 度通常是当前⼤⼩的⼀半
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength 0// assert minGrowth 0//当前⻓度加上 minGrowth 和 prefGrowth 中的较⼤值。int prefLength oldLength Math.max(minGrowth, prefGrowth); // might overflowif (0 prefLength prefLength SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}
}
private static int hugeLength(int oldLength, int minGrowth) {int minLength oldLength minGrowth;if (minLength 0) { // overflowthrow new OutOfMemoryError(Required array length oldLength minGrowth is too large);} else if (minLength SOFT_MAX_ARRAY_LENGTH) {return SOFT_MAX_ARRAY_LENGTH;} else {return minLength;}
}如果调⽤不带参数的构造⽅法第⼀次分配数组⼤⼩为10 后续扩容为1.5倍扩容 这次的ArrayList的学习就到的了剩下的叙述下一篇中
