一、数组

1. 数组的概念

数组（array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量称为元素。

数组的存储形式如图：

 数组的两个特点：

1. 数组中的每一个元素也都有着自己的下标，下标从0开始，一直到数组长度-1；
2. 在内存中顺序存储 ，因此可以很好地实现逻辑上的顺序表 。

2. 数组的基本操作

（数据结构的操作无非是增、删、改、查）

a. 读取元素

对于数组来说，读取是最简单的操作。由于数组在内存中顺序存储，所以只要给出一个数组下标，就可以快速读取到对应的数组元素。

在Python中，数组对应的是列表（list），使用方括号的形式创建。

# 初始化列表
my_list = [3, 1, 2, 5, 4, 9, 7, 2]

现在拥有了名叫my_list的数组，如要读取下标为3的元素，写作my_list[3]；要读取下标为5的元素，写作my_list[5]。需要注意的是，输入的下标必须在数组的长度范围之内，否则会出现数组越界的问题。像这种根据下标读取元素的方式叫做随机读取。

# 读取元素
print(my_list[2])

b. 更新元素

要把数组中某一个元素的值替换为一个新值，也是非常简单的操作。直接利用数组下标，就可以把新值赋给该元素。

# 更新元素
my_list[3] = 10
print(my_list[3])

c. 插入元素

插入数组元素有3种操作：

• 尾部插入
• 中间插入
• 超范围插入

尾部插入是直接把插入的元素放在数组尾部的空闲位置，等同于更新元素的操作。

中间插入需要首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。

 上面所描述的插入过程，Python中都有函数能快速实现：

# 尾部插入元素
my_list.append(6)
# 中间插入元素
my_list.insert(5, 11)  # insert中第一个是索引位置，第二个是要插入列表的对象
print(my_list)

为了更好地理解数组的工作方式，让我们来自己实现一段插入操作的代码：

class MyArray:
    def __init__(self, capacity):
        self.array = [None] * capacity
        self.size = 0
        
    def insert_v2(self, index, element):
        # 判断访问下标是否超出范围
        if index < 0 or index > self.size:
            raise Exception("超出数组实际元素范围！")
        # 从右向左循环，逐个元素向右挪一位
        for i in range(self.size-1, -1, -1):
            self.array[i+1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1
    
    def output(self):
        for i in range(self.size):
            print(self.array[i])


array = MyArray(4)
array.insert_v2(0, 10)
array.insert_v2(0, 11)
array.insert_v2(0, 15)
array.output()

代码中的成员变量size是数组中实际元素的数量。如果插入元素在数组尾部，传入的下标参数index等于size；如果插入元素在数组中间或头部，则index小于size。

如果传入的下标参数index大于size或小于0，则认为是非法输入，会直接抛出异常。

超范围插入就相当于数组的扩容。原数组在创建时长度就已经确定了，这时可以创建一个新的数组，长度是旧数组的2倍，再把旧数组的元素复制过去，这就完成了数组的扩容。

如此一来，我们的插入元素的方法也需要改写了，改写的代码如下：

class MyArray:
    def __init__(self, capacity):
        self.array = [None] * capacity
        self.size = 0
        
    def insert_v2(self, index, element):
        # 判断访问下标是否超出范围
        if index < 0 or index > self.size:
            raise Exception("超出数组实际元素范围！")
        # 如果实际元素达到数组容量上线，数组扩容
        if self.size >= len(self.array):
            self.resize()
        # 从右向左循环，逐个元素向右挪一位
        for i in range(self.size-1, -1, -1):
            self.array[i+1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1
        
    def resize(self):
        array_new = [None] * len(self.array) * 2
        # 从旧数组复制到新数组
        for i in range(self.size):
            array_new[i] = self.array[i]
        self.array = array_new
    
    def output(self):
        for i in range(self.size):
            print(self.array[i])


array = MyArray(4)
array.insert_v2(0, 10)
array.insert_v2(0, 11)
array.insert_v2(0, 12)
array.insert_v2(0, 13)
array.insert_v2(0, 14)
array.insert_v2(0, 15)
array.insert_v2(1, 16)
array.output()

d. 删除元素

数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。

同样的，尝试一下自己实现删除元素的操作：

def remove(self, index):
    # 判断访问下标是否超出范围
    if index < 0 or index > self.size:
        raise Exception("超出数组实际元素范围！")
    # 从左到右，逐个元素向左挪一位
    for i in range(index, self.size):
        self.array[i] = self.array[i+1]
    self.size -= 1

 3. 数组的特点

数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。

至于数组的劣势，体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。

总的来说，数组所适合的是读操作多、写操作少的场景。