【大模型2609·数据结构算法·02】线性存储基石：动态数组手写实现与扩容机制

专栏导读：数组是内存中最纯粹的连续存储结构。本篇从底层定长内存寻址出发，手把手实现功能完备的自定义动态数组类：详尽攻克指定索引插入/删除的数据搬移机制、元素更新查找与迭代器协议，并深度剖析 1.5/2 倍均摊时间复杂度动态扩容原理。

数组

数组的概述

数组是一种线性数据结构，将相同类型的元素顺序地存储在连续的内存空间中，每个元素都有一个索引。

image4.png

由于数组元素在内存中是连续存储的，所以只要知道数组的起始位置，以及数组元素的类型（单个元素的长度），就可以根据索引计算出任意元素的位置。

数组在创建时需要指定长度，并且数组一旦创建，长度就无法改变，如果需要扩容，只能创建一个更大的数组，再将原数据拷贝到新数组。并且由于数组的连续性，插入和删除数据可能需要移动其他元素。

在 Python 中，并没有像其他一些编程语言（如 C、Java）那样严格意义上的 “数组” 概念，但有多种数据结构可以用来模拟数组的功能，最常用的是列表（list），另外还有 array 模块的数组和 numpy 库的 ndarray。

通过Python 的list列表实现一个动态数组，它内部存储的实际上是对象的引用（指针），而不是对象本身。每个引用指向内存中存储实际对象的位置。

数组的功能定义

方法 说明
size() 返回数组中元素个数
is_empty() 判断数组是否为空
insert(index, item) 在指定位置插入元素
append(item) 在末尾插入元素
remove(index) 删除指定位置的元素
set(index, item) 修改指定位置的元素
get(index) 获取指定位置的元素
find(item) 查找数组中某个元素的位置
for_each(func) 遍历数组

数组的创建

实现一个动态数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Array:
    def __init__(self):
        """初始化数组"""
        self.__capacity = 8
        self.__size = 0
        self.__items = [0] * 8

    def __str__(self):
        """打印数组"""
        arr_str = "["
        for i in range(self.__size):
            arr_str += str(self.__items[i])
            if i < self.__size - 1:
                arr_str += ", "
        arr_str += "]"
        return arr_str

    @property
    def size(self):
        """获取数组元素个数"""
        return self.__size

    def is_empty(self):
        """判断数组是否为空"""
        return self.__size == 0

数组扩容

当数组容量占满后，我们可以创建一个新的数组，容量为之前数组的2倍，并将之前数组的元素拷贝到新数组中。

1
2
3
4
5
6
7
def __grow(self):
    """数组扩容"""
    self.new___items = [0] * self.__capacity * 2
    for i in range(self.__size):
        self.new___items[i] = self.__items[i]
    self.__items = self.new___items
    self.__capacity *= 2

插入元素

在中间插入元素时，将指定位置及其之后的元素全部向后移动一个位置，并将指定位置改为新的元素。

image5.png

1
2
3
4
5
6
7
8
9
10
def insert(self, index, item):
    """插入元素"""
    if index < 0 or index > self.__size:
        raise IndexError
    if self.__size == self.__capacity:
        self.__grow()
    for i in range(self.__size, index, -1):
        self.__items[i] = self.__items[i - 1]
    self.__items[index] = item
    self.__size += 1

在末尾插入元素时，使用insert()并将index设置为数组长度。

1
2
3
def append(self, item):
    """末尾插入元素"""
    self.insert(self.__size, item)

删除元素

删除数组中指定位置的元素时，将该位置之后的所有元素向前移动一个位置。

image6.png

1
2
3
4
5
6
7
def remove(self, index):
    """删除元素"""
    if index < 0 or index >= self.__size:
        raise IndexError
    for i in range(index, self.__size - 1):
        self.__items[i] = self.__items[i + 1]
    self.__size -= 1

修改元素

1
2
3
4
5
def set(self, index, item):
    """修改元素"""
    if index < 0 or index >= self.__size:
        raise IndexError
    self.__items[index] = item

访问元素

1
2
3
4
5
def get(self, index):
    """访问元素"""
    if index < 0 or index >= self.__size:
        raise IndexError
    return self.__items[index]

查找元素

1
2
3
4
5
6
def find(self, item):
    """查找元素"""
    for i in range(self.__size):
        if self.__items[i] == item:
            return i
    return -1

遍历数组

1
2
3
4
def for_each(self, func):
    """遍历数组"""
    for i in range(self.__size):
        func(self.__items[i])

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Array:
    def __init__(self):
        """初始化数组"""
        self.__capacity = 8
        self.__size = 0
        self.__items = [0] * 8

    def __str__(self):
        """打印数组"""
        arr_str = "["
        for i in range(self.__size):
            arr_str += str(self.__items[i])
            if i < self.__size - 1:
                arr_str += ", "
        arr_str += "]"
        return arr_str

    @property
    def size(self):
        """获取数组元素个数"""
        return self.__size

    def is_empty(self):
        """判断数组是否为空"""
        return self.__size == 0

    def __grow(self):
        """数组扩容"""
        self.new___items = [0] * self.__capacity * 2
        for i in range(self.__size):
            self.new___items[i] = self.__items[i]
        self.__items = self.new___items
        self.__capacity *= 2

    def insert(self, index, item):
        """插入元素"""
        if index < 0 or index > self.__size:
            raise IndexError
        if self.__size == self.__capacity:
            self.__grow()
        for i in range(self.__size, index, -1):
            self.__items[i] = self.__items[i - 1]
        self.__items[index] = item
        self.__size += 1

    def append(self, item):
        """末尾插入元素"""
        self.insert(self.__size, item)

    def remove(self, index):
        """删除元素"""
        if index < 0 or index >= self.__size:
            raise IndexError
        for i in range(index, self.__size - 1):
            self.__items[i] = self.__items[i + 1]
        self.__size -= 1

    def set(self, index, item):
        """修改元素"""
        if index < 0 or index >= self.__size:
            raise IndexError
        self.__items[index] = item

    def get(self, index):
        """访问元素"""
        if index < 0 or index >= self.__size:
            raise IndexError
        return self.__items[index]

    def find(self, item):
        """查找元素"""
        for i in range(self.__size):
            if self.__items[i] == item:
                return i
        return -1

    def for_each(self, func):
        """遍历数组"""
        for i in range(self.__size):
            func(self.__items[i])