python数据结构之List

发布于 | 分类： .
字数统计
List是python中一种很常见的数据结构，他有很多内置的函数或者操作，这些函数很有用，在这里从函数的功能（参数和输出），使用的场景，时间复杂度几个方面分析下这些函数。

Python的list的实现不是类似数据结构中的单链表，而是类似数组，也就是说==list中的元素保存在一片连续的内存区域中==，这样的话只有知道元素索引就能确定元素的内存位置，从而直接取出该位置上的值，但是它的缺点在于前插需要移动元素，而且随着list中元素的增多需要移动的元素也就越多，花费的时间也就自然多了。而单链表不同，单链表要得到某个位置上的元素必须要从头开始遍历，但是它的插入操作(前插或者后插)基本上都是恒定的时间，与链表中元素的多少没有关系，因为元素之间用“==指针==”维护着他们的关系。

参考的一个博客的博主，他的观点认为python中的列表其实是动态表，类似于C++中的vector和Java中的ArrayList。可以看算法导论中对动态表的介绍。

  • 首先是list()函数，list()函数的作用是将字符转化成列表，举个例子：
    1
    2
    3
    4
    5
    6
    7
    8
    >>> word = "Hello"
    >>> name = list(word)
    >>> name
    ['H', 'e', 'l', 'l', 'o']
    >>> mystr = "Welcome to here!"
    >>> name = list(mystr)
    >>> name
    ['W', 'e', 'l', 'c', 'o', 'm', 'e', ' ', 't', 'o', ' ', 'h', 'e', 'r', 'e', '!']

参数就是字符串，在使用list()函数以后，字符串里面的每一个字符都作为列表中的元素，第二个例子中，向空格和叹号这样的字符也被划分成一个列表中的元素。

  • 接下来就是一些针对列表的操作：
    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
    >>> list = [1,'234','hello','!','']
    >>> list
    [1, '234', 'hello', '!', '']
    >>> list[0] = '3'
    >>> list
    ['3', '234', 'hello', '!', '']
    >>> type(list[0])
    <class 'str'>
    >>> list[0] = 3
    >>> list
    [3, '234', 'hello', '!', '']
    >>> type(list[0])
    <class 'int'>
    >>> list[0] = 3.01
    >>> type(list[0])
    <class 'float'>
    >>> list[0] = [0,1,2]
    >>> list
    [[0, 1, 2], '234', 'hello', '!', '']
    >>> type(list[0])
    <class 'list'>
    >>> list[0] = {1:'hello', 2:'word'}
    >>> list
    [{1: 'hello', 2: 'word'}, '234', 'hello', '!', '']
    >>> type(list[0])
    <class 'dict'>
    >>> list[0] = (1,2,3)
    >>> list
    [(1, 2, 3), '234', 'hello', '!', '']
    >>> type(list[0])
    <class 'tuple'>
    >>> list[0] = True
    >>> list
    [True, '234', 'hello', '!', '']
    >>> type(list[0])
    <class 'bool'>

这么看来list虽然在一些方面和数组很像，但是他们两个的差别还是很大的，就比如上面的例子中list中的元素的类型可以是各种各样的，在创建一个list的时候不用考虑类型的问题，也不用考虑大小的问题（至于为什么不用考虑后面再继续研究下）。在上面的例子中还用到了python中的一个内置的函数type()，这个函数的作用就是查看对象的数据类型，要知道，在python中一切都是对象，所以type()是一个很实用的函数，并且type()本身也是有类型的，它是type类型的。

1
2
>>> type(type(list[0]))
<class 'type'>

  • 分片操作，类比数组就是取得子数组，但是python中的list的分片操作是很方便的。
    1
    2
    3
    4
    >>> listme = [1,2,3,4,5]
    >>> listme1 = listme[1:3]
    >>> listme1
    [2, 3]

在这里，通过标记索引来获得切片，比如这里的listme1 = listme[1:3]，冒号左边是起始元素的索引，冒号右边是结束元素后面一个位置的索引，在例子中就是从listme[1]到listme[3-1]，也就是listme[2]，得到的切片包含两个元素，listme1 = [listme[1],listme[2]]。

