Python数组详解与封装：从基础到动态数组实现

一 python中的数组

1. 数组是学习python接触到的第一个数据结构，也是最简单的数据结构;

2. 数组基础

• 把数据码成一排进行存放就叫做数组;
• 数组中有一个很重要的概念叫做索引(注意：索引从0开始)；
• 使用数组的优点：可以根据索引快速查询；
• 数组最好应用于有“索引有语意”的情况；
• 并非所有有语意的索引都适用于数组，比如说使用身份证号查询某人的工资情况，这样的情况就需要考虑其他的数据结构了或者考虑使用索引没有语意的情况；
• 如果索引没有语意就会出现新的问题比如说：

1. 如上图所示，在索引没有语意的情况下，如何表示没有的元素？
2. 如何添加元素，如何删除元素？

---

二 基于python提供的数组二次封装出一个属于自己的数组

1. 封装一个基本数组

2. 示例代码

class ArrayTest:
    """
    数组测试类的Python实现
    """

    def __init__(self, capacity=10):
        """
        构造函数
        :param capacity: 数组的容量，默认为10
        """
        # 创建一个容量为capacity的数组（使用列表实现）
        self._data = [None] * capacity
        # 初始长度为0
        self._size = 0

    def get_size(self):
        """
        获取数组中的元素个数
        :return: 数组中元素的数量
        """
        return self._size

    def get_capacity(self):
        """
        获取数组容量
        :return: 数组的总容量
        """
        return len(self._data)

    def is_empty(self):
        """
        判断数组中是否有元素
        :return: 如果数组为空返回True，否则返回False
        """
        return self._size == 0

# 使用示例
if __name__ == "__main__":
    # 创建默认容量的数组
    arr1 = ArrayTest()
    print(f"默认数组容量: {arr1.get_capacity()}")
    print(f"数组大小: {arr1.get_size()}")
    print(f"数组是否为空: {arr1.is_empty()}")

    # 创建指定容量的数组
    arr2 = ArrayTest(20)
    print(f"\n指定容量数组容量: {arr2.get_capacity()}")
    print(f"数组大小: {arr2.get_size()}")
    print(f"数组是否为空: {arr2.is_empty()}")

参数说明：

• size：表示数组中元素的个数(后续的添加 删除等操作需要维护此属性)；
• data：声明的数组；
• capacity：不需要维护，因为当用户创建数组是需要传入数组的默认长度；
  

  ---

  2. 向数组中添加元素

2.1 向空数组添加元素

2.2 代码

def addlast(self, e):
    """
    向所有元素后添加一个新元素
    :param e:
    """
    # 判断数组长度与容量是否相等
    if self.size == len(self.data):
        raise ValueError("AddLast failed. Array is full.")
    # 向最后一个元素后边添加一个元素
    self.data[self.size] = e
    # 维护数组长度
    self.size += 1

2.3 向数组中任意一个位置添加新的元素

由上边图示可以看出，向指定索引添加元素的过程需要对数组其他位置的元素进行移动的操作，而且是从后向前移动(如果从前往后移动会覆盖掉下一个索引位置的元素)，最后还需要维护一下size属性；

2.4 代码

def add(self, index, e):
    """
    向指定索引位置插入元素
    :param index:
    :param e:
    """
    # 判断数组长度与容量是否相等
    if self.size == len(self.data):
        raise ValueError("AddLast failed. Array is full.")
    # 判断索引是否合法
    if index < 0 or index > self.size:
        raise ValueError("Add failed. Require index >= 0 and index <= size.")
    # 从后往前遍历遍历数组,实现数组中元素的位移
    for i in range(self.size - 1, index - 1, -1):
        # 将当前索引位置的元素移动至下一个索引位置上
        self.data[i + 1] = self.data[i]
    # 向指定索引位置插入元素
    self.data[index] = e
    # 维护数组长度
    self.size += 1

2.5 复用核心添加逻辑改造方法

def addlast(self, e):
    """
    向所有元素后添加一个新元素
    :param e:
    """
    # 复用核心的添加逻辑
    self.add(self.size, e)

