Python数据结构（一）List使用

小咪咪 2024-04-18 14:23 73阅读 0赞

## List是什么？ ##

List顾名思义就是列表，那么它具体描述是什么呢？  
列表是一个线性的集合，它允许用户在任何位置插入、删除、访问和替换元素。在Python中list是保留字，List中的每个元素都有自己的编号，很像C、C++、java中的数组，但是List更强大。列表主要有以下几个特点：

*  列表中元素顺序是有序的。比如，你将1,2,3一次存入列表，那个列表中元素顺序一定是1,2,3，而不会是其他的。
 *  列表长度不确定。不同于C/C++里的数组，列表长度不确定，在使用列表时不需要提前声明长度。
 *  列表中存储的元素类型可以不唯一。可以将任何东西加入列表中，其中元素之间可以没有任何关系。
 *  列表中可以有重复元素。

![在这里插入图片描述][20190908010501404.png]

### List简单使用 ###

##### 1. 列表创建 #####

创建一个列表，只要把逗号分隔的不同的数据项使用方括号括起来即可。如下所示：

list1 = [1, 2, 3, 4, 5 ] # 这是注释
    list2 = ['physics', 'chemistry', 1997, 2000] #列表里数据类型可以不一致
    list3 = ["a", "b", "c", "d"]

此外，如果创建一些常用的数列等列表，可采取以下pythonic的方法快速创建列表：

list4 = [0] * 5
    # [0, 0, 0, 0, 0]
    list5 = [0 for _ in range(5)]
    # [0, 0, 0, 0, 0]
    list6 = [i for i in range(5)]
    # [0, 1, 2, 3, 4]
    list7 = list(range(5))
    # [0, 1, 2, 3, 4]

##### 2. 列表访问 #####

列表访问和其他数组访问差不多，常用索引。但是python列表可以切片，可以取指定索引区间内的元素。

list1 = [1, 2, 3, 4, 5]
    print("list1[0]: ", list1[0])  # list索引
    # list1[0]: 1
    
    print("list1[0:2]: ", list1[0:2])  # list切片
    # list1[0:2]: [1, 2]
    
    for i in range(len(list1)):  # 循环遍历
        print(list1[i], end=" ")
    # 1 2 3 4 5
    
    for x in list1:  # 循环遍历, pythonic
        print(x, end=" ")
    # 1 2 3 4 5

##### 3. 操作列表的函数 #####

*  len(list)：列表元素个数
 *  max(list)：返回列表元素最大值
 *  min(list)：返回列表元素最小值
 *  list(seq)：将元组转换为列表
 *  del：删除列表，释放内存空间

例子：

list1 = [1, 2, 3, 4, 5]
    print(len(list1)) # 获取长度
    # 1
    print(max(list1)) # 最大值
    # 5
    print(min(list1)) # 最小值
    # 1
    
    t = (1, 2, 3, 4, 5) # 这是元组类型，不可改类型，以后细说
    print(t)
    # (1, 2, 3, 4, 5)
    list2 = list(t) # 将元组转化为列表，那么就可以更改元素了
    print(list2)
    # [1, 2, 3, 4, 5]

##### 3. 列表类型定义的函数 #####

*  list.append(obj)：在列表末尾添加新的对象
 *  list.count(obj)：统计某个元素在列表中出现的次数
 *  list.extend(seq)：在列表末尾一次性追加另一个序列中的多个值
 *  list.index(obj)：从列表中找出某个值第一个匹配项的索引位置
 *  list.insert(index, obj)：将对象插入列表
 *  list.pop(obj=list\[-1\])：移除列表中的一个元素（默认最后一个元素），并返回
 *  list.remove(obj)：移除列表中某个值的第一个匹配项
 *  list.reverse()：反向列表中元素
 *  list.sort(\[func\])：对原列表进行排序

例子：

