动态数组【python】

本文将介绍一个简单的 Python 类 DynamicArray，用于实现动态数组的基本功能。动态数组是一种能够自动扩展和缩减容量的数据结构，具有高效的内存管理和快速的元素访问特性。

动态数组类定义

我们首先定义一个名为 DynamicArray 的类，包含以下实例变量：

• _array：存储实际数据的内部数组。
• _size：当前数组中的元素个数。
• _capacity：当前数组的容量。
  默认容量设置为 16。

class DynamicArray:
    '''动态数组
    self.__size    动态数组中的元素个数
    self._capacity 动态数组现在的容量
    '''
    DEFAULT_CAPACITY = 16 # 数组初始大小

    def __init__(self):
        self._array = [None] * self.DEFAULT_CAPACITY
        self._size = 0
        self._capacity = self.DEFAULT_CAPACITY # 实例变量：每个对象可以拥有自己的capacity

基本操作

获取数组大小、容量和判断empty

def size(self):
    return self._size

def capacity(self):
    return self._capacity

def is_empty(self):
    return self._size == 0

访问指定索引处的元素

def at(self, index):
    if index < 0 or index >= self._size:
        raise IndexError("Index out of range")
    return self._array[index]

添加元素

添加到数组末尾

def push(self, item):
    if self._size == self._capacity:
        self.__resize(self._capacity  * 2)
    self._array[self._size] = item
    self._size += 1

在指定位置插入元素

def insert(self, index, item):
    '''在指定位置index处插入元素item'''
    if index < 0 or index > self._size:
        raise IndexError("Index out of range")

    if self._capacity == self._size:
        self.__resize(self._capacity * 2)

    for i in range(self._size, index, -1):
        self._array[i] = self._array[i - 1]

    self._array[index] = item
    self._size += 1

在数组开头插入元素

def prepend(self, item):
    '''在开头插入元素item'''
    self.insert(0, item)

删除元素

删除末端元素

def pop(self):
    '''删除末端元素，并返回其值'''
    if self._size == 0:
        raise IndexError('Pop from empty DynamicArray')

    temp = self._array[self._size - 1]
    self._array[self._size - 1] = None

    self._size -= 1
    return temp

删除指定索引处的元素

def delete(self, index):
    '''删除指定索引的元素，并把后面的元素依次前移；如果需要彻底清除旧元素，可以在调整数组大小后将最后一个元素设为 None。'''
    if index < 0 or index >= self._size:
        raise IndexError('Index out of range')

    for i in range(index, self._size - 1):
        self._array[i] = self._array[i + 1]
    self._array[self._size - 1] = None
    self._size -= 1

删除指定值的所有元素

def remove(self, item):
    '''删除动态数组中所有的item，并返回其索引;可使用delete函数删除指定索引的元素'''
    index = DynamicArray()
    for i in range(self._size):
        if self._array[i] == item:
            index.push(i)

    for i in range(index._size - 1, -1, -1):
        self.delete(index.at(i))

    return index

查找元素

def find(self, item):
    '''寻找指定值的元素并返回第一个出现的元素其索引，未找到返回-1'''
    for i in range(self._size):
        if self._array[i] == item:
            return i
    return -1

内部方法

调整数组容量

def __resize(self, new_capacity):
    '''原数组空间不够，将其扩充'''
    old = self._array
    self._array = [None] * new_capacity

    for i in range(self._size):
        self._array[i] = old[i]

    self._capacity = new_capacity

打印数组

def __str__(self):
    return f'{[i for i in self._array[: self._size]]}'

测试代码

通过以下代码测试 DynamicArray 类的功能：

def main():
    arr = DynamicArray()
    for i in range(16):
        arr.push(i % 5)

    print(arr) # [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0]
    print(arr.capacity()) # 16
    arr.prepend(111)
    print(arr.capacity()) # 32

if __name__ == '__main__':
    main()

以上测试代码将动态数组填充到其初始容量，然后在数组开头插入一个元素，观察数组容量的变化。插入操作触发扩容，使容量从 16 增加到 32。

完整代码

class DynamicArray:
	'''动态数组
	self.__size    动态数组中的元素个数
	self._capacity 动态数组现在的容量
	'''
	DEFAULT_CAPACITY = 16 # 数组初始大小

	def __init__(self):
		self._array = [None] * self.DEFAULT_CAPACITY
		self._size = 0
		self._capacity = self.DEFAULT_CAPACITY # 实例变量：每个对象可以拥有自己的capacity

	def size(self):
		return self._size

	def capacity(self):
		return self._capacity

	def is_empty(self):
		return self._size == 0

	def at(self, index):
		if index < 0 or index >= self._size:
			raise IndexError("Index out of range")
		return self._array[index]

	def push(self, item):
		if self._size == self._capacity:
			self.__resize(self._capacity  * 2)
		self._array[self._size] = item
		self._size += 1

	def insert(self, index, item):
		'''在指定位置index处插入元素item'''
		if index < 0 or index > self._size:
			raise IndexError("Index out of range")

		if self._capacity == self._size:
			self.__resize(self._capacity * 2)

		for i in range(self._size, index, -1):
			self._array[i] = self._array[i - 1]

		self._array[index] = item
		self._size += 1

	def prepend(self, item):
		'''在开头插入元素item'''
		self.insert(0, item)

	def pop(self):
		'''删除末端元素，并返回其值'''
		if self._size == 0:
			raise IndexError('Pop from empty DynamicArray')

		temp = self._array[self._size - 1]
		self._array[self._size - 1] = None

		self._size -= 1
		return temp

	def delete(self, index):
		'''删除指定索引的元素，并把后面的元素依次前移；如果需要彻底清除旧元素，可以在调整数组大小后将最后一个元素设为 None。'''
		if index < 0 or index >= self._size:
			raise IndexError('Index out of range')

		for i in range(index, self._size - 1):
			self._array[i] = self._array[i + 1]
		self._array[self._size - 1] = None
		self._size -= 1

	def remove(self, item):
		'''删除动态数组中所有的item，并返回其索引;可使用delete函数删除指定索引的元素'''
		index = DynamicArray()
		for i in range(self._size):
			if self._array[i] == item:
				index.push(i)

		for i in range(index._size - 1, -1, -1):
			self.delete(index.at(i))

		return index

	def find(self, item):
		'''寻找指定值的元素并返回第一个出现的元素其索引，未找到返回-1'''
		for i in range(self._size):
			if self._array[i] == item:
				return i
		return -1


	def __str__(self):
		return f'{[i for i in self._array[: self._size]]}'

	def __resize(self, new_capacity):
		'''原数组空间不够，将其扩充'''
		old = self._array
		self._array = [None] * new_capacity

		for i in range(self._size):
			self._array[i] = old[i]

		self._capacity = new_capacity



def main():
	arr = DynamicArray()
	for i in range(16):
		arr.push(i % 5)

	print(arr) # [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0]
	print(arr.capacity()) # 16
	arr.prepend(111)
	print(arr.capacity()) # 32



if __name__ == '__main__':
	main()