概述
目录
一、线性表接口
二、动态数组
2.1动态数组的变量和构造方法
2.2添加元素
2.3输出数组的字符串形式
2.4在索引为index的位置插入新元素
2.5查询线性表中是否包含指定元素
2.6返回索引为index的元素值
2.7修改索引为index位置的元素为新值，返回修改前的元素值
2.8删除线性表中索引为index的元素，返回删除前的元素值
2.9删除第一个值为val的元素
2.10在线性表中删除所有值为val的元素
三、JDK中动态数组的实现
3.1ArrayList的定义、继承或实现的接口
3.2ArrayList的具体常见使用
3.2.1构造方法
3.2.2常用操作方法
3.2.3 ArrayList的三种遍历方式
3.3分析JDK中ArrayList
3.3.1 无参构造
3.3.2添加以及扩容机制
3.4ArrayList的特点
满足以下两个要求的数据结构称为线性表：
（1）保存在线性表中的元素都是相同类型的。
（2）元素之间线性排列，元素和元素之间逻辑上是连续的，索引为0的元素一定是逻辑上在索引为1的元素之前。
线性表有一个最大的特点，就是有明确的索引下标的概念。
线性表示一个比较抽象的感念，具体实现有很多，数组，链表，栈，队列，字符串都是具体的线性表。Java接口优先原则，无论具体是那种线性表，操作盒方法应该对外都是统一的，接口定义了所有实现子类所共同应当具备的行为和规范。
JDK中线性表的接口称为List，无论是数组实现还是链表实现，操作线性表的方法都已经在List接口中定义好了。
基本数组特点：保存的单个相同类型的元素，一旦声明一个原始数组，无论采用哪种实例化方式，最终数组一旦定义，长度固定。
由于原始数组存在定长问题，因此，需要将原始数组做扩充，将原始数组封装到自定义的类中，让他具备可扩展干的能力=>对使用者来说，用户无需关心数组的长度问题，提供给用户的数组是一个动态数组，用户只需要使用提供的数组进行增删改查即可，无需关心数组的越界问题。
本质：将原始的数组封装到类中，对用户淡化数组长度的概念，当数组长度不够时，类的内部自己进行扩容操作，对用户透明。
动态数组 = 基本数组封装到类中 + 对外提供一系列的方便进行增删改查的方法。
无论是数组还是链表都属于线性表的一种，所以只要是线性表的子类，都应该具备基础的增删改查方法。
定义线性表的规范：一个类能称之为是线性表的子类，应该具备类似的行为（都是保存单个元素的集合，集合中元素的类型是相同的，元素之间逻辑上连续）
一、线性表接口
定义线性表接口Seqlist。定义接口带来的好处：就是可以以非常低的成本来更换具体的子类。
public interface SeqList {
void add(int val);
// 在索引为index的位置插入新元素
void add(int index,int val);
// 查询线性表中是否包含指定元素val
boolean contains(int val);
// 返回索引为index的元素值
int get(int index);
// 修改索引为index位置的元素为新值，返回修改前的元素值
int set(int index,int newVal);
// 删除线性表中索引为index的元素，返回删除前的元素值
int removeByIndex(int index);
// 删除第一个值为val的元素
void removeByValueOnce(int val);
// 在线性表中删除所有值为val的元素
void removeAllValue(int val);
}二、动态数组
2.1动态数组的变量和构造方法
首先需要设置一个内部数组用来存储输入的数组，然后设置一个size用来记录add方法中插入的位置。再设置一个默认变量，在无参构造中使用。
创建两个构造方法，如果没有输入明确的数组长度，默认产生对象时，初始化长度为10。另一个构造方法则输入了数组长度，创建一个相应长度的数组。
public class MyArray implements SeqList {
private int[] elementData;
private int size;
private static final int DEFAULT_CAPACITY = 10;
public MyArray() {
this(DEFAULT_CAPACITY);
}
public MyArray(int capacity){
this.elementData = new int[capacity];
}
}2.2添加元素
首先需要排除非法情况，就是数组长度为0时，需要抛出异常。
size的位置恰好就是当前数组中尾部插入元素的位置，完全插入后size就可以记录当前线性表中的实际元素个数。
如果整个数组都被填满了，需要让数组在下一次插入前进行扩容，扩容后的就是根据原数组的内容拷贝过来，长度变为原来的1.5倍，超过原数组长度的内容。改变了原数组的引用，指向了扩容后的数组。
在扩容这里有一个隐藏风险，当原先数组长度为奇数个的时候，扩容失败，如果oldLength == 1，1 + 1 / 2 = 1 + 0 = 1，扩容没有成功，所以需要将newLength赋值为oldLength+((oldLength+1)>>1)。
public void add(int val) {
if (elementData.length == 0) {
throw new IllegalArgumentException("arr length cannot be zero!");
}
this.elementData[size] = val;
size ++;
if (size == elementData.length) {
grow();
}
}
private void grow(){
int oldLength = this.elementData.length;
int newLength = oldLength+((oldLength+1)>>1);
this.elementData = Arrays.copyOf(elementData,newLength);
}2.3输出数组的字符串形式
将数组输出成字符串形式，需要借用StringBuilder中的append方法，将每个数组中的元素按顺序添加，然后输出字符串形式。
public String toString(){
StringBuilder s = new StringBuilder("[");
for (int i = 0; i < size; i++) {
s.append(this.elementData[i]);
if(i<size-1){
s.append(",");
}
}
s.append("]");
return s.toString();
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(3);
list.add(5);
list.add(9);
System.out.println(list.toString());
}
2.4在索引为index的位置插入新元素
首先需要判断index的合法性，小于index和大于size都不合法。
如果index==size就是尾插法，可以直接调用add方法。
排除过后就可以将指定元素插入到索引位置，然后将本来在该位置的元素向后移一位，后面的每一个元素都向后移动一位，最后需要判断是否需要扩容为了方便下一步的add。
public void add(int index, int val) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index illegal!");
}
if (index == size) {
add(val);
return;
}
if(index==this.elementData.length){
grow();
}
size++;
for(int i = index;i<size;i++){
int tmp = this.elementData[i];
this.elementData[i] = val;
val = tmp;
}
if (size == elementData.length) {
grow();
}
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(3);
list.add(5);
list.add(9);
System.out.println(list.toString());
list.add(3,7);
System.out.println(list.toString());
list.add(0,7);
System.out.println(list.toString());
list.add(6,7);
System.out.println(list.toString());
}
2.5查询线性表中是否包含指定元素
查找整个数组，当遇到指定元素则返回true，如果不包含指定元素则返回false。
public boolean contains(int val) {
for(int i = 0;i<size;i++){
if(this.elementData[i]==val){
return true;
}
}
return false;
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(3);
list.add(5);
list.add(9);
System.out.println(list.toString());
System.out.println(list.contains(9));
System.out.println(list.contains(8));
}
2.6返回索引为index的元素值
首先需要判断index是否合法，创建了rangeCheck方法，排除了index < 0和index >= size的情况。
然后直接返回当前位置的元素。
public int get(int index) {
if (!rangeCheck(index)) {
throw new IllegalArgumentException("get index illegal!");
}
return elementData[index];
}
private boolean rangeCheck(int index) {
if (index < 0 || index >= size) {
return false;
}
return true;
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(3);
list.add(5);
list.add(9);
System.out.println(list.toString());
System.out.println(list.get(0));
}
2.7修改索引为index位置的元素为新值，返回修改前的元素值
同样首先判断index是否合法。
然后将索引位置的元素改成新的值，返回旧的值。
public int set(int index, int newVal) {
if (!rangeCheck(index)) {
throw new IllegalArgumentException("get index illegal!");
}
int temp = this.elementData[index];
this.elementData[index] = newVal;
return temp;
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(3);
list.add(5);
list.add(9);
System.out.println(list.toString());
System.out.println(list.set(3,7));
System.out.println(list.toString());
}
2.8删除线性表中索引为index的元素，返回删除前的元素值
首先先判断index是否合法。
然后将index位置后的每一个元素都向前移动一位，然后把size的数值减一，返回原本在索引位置上的值。
public int removeByIndex(int index) {
if (!rangeCheck(index)) {
throw new IllegalArgumentException("get index illegal!");
}
int tmp = this.elementData[index];
for(int i = index;i<size-1;i++){
this.elementData[i] = this.elementData[i+1];
}
size--;
return tmp;
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(3);
list.add(5);
list.add(9);
System.out.println(list.toString());
System.out.println(list.removeByIndex(3));
System.out.println(list.toString());
}
2.9删除第一个值为val的元素
直接遍历整个数组，当第一次遇到值为val的元素就调用removeByIndex方法，然后返回。
public void removeByValueOnce(int val) {
for(int i = 0;i<size;i++){
if(this.elementData[i]== val){
removeByIndex(i);
return ;
}
}
System.err.println("当前集合中不存在元素" + val);
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(9);
list.add(5);
list.add(9);
System.out.println(list.toString());
list.removeByValueOnce(9);
System.out.println(list.toString());
list.removeByValueOnce(2);
System.out.println(list.toString());
}
2.10在线性表中删除所有值为val的元素
直接遍历整个数组，当第一次遇到值为val的元素就调用removeByIndex方法，然后不返回，继续遍历。
这个时候有一个特殊情况，调用removeByIndex时可能补上来的元素值也是val，所以判断数组当前位置值是否为val需要用while循环。
public void removeAllValue(int val) {
boolean isRemoved = false;
for(int i = 0;i<size;i++){
while(this.elementData[i]== val){
isRemoved = true;
removeByIndex(i);
}
}
if (!isRemoved) {
System.err.println("当前集合中不存在元素" + val);
}
} public static void main(String[] args) {
SeqList list = new MyArray(4);
list.add(1);
list.add(9);
list.add(5);
list.add(9);
System.out.println(list.toString());
list.removeAllValue(9);
System.out.println(list.toString());
list.removeAllValue(2);
System.out.println(list.toString());
}
三、JDK中动态数组的实现
3.1ArrayList的定义、继承或实现的接口
RandomAccess：实现了整个接口就具备了随机访问的能力，给一个索引下标可以立即O（1）取得该位置的元素。
Cloneable：可复制的能力。
List：线性表接口。
Seriallizable：序列化接口，ArrayList这个类就可以方便的转为字节数组进行输入输出。
List下关于动态数组的实现有两个子类，ArrayList和Vector都是基于动态数组的实现，ArrayList式异步操作，线程不安全，效率高。Vector是同步操作（对整个数组进行加锁操作）线程安全，效率比较低。
3.2ArrayList的具体常见使用
3.2.1构造方法
ArrayList()构造一个初始容量为 10 的空列表。 |
ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。 |
ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。 |
前两种构造方法都没有传入数值，l3传入了数值，但是也产生了新的对象，改变l3，link不会发生改变。
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>(5);
List<Integer> link = new LinkedList<>();
link.add(1);
link.add(3);
link.add(5);
List<Integer> l3 = new ArrayList<>(link);
System.out.println(l1);
System.out.println(l2);
System.out.println(l3);
}
3.2.2常用操作方法
（1）添加
boolean | add(E e)将指定的元素添加到此列表的尾部。 |
void | add(int index, E element)将指定的元素插入此列表中的指定位置。 |
boolean | addAll(Collection<? extends E> c)按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。 |
在第三个方法中将link的所有元素添加到l1的尾部，但是对l1进行操作，并不会影响到list。
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
// 尾插
l1.add(1);
l1.add(3);
l1.add(5);
l1.add(1,10);
List<Integer> link = new LinkedList<>();
link.add(2);
link.add(4);
link.add(6);
l1.addAll(link);
System.out.println(l1);
}
（2）删除
E | remove(int index)移除此列表中指定位置上的元素。 |
boolean | remove(Object o)移除此列表中首次出现的指定元素（如果存在）。 |
void | clear()移除此列表中的所有元素。 |
当调用List集合保存的就是整型，调用remove方法默认会调用按照索引删除。
如果想用移除此列表中首次出现的指定元素，需要先获取值对应的索引，然后调用remove。
而clear清空则调用了就把集合中所有元素都删除。
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
l1.add(1);
l1.add(3);
l1.add(5);
l1.add(7);
System.out.println(l1.remove(1));
System.out.println(l1);
System.out.println(l1.remove(l1.indexOf(7)));
System.out.println(l1);
l1.clear();
System.out.println(l1);
}
（3）截取
List<E> | subList(int fromindex, int toIndex)截取部分list。 |
截取的区间是左闭右开的，并且截取是产生新的集合，并不影响被截取的原集合。
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
l1.add(1);
l1.add(3);
l1.add(5);
l1.add(7);
System.out.println(l1);
List<Integer> ret = l1.subList(1,3);
System.out.println(ret);
System.out.println(l1);
}
（4）指定元素有关的方法。
boolean | contains(Object o)如果此列表中包含指定的元素，则返回 true。 |
E | get(int index)返回此列表中指定位置上的元素。 |
int | indexOf(Object o)返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。 |
int | lastIndexOf(Object o)返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。 |
E | set(int index, E element)用指定的元素替代此列表中指定位置上的元素。 |
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
l1.add(1);
l1.add(3);
l1.add(5);
l1.add(7);
l1.add(7);
System.out.println(l1.contains(7));
System.out.println(l1.get(2));
System.out.println(l1.indexOf(3));
System.out.println(l1.lastIndexOf(7));
System.out.println(l1.set(2,9));
System.out.println(l1);
}
3.2.3 ArrayList的三种遍历方式
什么是遍历：就是按照一定的规则将集合中的所有元素全部访问一遍，做到不重复，不遗漏。
（1）普通for循环+get方法进行遍历。
（2）for-each循环（lterable接口的子类都可使用for-each循环）。
（3）使用集合的迭代器。
迭代器是专门为了遍历一个集合产生的，对于List集合的子类，有一个接口；terator接口，从前向后遍历，hasNext()=> 判断集合是否还有元素没有遍历，next()=> 取出当前要遍历的元素。
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(5);
list.add(7);
for (int i = 0; i < l1.size(); i++) {
System.out.print(l1.get(i)+" ");
}
System.out.println();
for (int i :l1) {
System.out.print(i+" ");
}
System.out.println();
Iterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
这三种遍历方式，如果只是普通遍历的话，不牵扯到集合内容的修改时，用哪一种都行。但是在遍历的过程中，修改了集合的内容需要使用的迭代器方式。
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(5);
list.add(7);
for (int i :list) {
System.out.print(i+" ");
}
System.out.println();
}如果没有使用迭代器就会报错，这个错误叫集合的并发修改异常。假设这个集合是由多个用户同时访问的，其中一个用户修改了集合的内容，那么其他用户就看看到不一样的结果。
以下为采用迭代器的方法。
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(5);
list.add(7);
Iterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
int num = iterator.next();
if (num == 3) {
iterator.remove();
}
System.out.println(iterator.next());
}3.3分析JDK中ArrayList
3.3.1 无参构造
ArrayList的无参构造并没有初始化elementData。只有在第一次add时才会真正将数组进行实例化。是懒加载。懒加载就是产生对象时，内部保存的元素的集合并不初始化，只有在第一次真正添加元素之前在进行内部空间的初始化，尽可能的避免空间浪费。
Vector的无参构造就默认初始化了长度为10的Object数组。
3.3.2添加以及扩容机制
ArrayList中size是有效元素个数，默认为零。在add方法中首先要判断size加一判断是否越界，确保空间够用再进行尾插操作。
若此时data为空，返回默认长度10和size+1的最大值，若数组不为空直接返回size+1整个长度，也就是说如果数组还没有初始化，第一次调用add时，就将数组长度赋值为10。
当前有效元素的个数首先要+1，然后和data的长度进行比较，在添加元素之前先扩容。
在grow中也是将新数组长度变为1.5倍。第一个if循环中如果data还没初始化，newCap为默认长度10，同时还有一种情况，当data长度已经接近整形最大值还要翻倍处理，只要新增一个长度元素即可。
而Vector的grow方法前面不太一样，capacityIncrement为自定义扩容参数，并且扩容为原数组的两倍。
3.4ArrayList的特点
动态数组仍然是数组，因此支持随机访问的能力，在O(1)时间内根据索引取得对应索引的元素。
不能简单的说，动态数组的插入和删除效率较低，只有在数组的任意位置的插入和删除（尤其是数组头部）需要进行元素的搬移。默认的尾插其实效率特别高，甚至比链表还快。
扩容需要开辟新的空间，旧的空间需要JVM来进行垃圾回收，此时需要频繁添加数据频繁导致扩容触发，空间的申请和释放都是不小的性能消耗。因此在频繁的进行元素插入和删除时，考虑用链表进行。
一般的扩容都是扩容为原数组的1.5倍或者两倍，假设当前元素100个，为了多放一个元素需要多申请50个或者100个单位，会造成空间的浪费。
所以若需要频繁进行元素的插入和删除，此时选择链表最优，若需要频繁按照索引查询元素，使用数组更优。
最后
以上就是背后冥王星为你收集整理的【数据结构】动态数组一、线性表接口二、动态数组三、JDK中动态数组的实现的全部内容，希望文章能够帮你解决【数据结构】动态数组一、线性表接口二、动态数组三、JDK中动态数组的实现所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复