动态数组在处理大量数据时，如何实现高效的数据插入和删除操作？

本文共计2329个文字，预计阅读时间需要10分钟。

简介+数组（Array）是一种线性表数据结构。它使用一组连续的内存空间来存储具有相同类型的数据。因此，可以通过索引（Index）直接计算出某个元素的位置。+数组特点+索引（即下标）+一般称为下标。

简介

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。因此可以通过索引(Index)计算出某个元素的地址。

 

数组特点

• 索引(即下标) 一般从0开始，如java, C/C++。
• 长度固定，在申请时长度固定。内存连续，在内存中则是申请一块连续的固定大小的空间。
• 数组有一维数组和多维数组，数组元素可以是基本数据类型(Primitive)，也可以是对象引用(Reference)。
• 随机访问，能够根据位置(下标)直接访问到元素。

线性表（Linear List）

零个或多个数据元素的有限序列。每个线性表上的数据最多只有前和后两个方向。其实除了数组、链表、队列、栈等也是线性表结构。

非线性表

它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

连续的内存空间和相同类型的数据：这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。但是数组的随机访问效率确实十分的高。

插入

假设数组的长度为 n，将一个数据插入到数组中的第 k 个位置。为了把第 k 个 位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。