顺序表的实现关键在于动态扩容和元素移动的优化，1. 扩容时机应选择在添加元素前发现容量不足时进行，最佳策略是容量不足时扩容为原容量的2倍，以平衡时间与空间开销；2. 为减少插入删除时的数据搬移，可采用批量操作、延迟删除或改用链表结构；3. 选择顺序表还是链表需根据场景权衡：若频繁随机访问且内存敏感，选顺序表；若频繁插入删除且容量变化大，选链表。最终应结合具体需求选择合适的数据结构以达到最优性能。
顺序表，说白了，就是用数组来存储数据。Java实现起来也简单，但要写好，让它易用、高效，还是有点讲究的。关键在于理解数组的特性，以及如何巧妙地利用它。
public class SequenceList<T> {
private T[] data; // 存储数据的数组
private int size; // 当前顺序表的元素个数
private int capacity; // 顺序表的最大容量
public SequenceList() {
this(10); // 默认容量为10
}
public SequenceList(int initialCapacity) {
this.capacity = initialCapacity;
this.data = (T[]) new Object[initialCapacity]; // 注意类型转换
this.size = 0;
}
// 添加元素到顺序表末尾
public void add(T element) {
ensureCapacity(size + 1); // 确保容量足够
data[size++] = element;
}
// 在指定位置插入元素
public void insert(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
data[i] = data[i - 1]; // 元素后移
}
data[index] = element;
size++;
}
// 删除指定位置的元素
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
T removedElement = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1]; // 元素前移
}
data[--size] = null; // help GC, 防止内存泄漏，重要！
return removedElement;
}
// 获取指定位置的元素
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
return data[index];
}
// 设置指定位置的元素
public void set(int index, T element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "size);
}
data[index] = element;
}
// 获取顺序表的大小
public int size() {
return size;
}
// 顺序表是否为空
public boolean isEmpty() {
return size == 0;
}
// 确保容量足够
private void ensureCapacity(int minCapacity) {
if (minCapacity > capacity) {
int newCapacity = Math.max(minCapacity, capacity * 2); // 扩容为原来的2倍
T[] newData = (T[]) new Object[newCapacity];
System.arraycopy(data, 0, newData, 0, size);
data = newData;
capacity = newCapacity;
}
}
// toString 方法，方便查看顺序表的内容
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i < size - 1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
public static void main(String[] args) {
SequenceList<String> list = new SequenceList<>();
list.add("Apple");
list.add("Banana");
list.add("Orange");
System.out.println(list); // 输出: [Apple, Banana, Orange]
list.insert(1, "Grape");
System.out.println(list); // 输出: [Apple, Grape, Banana, Orange]
list.remove(2);
System.out.println(list); // 输出: [Apple, Grape, Orange]
System.out.println("Size: " + list.size()); // 输出: Size: 3
System.out.println("Get element at index 1: " + list.get(1)); // 输出: Get element at index 1: Grape
}
}顺序表实现的关键点在于数组的动态扩容和元素的移动。
顺序表扩容时机选择：什么时候扩容性能最佳？
顺序表扩容的时机非常重要，直接影响到程序的性能。一般来说，当顺序表即将满的时候，就需要进行扩容。但“即将满”这个概念比较模糊，实际操作中，通常是在添加元素之前检查当前元素个数是否等于数组容量。如果相等，就进行扩容。
立即学习“Java免费学习笔记（深入）”；
扩容策略也很关键。一种常见的策略是每次扩容时，将容量增加一倍（或者1.5倍）。这种策略在时间和空间上做了一个平衡。如果每次扩容增加的容量太少，会导致频繁扩容，影响性能；如果增加的容量太多，又会浪费空间。
另一个需要考虑的因素是扩容的成本。扩容涉及到创建一个新的数组，并将原数组中的元素复制到新数组中，这是一个比较耗时的操作。因此，应该尽量避免频繁扩容。
最佳的扩容时机和策略，需要根据具体的应用场景进行调整。例如，如果事先知道顺序表的大概大小，可以在创建顺序表时就指定一个合适的容量，从而避免扩容。如果顺序表的使用场景是对内存非常敏感，可以考虑使用更节省空间的扩容策略。
顺序表插入删除操作效率优化：如何避免频繁的数据搬移？
顺序表的插入和删除操作，效率瓶颈主要在于元素的移动。每次插入或删除一个元素，都需要将后续的元素向前或向后移动，这在元素数量较多时，会消耗大量的时间。
要优化插入和删除操作的效率，可以考虑以下几种方法：
- 批量插入/删除： 如果需要插入或删除多个元素，可以考虑一次性完成，减少元素移动的次数。
- 使用链表： 如果插入和删除操作非常频繁，可以考虑使用链表来代替顺序表。链表的插入和删除操作不需要移动元素，效率更高。当然，链表也有缺点，例如访问元素需要遍历链表，效率不如顺序表。
- 延迟删除： 对于删除操作，可以采用延迟删除的策略。即不立即删除元素，而是将元素标记为已删除，等到需要的时候再进行真正的删除。这种策略可以减少元素的移动次数，但会增加空间的占用。
- 优化查找算法： 在插入和删除之前，通常需要先查找元素的位置。优化查找算法可以减少查找的时间，从而提高插入和删除的整体效率。例如，可以使用二分查找来快速定位元素的位置。
选择哪种优化方法，需要根据具体的应用场景进行权衡。如果插入和删除操作不是很频繁，可以不用进行优化。如果插入和删除操作非常频繁，可以考虑使用链表或延迟删除等策略。
如何选择合适的线性表：顺序表还是链表？
顺序表和链表都是常见的线性表，它们各有优缺点。选择哪种线性表，需要根据具体的应用场景进行权衡。
顺序表的优点：
- 随机访问： 可以通过下标直接访问元素，时间复杂度为O(1)。
- 存储密度高： 顺序表中的元素在内存中是连续存储的，没有额外的空间开销。
顺序表的缺点：
- 插入和删除效率低： 需要移动大量的元素，时间复杂度为O(n)。
- 容量固定： 需要预先分配空间，如果空间不足，需要进行扩容。
链表的优点：
- 插入和删除效率高： 不需要移动元素，时间复杂度为O(1)。
- 容量可变： 可以动态分配空间，不需要预先分配空间。
链表的缺点：
- 随机访问效率低： 需要遍历链表才能访问元素，时间复杂度为O(n)。
- 存储密度低： 链表中的元素在内存中是分散存储的，需要额外的空间来存储指针。
总结：
- 如果需要频繁进行随机访问，或者对存储空间要求较高，可以选择顺序表。
- 如果需要频繁进行插入和删除操作，或者对容量要求较高，可以选择链表。
当然，还有一些其他的线性表，例如栈、队列等，它们都有各自的特点，可以根据具体的应用场景进行选择。