def addFirst(self, e):
    """
    向数组的第一个位置添加一个元素
    :param e:
    """
    # 复用核心的添加逻辑
    self.add(0, e)

def add(self, index, e):
    """
    向指定索引位置插入元素
    :param index:
    :param e:
    """
    # 判断数组长度与容量是否相等
    if self.size == len(self.data):
        raise ValueError("AddLast failed. Array is full.")
    # 判断索引是否合法
    if index < 0 or index > self.size:
        raise ValueError("Add failed. Require index >= 0 and index <= size.")
    # 从后往前遍历遍历数组，实现数组中元素的位移
    i = self.size - 1
    while i >= index:
        # 将当前索引位置的元素移动至下一个索引位置上
        self.data[i + 1] = self.data[i]
        i -= 1
    # 向指定索引位置插入元素
    self.data[index] = e
    # 维护数组长度
    self.size += 1

3. 重写toString

def __str__(self):
    """
    toString
    :return:
    """
    # 创建新的容器
    string_builder = []
    # 设置格式
    string_builder.append(f"Array: size = {self.size} , capacity = {len(self.data)}\n")
    # 开始拼接返回值
    string_builder.append("[")
    # 使用循环进行拼接
    for i in range(self.size):
        # 向容器中装载元素
        string_builder.append(str(self.data[i]))
        # 判断是否是最后一个元素
        if i != self.size - 1:
            # 拼接分隔符
            string_builder.append(", ")
    # 闭合
    string_builder.append("]")
    # 返回
    return "".join(string_builder)

4 获取以及修改指定索引位置的元素

def get(self, index):
    """
    获取指定索引位置上的元素
    :param index:
    :return:
    """
    if index < 0 or index >= self.size:
        raise ValueError("Get failed, index is illegal.")
    return self.data[index]

def set(self, index, e):
    """
    修改指定索引位置的元素
    :param index:
    :param e:
    """
    if index < 0 or index >= self.size:
        raise ValueError("Set failed, index is illegal.")
    self.data[index] = e

注意：get方法对data进行了封装，调用者是无法调用到没有元素的索引位置的。

5 包含与搜索

def contains(self, e):
    """
    查看数组中是否包含某个元素
    @param e
    @return
    """
    # 遍历数组查询元素
    for i in range(self.size):
        # 判断当前位置元素是否是要找的元素
        if self.data[i] == e:
            # 返回结果
            return True
    # 返回结果
    return False

def find(self, e):
    """
    查找数组中元素e所在的索引,如果不存在元素e,则返回-1
    @param e
    @return
    """
    # 遍历数组查询元素
    for i in range(self.size):
        # 判断当前位置元素是否是要找的元素
        if self.data[i] == e:
            # 返回结果
            return i
    return -1

6 删除操作

6.1 删除操作过程图示

从以上图示中可以看出，删除操作与添加操作相似，删除操作是一个从后向前赋值的操作，通过将后一个元素赋值给前一个元素从而到达删除元素的目的；值得注意的是最后一个元素也就是size所在位置的元素在操作完成以后并没有被置为默认值，但是调用者是无法调用到这个位置的，所以可以不做处理；

6.2 代码

def remove(self, index):
    """
    删除指定索引位置的元素，并返回被删除的元素
    @param index
    @return
    """
    # 判断索引是否合法
    if index < 0 or index = self.size:
        raise ValueError("Remove failed, index is illegal.")
    # 记录要被删除的元素
    ret = self.data[index]
    # 通过遍历找到要被删除的元素
    for i in range(index + 1, self.size):
        # 从后向前进行赋值操作
        self.data[i - 1] = self.data[i]
    # 维护数组长度
    self.size -= 1
    # 返回结果
    return ret

def removeFirst(self):
    """
    删除数组中的第一个元素
    @return
    """
    return self.remove(0)

def removelast(self):
    """
    删除数组中的最后一个元素
    @return
    """
    return self.remove(self.size - 1)

def removeElement(self, e):
    """
    删除指定索引
    @param e
    """
    # 调用查询方法查找要删除元素的索引
    index = self.find(e)
    # 判断索引是否合法
    if index != -1:
        # 调用删除方法执行删除操作
        self.remove(index)

