Py008-02-01数据结构之列表

数据结构

相互之间存在一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成

  • 数据结构就是设计数据以何种方式组织并存储在计算机中。
  • 比如：列表/集合与字典等都是一种数据结构

数据结构的分类

  • 线性结构:数据结构中的元素存在一对一的相互关系
  • 树结构：数据结构中的元素存在一对多的相互关系
  • 图结构：数据结构中的元素存在多对多的相互关系

列表

  • 列表是如何存储的
  • 列表的下标查找，插入，删除操作的时间复杂度
  • python的列表是如何实现的

列表是如何存储的

  • 顺序存储，一块(一个接一个)连续的内存
1
2
3
4
5
6
7
32位机器上，一个整数四个字节32位
在c语言里的数组
arr = [1,2,3,4,5]
假设arr[0] 内存地址是100
整型变量占用4个字节
那么a[1] 的内存地址就是104
a[2] 的内存地址是 108 。。。

数组和列表两点不同

  • 数组元素类型要相同
  • 数组长度固定

通过li[index]的寻址过程和处理数组内数据类型不同问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
python中列表
li = [1,2,3]
针对常用的小整数python直接分配固定的内存
假设分配的addr
1 addr = 200
2 addr = 305
3 addr = 500
那么 li = [1,2,3]
32位机器上，一个整数四个字节32位
假设li[0] 的地址为 100  它里面存的是1的内存地址200
假设li[1] 的地址为 104  它里面存的是1的内存地址305 
假设li[2] 的地址为 108  它里面存的是1的内存地址500

这就是python列表解决 类型不同的问题

如何解决数组动态添加元素的问题

1
内存动态分配

append的时间复杂度

1
O(1)

插入和删除的时间复杂度

  • O(n)
1
2
3
4
5

[1,2,3,4,5,6]
删除第一个元素
1后面的元素都要把地址向前迁移一位
[2,3,4,5,6]