当前位置：首页 > news >正文

顺序表与Myarraylist

news 来源：原创 2025/9/2 17:38:56

对于所有编程语言来说，数据结构都是精华

一个计算机程序=数据结构+算法；

我在之前的博客中写了关于集合框架与泛型，这就是数据结构的开始，我今天说的便是数据结构的第一个线性数据结构--顺序表

顺序表是一种线性数据结构，它使用连续的内存空间来存储数据元素。顺序表的每个元素在内存中是紧挨着的，可以通过索引快速访问任意位置的元素。顺序表是实现线性表的一种常见方式，通常可以用数组来实现。

一.顺序表的核心特点

存储方式：
- 顺序表使用连续的内存空间来存储数据元素，通常通过数组实现。
- 所有元素在内存中是紧挨着的，因此顺序表支持随机访问。
随机访问：
- 可以通过索引直接访问任意位置的元素，时间复杂度为 O(1)。
- 这使得顺序表在需要频繁访问元素的场景中非常高效。
插入和删除操作：
- 插入操作：在中间位置插入一个元素时，需要将插入点之后的所有元素向后移动一个位置，时间复杂度为 O(n)。
- 删除操作：在中间位置删除一个元素时，需要将删除点之后的所有元素向前移动一个位置，时间复杂度为 O(n)。
空间利用率：
- 静态顺序表：空间大小固定，可能会造成空间浪费。
- 动态顺序表：可以通过动态扩容来解决空间不足的问题，但扩容操作本身会带来额外的时间开销。

二.顺序表的实现

顺序表的实现可以分为静态顺序表和动态顺序表：

（1）静态顺序表

静态顺序表使用固定大小的数组来存储数据元素，其大小在创建时确定，不能动态改变。

示例代码：

java

复制

public class StaticArrayList<T> {private T[] elements; // 存储元素的数组private int size; // 当前元素个数// 构造方法，指定数组大小public StaticArrayList(int capacity) {elements = (T[]) new Object[capacity];size = 0;}// 添加元素public void add(T element) {if (size == elements.length) {throw new IllegalStateException("Array is full");}elements[size++] = element;}// 获取元素public T get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}return elements[index];}// 删除元素public T remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}T removedElement = elements[index];for (int i = index; i < size - 1; i++) {elements[i] = elements[i + 1];}size--;return removedElement;}// 获取当前元素个数public int size() {return size;}
}

（2）动态顺序表

动态顺序表使用动态数组来存储数据元素，其大小可以根据需要动态扩容。

示例代码：

java

复制

public class DynamicArrayList<T> {private T[] elements; // 存储元素的数组private int size; // 当前元素个数// 构造方法，初始容量为10public DynamicArrayList() {elements = (T[]) new Object[10];size = 0;}// 添加元素public void add(T element) {if (size == elements.length) {ensureCapacity(); // 动态扩容}elements[size++] = element;}// 插入元素public void add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException();}if (size == elements.length) {ensureCapacity();}for (int i = size; i > index; i--) {elements[i] = elements[i - 1];}elements[index] = element;size++;}// 获取元素public T get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}return elements[index];}// 删除元素public T remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}T removedElement = elements[index];for (int i = index; i < size - 1; i++) {elements[i] = elements[i + 1];}size--;return removedElement;}// 动态扩容private void ensureCapacity() {int newSize = elements.length * 2;T[] newElements = (T[]) new Object[newSize];System.arraycopy(elements, 0, newElements, 0, size);elements = newElements;}// 获取当前元素个数public int size() {return size;}
}

三.顺序表的操作

添加元素：
- 尾部添加：直接将元素放在数组的末尾，时间复杂度为 O(1)。
- 中间插入：需要将插入点之后的所有元素向后移动一个位置，时间复杂度为 O(n)。
删除元素：
- 尾部删除：直接移除数组末尾的元素，时间复杂度为 O(1)。
- 中间删除：需要将删除点之后的所有元素向前移动一个位置，时间复杂度为 O(n)。
查找元素：
- 按索引查找：直接通过索引访问，时间复杂度为 O(1)。
- 按值查找：需要遍历数组，时间复杂度为 O(n)。
遍历：
- 顺序表支持快速遍历，可以通过循环依次访问每个元素，时间复杂度为 O(n)。

四.顺序表的优缺点

优点

随机访问高效：
- 通过索引可以快速访问任意位置的元素，时间复杂度为 O(1)。
内存利用率高：
- 静态顺序表的内存利用率较高，适合存储大量数据。
实现简单：
- 基于数组实现，代码简单易懂。

缺点

插入和删除效率低：
- 在中间位置插入或删除元素时，需要移动大量元素，时间复杂度为 O(n)。
空间固定：
- 静态顺序表的大小固定，可能会造成空间浪费。动态顺序表虽然可以动态扩容，但扩容操作本身会带来额外的时间开销。
线程不安全：
- 顺序表本身不是线程安全的，需要额外的同步机制来保证线程安全。

五.顺序表的应用场景

数据量较大且频繁访问：
- 适合存储大量数据，并且需要频繁通过索引访问元素的场景。
插入和删除操作较少：
- 如果数据结构的插入和删除操作较少，顺序表是一个很好的选择。
学习数据结构：
- 顺序表是学习线性表和数组操作的基础，适合用于教学和学习。

六.总结

顺序表是一种基于数组实现的线性数据结构，具有随机访问高效、内存利用率高、实现简单等优点。然而，它的插入和删除操作效率较低，且空间大小固定（静态顺序表）或需要动态扩容（动态顺序表）。在实际应用中，顺序表适合用于数据量较大且频繁访问的场景，尤其是在插入和删除操作较少的情况下。