在删除操作中也使用了类似于添加操作的复用思想。

7 使用泛型改造数组
截止目前为止，封装的数组是int型的(也就是说只能存放int型的数据)，在python的概念中关于数组我们一般习惯性的称之为容器；所以我们需要对数组进行一定的改造，让它可以存放任何类型(这些类型包含python中的对象以及我们自己创建的数据类型比如：student、car)
下面看一下改造以后的代码：

class Array:
    """
    Created by yangxiaokai on 2018/5/27.
    """

    def __init__(self, capacity=None):
        """
        构造函数，传入数组的容量capacity构造Array
        @param capacity
        """
        if capacity is not None:
            # 创建数据，长度为capacity
            self.data = [None] * capacity
            # 长度为0
            self.size = 0
        else:
            # 无参数的构造函数，默认数组的容量capacity=10
            # 默认数组长度为10
            self.data = [None] * 10
            self.size = 0

    def getCapacity(self):
        """
        获取数组的容量
        @return
        """
        return len(self.data)

    def getSize(self):
        """
        获取数组中的元素个数
        @return
        """
        return self.size

    def isEmpty(self):
        """
        返回数组是否为空
        @return
        """
        return self.size == 0

    def addLast(self, e):
        """
        向所有元素后添加一个新元素
        @param e
        """
        self.add(self.size, e)

    def addFirst(self, e):
        """
        在所有元素前添加一个新元素
        @param e
        """
        self.add(0, e)

    def add(self, index, e):
        """
        在index索引的位置插入一个新元素e
        @param index
        @param e
        """
        # 判断索引是不是合法
        if index < 0 or index  self.size:
            raise ValueError("Add failed. Require index = 0 and index <= size.")
        # 通过遍历将数组中的元素进行位移
        for i in range(self.size - 1, index - 1, -1):
            if i = index:
                self.data[i + 1] = self.data[i]
        # 将新添加的元素放入到数组指定的索引位置上
        self.data[index] = e
        # 操作数组长度增加1
        self.size += 1

    def get(self, index):
        """
        获取索引index上的元素
        @param index
        @return
        """
        if index < 0 or index = self.size:
            raise ValueError("Get failed, index is illegal.")
        return self.data[index]

    def set(self, index, e):
        """
        设置索引index上的元素
        @param index
        @param e
        """
        if index < 0 or index = self.size:
            raise ValueError("Set failed, index is illegal.")
        self.data[index] = e

    def contains(self, e):
        """
        查询数组中是否包含元素e
        @param e
        @return
        """
        # 遍历数组查找元素
        for i in range(self.size):
            if self.data[i] == e:
                return True
        return False

    def find(self, e):
        """
        查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        @param e
        @return
        """
        # 遍历数组查找元素
        for i in range(self.size):
            if self.data[i] == e:
                # 返回索引
                return i
        return -1

    def remove(self, index):
        """
        从数组中删除index位置的元素, 返回删除的元素
        @param index
        @return
        """
        if index < 0 or index = self.size:
            raise ValueError("Remove failed, index is illegal.")
        # 记录被删除的元素
        res = self.data[index]
        # 通过遍历将数组中的元素进行位移
        for i in range(index + 1, self.size):
            # 索引考后的元素覆盖索引靠前的元素
            self.data[i - 1] = self.data[i]
        # 操作数组长度
        self.size -= 1
        # 将数组的最后一个位置上的元素置为空
        self.data[self.size] = None
        # 返回记录结果
        return res

    def removeFirst(self):
        """
        从数组中删除第一个索引上的元素并返回被删除的元素
        @return
        """
        return self.remove(0)

    def removeLast(self):
        """
        从数组中删除最后一个索引上的元素并返回被删除的元素
        @return
        """
        return self.remove(self.size - 1)

    def removeElement(self, e):
        """
        从数组中删除指定元素
        @param e
        """
        # 查询数组中是否有此元素
        index = self.find(e)
        # 根据结果判断
        if index != -1:
            self.remove(index)

    def __str__(self):
        """
        toString
        @return
        """
        # 创建新的容器
        builder = []
        # 设置数组格式
        builder.append(f"Array: size = {self.size} , capacity = {len(self.data)}\n")
        # 拼接返回值
        builder.append("[")
        for i in range(self.size):
            # 向容器中添加元素
            builder.append(str(self.data[i]))
            # 判断是否大于容器长度
            if i != self.size - 1:
                # 拼接分隔符
                builder.append(", ")
        # 闭合
        builder.append("]")
        # 返回
        return "".join(builder)