1
2
3
4
5
6
7
8
9
10
>>> num  = [0,1,2,3,4,5,6,7,8,9,10]
>>> num1 = num[3:]
>>> num1
[3, 4, 5, 6, 7, 8, 9, 10]
>>> num2 = num[:5]
>>> num2
[0, 1, 2, 3, 4]
>>> num3 = num[:]
>>> num3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在这里如果冒号左边的索引省略，则默认是从头开始；如果冒号右边的索引省略，则默认是一直到最后的元素。

  • 修改序列：

    1
    2
    3
    4
    >>> num  = [0,1,2,3,4,5,6,7,8,9,10]
    >>> num[1:] = 'hello'
    >>> num
    [0, 'h', 'e', 'l', 'l', 'o']

  • 插入序列：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    >>> num
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    >>> num[2:2] = [1,2,3]
    >>> num
    [0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    >>> mylist = ['he','hel','lo',1,2,3,'!','']
    >>> mylist
    ['he', 'hel', 'lo', 1, 2, 3, '!', '']
    >>> mylist[3:3] = 'follow me'
    >>> mylist
    ['he', 'hel', 'lo', 'f', 'o', 'l', 'l', 'o', 'w', ' ', 'm', 'e', 1, 2, 3, '!', '']

在插入的时候，如果插入的数据是列表或者字符串，那么列表的每项，字符串的每个字符都会作为列表的一个元素，而不是说列表或者字符串整体作为一个字符串插入。

那么问题来了，如果想作为整体插入该怎么办呢？

这时候要用到insert()函数，语法：list.insert(index, obj)。这个函数有两个参数第一个参数是要插入位置的索引，第二个参数是要插入的内容。

1
2
3
4
5
6
7
>>> mylist = ['he','hel','lo',1,2,3,'!','']
>>> mylist.insert(2,'Follow me')
>>> mylist
['he', 'hel', 'Follow me', 'lo', 1, 2, 3, '!', '']
>>> mylist.insert(1,[2,3,4])
>>> mylist
['he', [2, 3, 4], 'hel', 'Follow me', 'lo', 1, 2, 3, '!', '']

  • 删除序列：把要删除的部分置为空列表即可

    1
    2
    3
    4
    5
    6
    7
    8
    >>> mylist
    ['he', [2, 3, 4], 'hel', 'Follow me', 'lo', 1, 2, 3, '!', '']
    >>> mylist[2:] = []
    >>> mylist
    ['he', [2, 3, 4]]
    >>> mylist[1:len(mylist)] = []
    >>> mylist
    ['he']

  • count()函数，用来统计某个元素在列表中出现的次数。

    1
    2
    3
    >>> num = [1,2,3,3,4,5,6,7,5,4,6,7,8,3,0]
    >>> num.count(3)
    3

  • len()函数用来统计列表中元素的个数，有时候也是用来计算列表的长度。

    1
    2
    3
    >>> num = [1,2,3,3,4,5,6,7,5,4,6,7,8,3,0]
    >>> len(num)
    15

  • append()函数用来在列表的最后一个位置插入元素（类似于入栈操作）：

    1
    2
    3
    4
    5
    6
    7
    >>> num = [1,2,3,3,4,5,6,7,5,4,6,7,8,3,0]
    >>> num.append(10)
    >>> num
    [1, 2, 3, 3, 4, 5, 6, 7, 5, 4, 6, 7, 8, 3, 0, 10]
    >>> num.append('hello')
    >>> num
    [1, 2, 3, 3, 4, 5, 6, 7, 5, 4, 6, 7, 8, 3, 0, 10, 'hello']

Tips：可以使用“+”来实现列表的相加操作：

1
2
3
4
5
6
7
8
9
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> c = [7,8,9]
>>> d  = a + c + b
>>> d
[1, 2, 3, 7, 8, 9, 4, 5, 6]
>>> e = b + a +c
>>> e
[4, 5, 6, 1, 2, 3, 7, 8, 9]

  • extend函数，修改原来的序列，链接两个序列产生新的序列：
    1
    2
    3
    4
    5
    6
    7
    >>> a = [1,2,3]
    >>> b = ['1','2','3']
    >>> a.extend(b)
    >>> a
    [1, 2, 3, '1', '2', '3']
    >>> b
    ['1', '2', '3']

那么append()和extend()函数区别在哪里呢？个人认为一个是向列表的末尾逐个的插入新的元素，另一个是将另一个列表中的元素链接到前一个列表的后面。

  • pop()函数，弹出指定的列表中的元素，如果不指定索引的话，默认是弹出列表的最后一个元素。pop()函数将元素弹出来之后，原来列表中就没有这个元素了，可以看成是一种删除列表中的元素的方法。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    >>> a
    [1, 2, 3, '1', '2', '3']
    >>> b
    ['1', '2', '3']
    >>> a.pop()
    '3'
    >>> a
    [1, 2, 3, '1', '2']
    >>> a.pop(0)
    1
    >>> a
    [2, 3, '1', '2']

其实pop()和append()搭档可以类比栈和队列，如果是appen()之后使用pop()，可以看成是先进后出，类比栈结构。但是append()之后写一个循环去pop(0)的话，就可以看成先进先出，可以模仿队结构。

  • remove()函数，就是删除遇到的第一个指定的元素，这是在知道元素的值得时候。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    >>> num
    [1, 2, 3, 3, 4, 5, 6, 7, 5, 4, 6, 7, 8, 3, 0, 10, 'hello']
    # 因为只有一个1，所以删除了就没了
    >>> num.remove(1)
    >>> num
    [2, 3, 3, 4, 5, 6, 7, 5, 4, 6, 7, 8, 3, 0, 10, 'hello']
    # 但是3有多个，remove()函数就只是删除遇到的第一个符合条件的元素
    >>> num.remove(3)
    >>> num
    [2, 3, 4, 5, 6, 7, 5, 4, 6, 7, 8, 3, 0, 10, 'hello']
    # 那问题来了，如果一个元素在列表里面出现了很多次，怎样将他们全部删除呢？
    # 很简单啊，写个循环就好了，遇到这个元素就删掉，直到删光为止啊！
    >>> num
    [2, 3, 4, 5, 6, 7, 5, 4, 6, 7, 8, 3, 0, 10, 'hello']
    >>> while 3 in num:
    ...     num.remove(3)
    ... 
    >>> num
    [2, 4, 5, 6, 7, 5, 4, 6, 7, 8, 0, 10, 'hello']

  • index()函数，用来寻找与某个指定元素匹配的第一个索引（匹配项的位置：

    1
    2
    3
    4
    5
    6
    7
    8
    >>> num
    [2, 4, 5, 6, 7, 5, 4, 6, 7, 8, 0, 10, 'hello']
    >>> num.index(4)
    1
    >>> num.index(33)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    ValueError: 33 is not in list

  • reverse()函数，可以翻转列表：

    1
    2
    3
    4
    5
    >>> num
    [2, 4, 5, 6, 7, 5, 4, 6, 7, 8, 0, 10, 'hello']
    >>> num.reverse()
    >>> num
    ['hello', 10, 0, 8, 7, 6, 4, 5, 7, 6, 5, 4, 2]

  • sort()函数，用来对列表中的元素进行排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    >>> num
    ['hello', 10, 0, 8, 7, 6, 4, 5, 7, 6, 5, 4, 2]
    >>> num.sort()
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unorderable types: int() < str()
    >>> num.pop(0)
    'hello'
    >>> num
    [10, 0, 8, 7, 6, 4, 5, 7, 6, 5, 4, 2]
    >>> num.sort()
    >>> num
    [0, 2, 4, 4, 5, 5, 6, 6, 7, 7, 8, 10]

在这里，要排序的列表中的元素类型应该是一样的，

1
2
3
4
5
6
7
8
9
>>> mystr = ['Hello','1','!','last','follow me']
>>> mystr.sort()
>>> mystr
['!', '1', 'Hello', 'follow me', 'last']
>>> mystr.append(0)
>>> mystr.sort()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: int() < str()

那么在这里排序是按照什么来进行的呢？这个可以参考一下大神们的博客：http://blog.csdn.net/zyl1042635242/article/details/43115675

sor()函数会修改原来的序列，如果采用b = a的方式，那么对b排序之后，a也改变了。

1
2
3
4
5
6
7
>>> a = [2,3,1]
>>> b = a
>>> b.sort()
>>> b
[1, 2, 3]
>>> a
[1, 2, 3]

怎样做才能不会修改原来的列表呢？

两个方法，第一个方法就是使用sorted()函数：

1
2
3
4
5
6
>>> a = [1,4,3,1,6,7,4,8,9,2]
>>> b = sorted(a)
>>> b
[1, 1, 2, 3, 4, 4, 6, 7, 8, 9]
>>> a
[1, 4, 3, 1, 6, 7, 4, 8, 9, 2]

另一种方法就是创建副本：

1
2
3
4
5
6
7
8
9
10
>>> a
[1, 4, 3, 1, 6, 7, 4, 8, 9, 2]
>>> b = a[:]
>>> b
[1, 4, 3, 1, 6, 7, 4, 8, 9, 2]
>>> b.sort()
>>> b
[1, 1, 2, 3, 4, 4, 6, 7, 8, 9]
>>> a
[1, 4, 3, 1, 6, 7, 4, 8, 9, 2]

在这里如果b = a,那么a和b指向的就是同一个列表，如果b = a[:]，那么b就是创建的一个a的副本，对b的操作不会影响到a。

  • 关键字排序:key，举个例子一个元素都是字符串的列表中，按照字符串的长度来进行排序：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    >>> mystr
    ['!', '1', 'Hello', 'follow me', 'last', 0]
    >>> mystr.sort(key = len)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: object of type 'int' has no len()
    >>> mystr.pop()
    0
    >>> mystr.sort(key = len)
    >>> mystr
    ['!', '1', 'last', 'Hello', 'follow me']

  • 关键词排序，reverse。因为sort()函数默认是按照从小到大排序的也就是升序排序，但是如果想按照从大到小排序也就是降序排序的话，需要指定关键字reverse，因为默认是False，所以要设置成True。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    >>> mystr
    ['!', '1', 'last', 'Hello', 'follow me']
    >>> mystr.sort(reverse = True)
    >>> mystr
    ['last', 'follow me', 'Hello', '1', '!']
    >>> a
    [1, 4, 3, 1, 6, 7, 4, 8, 9, 2]
    >>> a.sort()
    >>> a
    [1, 1, 2, 3, 4, 4, 6, 7, 8, 9]
    >>> a.sort(reverse = True)
    >>> a
    [9, 8, 7, 6, 4, 4, 3, 2, 1, 1]

  • cmp()函数，用来比较两个元素的大小。==但是python3.x中已经没有了cmp()函数，如果想要比较两个元素大小的话，需不要import进operator模块，==

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    operator.lt(a, b)
    operator.le(a, b)
    operator.eq(a, b)
    operator.ne(a, b)
    operator.ge(a, b)
    operator.gt(a, b)
    operator.__lt__(a, b)
    operator.__le__(a, b)
    operator.__eq__(a, b)
    operator.__ne__(a, b)
    operator.__ge__(a, b)
    operator.__gt__(a, b)
    >>> import operator
    >>> operator.eq('hello', 'name');
    False
    >>> operator.eq('hello', 'hello');
    True

  • set()函数，用来过滤掉列表中的重复的元素，也就是如果一个列表中有一个元素重复了很多次，使用set()函数之后只留下一个。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    >>> a
    [9, 8, 7, 6, 4, 4, 3, 2, 1, 1]
    >>> a.append(4)
    >>> a
    [9, 8, 7, 6, 4, 4, 3, 2, 1, 1, 4]
    >>> c = set(a)
    >>> c
    {1, 2, 3, 4, 6, 7, 8, 9}
    >>> c[2]
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: 'set' object does not support indexing
    >>> set([4,4,4,3,4,2,1,3,4,1,1,1,1,1,2])
    {1, 2, 3, 4}

set()完成之后，输出结果集合，集合中的元素是没有顺序的，所以再按照索引寻找元素就会出错。可以看得出来，每次转换成集合，里面的元素都是已经排好序的。

删除列表中的元素可以用del(), pop(), remove()三种方法：

  • 首先del()方法的参数是按照索引寻找的列表的元素，这种方法必须知道要删除的元素的索引。这个方法没有任何的返回值。

    1
    2
    3
    4
    5
    >>> mylist
    ['3', '6', '1', '3', '2', '1']
    >>> del mylist[0]
    >>> mylist
    ['6', '1', '3', '2', '1']

  • 接下来pop()是将要删除的元素弹出来，并且删除该元素，这个方法也需要知道要删除的元素的索引，返回的是要删除的元素的值。

    1
    2
    3
    4
    5
    6
    >>> mylist
    ['6', '1', '3', '2', '1']
    >>> mylist.pop(3)
    '2'
    >>> mylist
    ['6', '1', '3', '1']

  • 最后是remove()这个是可以按照元素的值删除列表中的元素的。我们要先知道要删除的元素的值，将这个值作为参数传入到这个方法。看下面的代码可以知道，当列表中出现重复的元素的时候，也就是值相同的元素的时候，remove()方法就删除掉从前往后第一个这个值的元素，也就是索引值最小的那个。而且remove()是列表的一个属性方法，不能脱离列表单独使用。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> mylist
    ['6', '1', '3', '1']
    >>> mylist.remove('1')
    >>> mylist
    ['6', '3', '1']
    >>> remove(mylist[1])
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    NameError: name 'remove' is not defined

  • 未完待续