l = [1, 2, 3, 4, 5]
    print(l)
    # [1,2,3,4,5]
    l.append(1)
    print(l)
    # [1, 2, 3, 4, 5, 1]
    print(l.count(1))
    # 2
    print(l.count(2))
    # 1
    
    ll = [1, 2, 3]
    l.extend(ll)
    print(l)
    # [1, 2, 3, 4, 5, 1, 2, 3]
    l = l + ll  # + 等同于上面extend操作 注意l上面已经变成[1, 2, 3, 4, 5, 1, 2, 3]了
    print(l)
    # [1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3]
    
    print(l.index(1))  # 返回第一次匹配的位置
    # 0
    l.insert(0, 6)  # 在第0位置插入6
    print(l)
    # [6, 1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3]
    
    print(l.pop())  # 默认取出最后一个元素，类似于栈
    # 3
    print(l.pop(0))  # 取出第一个元素，模拟队列
    # 6
    
    l.reverse()
    print(l)
    # [2, 1, 3, 2, 1, 1, 5, 4, 3, 2, 1]
    
    l.sort()
    print(l)
    # [1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5]

### list一些常见函数的时间复杂度 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">Operation</th> 
   <th align="left">Big-O Efficiency</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">index []</td> 
   <td align="left">O(1)</td> 
  </tr> 
  <tr> 
   <td align="left">append</td> 
   <td align="left">O(1)</td> 
  </tr> 
  <tr> 
   <td align="left">pop()</td> 
   <td align="left">O(1)</td> 
  </tr> 
  <tr> 
   <td align="left">pop(i)</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">insert(i,item)</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">del operator</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">iteration</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">contains (in)</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">get slice [x:y]</td> 
   <td align="left">O(k)</td> 
  </tr> 
  <tr> 
   <td align="left">del slice</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">set slice</td> 
   <td align="left">O(n+k)</td> 
  </tr> 
  <tr> 
   <td align="left">reverse</td> 
   <td align="left">O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">concatenate</td> 
   <td align="left">O(k)</td> 
  </tr> 
  <tr> 
   <td align="left">sort</td> 
   <td align="left">O(n log n)</td> 
  </tr> 
  <tr> 
   <td align="left">multiply</td> 
   <td align="left">O(nk)</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][20190908010839178.png]  
【附加阅读】

## 底层实现机制 ##

List对象是用c结构来实现，由一个保存元素的指针数组和预先分配的内存总容量构成。分离式结构，两者之间用一个元素建立一个链接，连在一起。能够根据元素的数量自动的扩充或者缩小list的内存大小。

要在内存中给集合开辟一块区域，总得先确定大小（容量），不然如何开辟？另外，确定区域后，还要知道当前已经占用了几个元素（元素个数），一旦溢出，就需要重新申请空间。要表达这种结构，有两种实现方式。一种是把头信息和元素串到一起，形成一个元素个数+2的表。另一种就是把头信息和元素分开放，两者之间用一个元素建立一个链接，连在一起。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjAzNDI1_size_16_color_FFFFFF_t_70]  
存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

分离式结构中表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。一旦表需要扩充，对于一体式结构来说，就要重新申请一块更大的空内存区域，将所有元素放入其中，再清空旧的内存区域。对于分离式结构来说，则需要将链接地址更新一下，顺序表对象是不变的。

List的扩充采取两种策略，每次扩充增加固定数目的存储位置，这种策略可称为线性增长，节省空间，但是扩充操作频繁，操作次数多。每次扩充容量加倍，以空间换时间。从实现上来讲，在python中创建空ist时，会申请一个8个元素大小的内存区域。以后如果满了，就扩容4倍，且当元素总数达到50000时，再扩容就改为2倍。

[20190908010501404.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/54dd5f42adec4c03a1d45fd74b8ea45d.png
[20190908010839178.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ce57357fa2f341edaff382c7502c620f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjAzNDI1_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b2a2e474a35d42c89858952d228cbb6e.png