数组结构整理

什么是数组结构？

数组结构是计算机存储、组织数据的方式。数据结构是指互相之间存在一种或者多种特定关系的数据的集合。结构包括逻辑结构和物理结构

数据的逻辑结构包括4种：

（1）集合：数据元素之间除了有相同的数据类型再没有其他关系

（2）线性结构：数据元素之间是一对一——线性表，栈，队列

（3）树形结构：数据元素之间是一对多的关系

（4）图状结构：数据元素是多对多的关系

物理结构包括顺序存储与链式存储：

（1）顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率高。

（2）链式存储结构是用任意存储空间来存储数据，不可以随机访问，访问效率低

头指针和头结点的区别：

（1）头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在

（2）头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头节点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息

线性结构的特点：

（1）集合中必须存在唯一的一个“第一个元素”

（2）集合中必须存在唯一的一个“最后一个元素”

（3）除最后元素之外，其他数据元素均有唯一的“后继”

（4）除第一个元素之外，其他数据元素均有唯一的“前驱”

数组和链表的区别：

（1）从逻辑结构来说：数组存储长度是固定的，不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，易于进行插入和删除的操作

（2）从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O（n）,单链表只需要在第一次寻找i位置 时间复杂度为O(n),其余插入和删除的时间复杂度均为O(1),提高了插入和删除的效率

单链表结构和顺序存储结构

(1) 当进行删除和插入操作，顺序存储结构每次都需要移动元素，总的时间复杂度为O（n2）

(2) 链式存储结构确定i位置的指针后，其时间复杂度仅为O（1）.

顺序存储结构需要进行预分配内存空间，所以会造成空间浪费或溢出。链式存储结构不需要预分配存储空间，元素个数不受限制。

栈和队列的区别：

（1）队列是允许在一段进行插入 另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除，在表尾进行插入。

（2）栈是只能在表尾进行插入和删除的线性表，对于插入到栈的元素按“后进先出”的规则处理，插入和删除都在栈顶进行，由于进栈和出栈都是在栈顶进行，所以要有一个size变量记录当前栈的大小，当进栈时size不能超过数组长度，size+1，出栈时栈不为空，size-1

参考：数据结构面试题以及答案整理_けいしん的博客-CSDN博客_数据结构面试题