Java数据结构之ArrayList与顺序表详解

目录

• 前言
• 一、线性表
• 1.1线性表的基本特性
• 1.2线性表在Java中的常见实现方式
• 二、顺序表
• 2.1定义一个类来表示顺序表
• 2.2接口的实现
• 三、ArrayList的简介
• 四、ArrayList使用
• 4.1 ArrayList的构造
• 4.2 ArrayList常⻅操作
• 4.2.1添加元素
• 4.2.2获取元素
• 4.2.3修改元素
• 4.2.4删除元素
• 4.2.5遍历ArrayList
• 五、ArrayList的扩容机制

前言

在 Java编程的广袤世界里，数据结构犹如精巧的建筑蓝图，决定着程序在数据处理与存储时的效率、灵活性以及可扩展性。其中，ArrayList和顺序表作为线性数据结构的典型代表，犹如两颗璀璨的明星，在众多数据处理场景中熠熠生辉。

顺序表，以其简洁而直观的连续内存存储方式，为数据的快速随机访问提供了可能。它犹如一位严谨的管家，将数据元素有条不紊地排列在连续的内存空间中，使得我们能够通过精确的索引迅速定位到所需的数据，就像在一本精心编排索引的书籍中快速找到特定章节一样高效。这种特性在一些对数据访问速度有严格要求且数据量相对固定或可预知的场景中，展现出了无与伦比的优势。 而 ArrayList，则是 Java 集合框架中备受瞩目的一员。它基于数组实现，却又巧妙地融入了动态扩容机制，如同一位富有弹性的艺术家，能够根据创作需求灵活调整画布的大小。这种动态性使得 ArrayList在应对数据量不确定、频繁增删元素的复杂情况时游刃有余。它为开发者提供了丰富便捷的方法库，极大地简化了数据操作的流程，仿佛一把瑞士军刀，在各种数据处理任务中都能发挥出色的作用。 在实际的编程旅程中，深入理解 ArrayList 和顺序表的特性、性能表现以及适用场景，就如同掌握了两门精湛的技艺。无论是构建高效的数据库管理系统、开发复杂的算法，还是打造用户友好的图形界面应用，都离不开对这两种数据结构的精准运用。本博客将深入剖析 Java ArrayList 和顺序表，从原理到实现，从性能对比到应用场景分析，为你揭开它们神秘的面纱，引领你在 Java编程的数据结构之路上稳步前行，帮助你在面对各种数据处理挑战时做出明智而高效的抉择。

一、线性表

线性表（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 分的学生，可能需要逐个比较所有学生的成绩。

二、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成 数据的增删查改。

2.1定义一个类来表示顺序表

class ArrayList<E> {
    // 存储数据的数组
    private E[] data;
    // 记录当前顺序表中元素的个数
    private int size;
    // 构造函数，初始化数组容量
    public ArrayList(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }
}

这里的 data 数组就是用来存放顺序表元素的核心容器，而 size 则用于追踪实际存储的元素数量。

2.2接口的实现

public class SeqList {
private int[] array;
private int size;
// 默认构造方法
SeqList(){ }
// 将顺序表的底层容量设置为initcapacity
SeqList(int initcapacity){ }
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
publisrkKOvjdc 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() { }
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
pusrkKOvjdblic void display() { }
}

插入操作

当向顺序表中插入一个元素时，情况会相对复杂一些。如果是在顺序表的末尾插入元素，操作较为简单，只需将元素放入 data[size] 的位置，并将 size 加 1 即可。但如果是在中间位置插入，例如在索引 k 处插入元素 e，则需要将索引 k 及之后的元素依次向后移动一位，为新元素腾出空间，然后再将新元素放入索引 k 处。

puandroidblic 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) {
        ArrayList<String> list = new ArrayList<String>();
    }
}

创建了一个可以存储String类型元素的ArrayList。其中是泛型参数，用于指定列表中元素的类型。除了String，还可以是其他基本数据类型对应的包装类（如Integer、Double等）或自定义的类类型。

四、ArrayList使用

4.1 ArrayList的构造

public static void main(String[] args) {
// ArrayList创建，推荐写法
// 构造⼀个空的列表
List<Integer> list1 = new ArrayList<>();
// 构造⼀个具有10个容量的列表
List<Integer&gsrkKOvjdt; list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整
形元素
// list3构造好之后，与list中的元素⼀致
ArrayList<Integer> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> 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) {
        ArrayList<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        Iterator<String> 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.length=0，s = 0
	elementData = 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) {
	// presrkKOvjdconditions not checked because of inlining
	// assert oldLength >= 0
	// assert minGrowth > 0
	//当前⻓度加上 minGrowth 和 prefGrowth 中的较⼤值。
	int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
	if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
		return prefLength;
	} else {
		// put code cold in a separate method
			return hugeLength(oldLength, minGrowth);
		}
}
private static int hugeLength(int oldLength, int minGrowth) {
	int minLength = oldLength + minGrowth;
	if (minLength < 0) { // overflow
		throw 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倍扩容

以上就是Java数据结构之ArrayList与顺序表详解的详细内容，更多关于Java ArrayList与顺序表的资料请关注编程客栈(www.devze.com)其它相关文章！