由于现在数组使用了泛型可以存放引用的数据类型，所以我们在删除的方法中需要将最后一个位置上的元素置为空，如果不置空的话将会影响垃圾回收，因为此位置上一直存在一个引用。

8 动态数组改造
截止目前为止，我们自己封装的数据还是一个静态的数组，但是静态数组有一个问题：每一次在初始化的时候对于数组的初始容量没有办法进行准确的预估，这就导致数组空间开辟过大会产生空间的浪费，开辟的过小又不够用的情况；所以我们需要一种自动的可伸缩的机制来实现数组容量的自动化管理来解决我们的这个问题。

8.1 动态数组图示

通过以上图示可以看出，当数组空间达到上限的时候我们可以创建一个容量更大的新数组，然后使用循环将之前数组中的元素放入新数组中，这样就实现了数组的扩容，就可以解决上面我们提到的静态数组空间的问题；对于删除的操作我们也可以采用这样的机制来实现；不过这个过程需要循环来将原来数组中的数据添加到新的数组中可能对于性能有一定的损耗，我们将在文章的最后来一起探究这个数组的性能问题。

8.2 代码

def __resize(self, newCapacity):
    """
    动态数组逻辑(扩容缩容)
    @param newCapacity
    """
    # 创建新的容器
    newData = [None] * newCapacity
    # 复制数组元素到新的数组
    for i in range(self.size):
        newData[i] = self.data[i]
    # 改变数组索引
    self.data = newData

