美文网首页
Python 数据结构 list

Python 数据结构 list

作者: __RY__ | 来源:发表于2018-08-17 11:02 被阅读1次

列表

  • 一个队列,一个排序整齐的队伍
  • 列表内的个体称为元素,由若干元素组成列表
  • 元素可以是任意对象(数字,字符串,对象,列表等)
  • 列表内元素有顺序,可以使用索引
  • 线性的数据结构
  • 使用[]表示
  • 列表是可变的

列表、链表、queue(队列)、stack(栈)的差异

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

queue

队列是一种特殊的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

stack

栈(英语:stack)又称为栈或堆叠,是计算机科学中一种特殊的串列形式的抽象数据类型,其特殊之处在于只能允许在链表或数组的一端(称为堆栈顶端指针,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。另外栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。

由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

列表list定义 初始化

  • list() -> new empty list
  • list(iterable) -> new list initialized from iterable's items
  • 列表不能一开始就定义大小

列表查询

  • index(value, [start, [stop]])

    • 通过值value,从指定区间查找列表内的元素是否匹配
    • 匹配第一个就立即返回索引
    • 匹配不到,抛出异常ValueError
  • count(value)

    • 返回列表中匹配value的次数
  • 时间复杂度

    • index和count方法都是O(n)
    • 随着列表数据规模的增大,而效率下降

列表增加、插入元素

  • append(object) -> None

    • 列表尾部追加元素,返回None
    • 返回None就意味着没有新的列表产生,就地修改
    • 时间复杂度是O(1)
  • insert(index, object) -> None -- insert object before index

    • 在制定的索引index出插入元素object

    • 返回None就意味着没有新的列表产生,就地修改

    • 时间复杂度是O(n)

    • 索引

      • 超过上界,尾部追加5
      • 超过下届,头部追加
  • extend(iterable) -> None -- extend list by appending elements from the iterable

    • 将可迭代对象的元素追加进来,返回None

    • 就地修改

  • + -> list

    • 连接操作,将两个列表连接起来
    • 产生新的列表,原列表不变
    • 本质上调用的是add()方法
  • * -> list

    • 重复操作,将本列表元素重复n次,返回新的列表

列表删除元素

  • remove(value) -> None -- remove first occurrence of value.

    • 从左至右查找第一个匹配value的值,移除该元素,返回None
    • 就地修改
    • 效率O(n),每删除一个元素其后面的元素都要往前移动
  • pop([index]) -> item -- remove and return item at index (default last).

    • 不指定索引index,就从列表尾部弹出一个元素
    • 指定索引index,就从索引出弹出一个元素,索引超界抛出IndexError错误
    • 效率O(1),指定索引的时间复杂度O(n),不指定索引O(1)
  • clear() -> None -- remove all items from L

    • 清除列表所有元素,剩下一个空列表

相关文章

网友评论

      本文标题:Python 数据结构 list

      本文链接:https://www.haomeiwen.com/subject/jhszbftx.html