def remove(self, index):
    """
    从数组中删除index位置的元素, 返回删除的元素
    @param index
    @return
    """
    if index < 0 or index = self.size:
        raise ValueError("Remove failed, index is illegal.")
    # 记录被删除的元素
    res = self.data[index]
    # 通过遍历将数组中的元素进行位移
    for i in range(index + 1, self.size):
        # 索引考后的元素覆盖索引靠前的元素
        self.data[i - 1] = self.data[i]
    # 操作数组长度
    self.size -= 1
    # 将数组的最后一个位置上的元素置为空
    self.data[self.size] = None
    # 数组缩容逻辑
    if self.size == len(self.data) // 4 and len(self.data) // 2 != 0:
        # 执行数组缩容
        self.__resize(len(self.data) // 2)
    # 返回记录结果
    return res

def add(self, index, e):
    """
    在index索引的位置插入一个新元素e
    @param index
    @param e
    """
    # 判断索引是不是合法
    if index < 0 or index  self.size:
        raise ValueError("Add failed. Require index = 0 and index <= size.")
    # 判断当前长度是不是大于数组长度,如果大于则进行扩容
    if self.size = len(self.data):
        self.__resize(len(self.data) * 2)
    # 通过遍历将数组中的元素进行位移
    for i in range(self.size - 1, index - 1, -1):
        if i = index:
            self.data[i + 1] = self.data[i]
    # 将新添加的元素放入到数组指定的索引位置上
    self.data[index] = e
    # 操作数组长度增加1
    self.size += 1

---

三 完整版代码

class Array:
    """
    Created by yangxiaokai on 2018/5/27.
    """

    def __init__(self, capacity=None):
        """
        构造函数，传入数组的容量capacity构造Array
        @param capacity
        """
        if capacity is not None:
            # 创建数据，长度为capacity
            self.data = [None] * capacity
            # 长度为0
            self.size = 0
        else:
            # 无参数的构造函数，默认数组的容量capacity=10
            # 默认数组长度为10
            self.data = [None] * 10
            self.size = 0

    def getCapacity(self):
        """
        获取数组的容量
        @return
        """
        return len(self.data)

    def getSize(self):
        """
        获取数组中的元素个数
        @return
        """
        return self.size

    def isEmpty(self):
        """
        返回数组是否为空
        @return
        """
        return self.size == 0

    def addLast(self, e):
        """
        向所有元素后添加一个新元素
        @param e
        """
        self.add(self.size, e)

    def addFirst(self, e):
        """
        在所有元素前添加一个新元素
        @param e
        """
        self.add(0, e)

    def add(self, index, e):
        """
        在index索引的位置插入一个新元素e
        @param index
        @param e
        """
        # 判断索引是不是合法
        if index < 0 or index  self.size:
            raise ValueError("Add failed. Require index = 0 and index <= size.")
        # 判断当前长度是不是大于数组长度,如果大于则进行扩容
        if self.size = len(self.data):
            self.__resize(len(self.data) * 2)
        # 通过遍历将数组中的元素进行位移
        for i in range(self.size - 1, index - 1, -1):
            if i = index:
                self.data[i + 1] = self.data[i]
        # 将新添加的元素放入到数组指定的索引位置上
        self.data[index] = e
        # 操作数组长度增加1
        self.size += 1

    def get(self, index):
        """
        获取索引index上的元素
        @param index
        @return
        """
        if index < 0 or index = self.size:
            raise ValueError("Get failed, index is illegal.")
        return self.data[index]

    def set(self, index, e):
        """
        设置索引index上的元素
        @param index
        @param e
        """
        if index < 0 or index = self.size:
            raise ValueError("Set failed, index is illegal.")
        self.data[index] = e

    def contains(self, e):
        """
        查询数组中是否包含元素e
        @param e
        @return
        """
        # 遍历数组查找元素
        for i in range(self.size):
            if self.data[i] == e:
                return True
        return False

    def find(self, e):
        """
        查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        @param e
        @return
        """
        # 遍历数组查找元素
        for i in range(self.size):
            if self.data[i] == e:
                # 返回索引
                return i
        return -1

    def remove(self, index):
        """
        从数组中删除index位置的元素, 返回删除的元素
        @param index
        @return
        """
        if index < 0 or index = self.size:
            raise ValueError("Remove failed, index is illegal.")
        # 记录被删除的元素
        res = self.data[index]
        # 通过遍历将数组中的元素进行位移
        for i in range(index + 1, self.size):
            # 索引考后的元素覆盖索引靠前的元素
            self.data[i - 1] = self.data[i]
        # 操作数组长度
        self.size -= 1
        # 将数组的最后一个位置上的元素置为空
        self.data[self.size] = None
        # 数组缩容逻辑
        if self.size == len(self.data) // 4 and len(self.data) // 2 != 0:
            # 执行数组缩容
            self.__resize(len(self.data) // 2)

        # 返回记录结果
        return res

    def removeFirst(self):
        """
        从数组中删除第一个索引上的元素并返回被删除的元素
        @return
        """
        return self.remove(0)

    def removeLast(self):
        """
        从数组中删除最后一个索引上的元素并返回被删除的元素
        @return
        """
        return self.remove(self.size - 1)

    def removeElement(self, e):
        """
        从数组中删除指定元素
        @param e
        """
        # 查询数组中是否有此元素
        index = self.find(e)
        # 根据结果判断
        if index != -1:
            self.remove(index)

    def __str__(self):
        """
        toString
        @return
        """
        # 创建新的容器
        builder = []
        # 设置数组格式
        builder.append(f"Array: size = {self.size} , capacity = {len(self.data)}\n")
        # 拼接返回值
        builder.append("[")
        for i in range(self.size):
            # 向容器中添加元素
            builder.append(str(self.data[i]))
            # 判断是否大于容器长度
            if i != self.size - 1:
                # 拼接分隔符
                builder.append(", ")
        # 闭合
        builder.append("]")
        # 返回
        return "".join(builder)

    def __resize(self, newCapacity):
        """
        动态数组逻辑(扩容缩容)
        @param newCapacity
        """
        # 创建新的容器
        newData = [None] * newCapacity
        # 复制数组元素到新的数组
        for i in range(self.size):
            newData[i] = self.data[i]
        # 改变数组索引
        self.data = newData