python内置数据结构大起底-List篇

python内置的多种数据结构为编程提供了相当的便利，灵活的使用python中的内置数据类型可以达到事半功倍的效果，本文是对Python一些常用数据类型的整理，并列举出来了一些使用技巧。

使用最多的数据结构 list

list内置了许多方法，常用的如：

1. list.append(x)
2. list.insert(i,x)
3. list.remove(x)
4. list.pop(i)
5. list.index(x, start, end)
6. list.sort(key, reverse)
7. list.reverse()
8. list.copy()

…

上面的方法中，根据字面意思就能知道方法的作用，灵活使用这些方法，可以实现出来其他的数据结构。

使用list实现stack

stack是一个后进先出的数据结构，不理解stack的可以参看我的这篇博客,他的接口一般被这样定义：

// Stack 接口，java代码表示
public Interface Stack<Item>{
    // 添加一个元素
    public void push(Item item); 

    // 移除最后添加的元素,并返回这个元素
    public Item pop();

    // 空监测
    public isEmpty();
}

在python的list中，pop()方法依旧存在，使用不带参数的pop方法，就会从移除list最后一个元素，而push()方法则等价于list的append方法。所以可以直接把list当做stack来使用。

stack = []
stack.append('a')  # stack = ['a']
stack.append('b')  # stack = ['b']
last = stack.pop() # last='b', stack=['a']

如果你觉得这样做不是很安全，万一一不小心调用了别的方法，很容易破坏数据结构，那么你可以使用list自己实现一个Stack(虽然这看上去有点脱裤子放屁)：

class Stack:
    def __init__(self):
        ¦   self._stack = []
    
    def is_empty(self):
        return False if self.stack else True

    def pop(self):
    return self._stack.pop()

    def push(self, item):
        self._stack.append(item)

    def __iter__(self):
        for item in self._stack:
            yield item

使用list实现queue

queue的特点是先进先出，不理解queue的可以参看我的这篇文章，queue的接口一般包含如下几种方法：

// Queue接口，java代码表示
public Interface Queue<Item>{
    // 入队操作，添加到最右（后）
    public void enqueue(Item);
    //出队操作，移除最早入队的（最左边）
    public Item dequeue();
    public isEmpty();
}

值得庆祝的是，当我们要使用queue的时候并不要自己去编写一个queque的结构，直接使用python
collections模块里面的deque即可，当然你也可以尝试自己实现。

deque保留了list的append方法，但是有而外的添加了一个popleft方法，从而实现了dequeque的操作。

from collections import deque
queue = deque()
queue.append(1) # [1]
queue.append(2) # [1, 2]
queue.append(3) # [1, 2, 3]
first = queue.popleft() # first=1, queue=[2, 3]

list Comprehensions 列表推导

python官方文档列出了三中创建列表的方式，他们分别是迭代器，lambda和列表推导

# 使用迭代去
squares = []
for x in range(10):
    squares.append(x**2)

# 使用lambda
squares = list(map(lambda x:x**2, range(10)))

# 使用列表推导
squares = [x**2 for x in range(10)]

列表推导式可以让代码变得更加简洁，解决2SUM问题，使用列表推导只需要一行代码即可暴力求解：

# 从1到100，两两组合，求所有合为105的组合
[(x, y) for x in range(1,101) y in range(1,101) if (x != y and x+y == 105)]

列表推导式还支持嵌套,如生成一个二维数组

# 生成一个5*5的二维数组
[[i for i in range(5)] for col in range(5) ]

del操作

list之所以能够把很多不同类型的数据放在一个集合里面，其他原因在于python的引用特性，所以对于列表内的任何一个元素都可以直接del。

a = [1, 2, 3, 4, 5]
del a[0] # 可以直接del
del a[2:4] # 也可以按照范围del，范围是左闭右开[2:4)

引用的陷阱

[[i for i in range(5)] for col in range(5) ]

这是上面用来创建二维数组的例子，有些比较聪明的人，可能会想到利用python的语言特性，与时代吗可能会这么写：

[[i for i in range(5)] * 5]

这看上去很简洁，并且两段代码输出的内容确实一毛一样的，但这并不称得上是聪明，简直愚蠢。事实上，当你尝试修改二维数组的任何一列的时候，每一列都会被改变。

a = [[i for i in range(5)] * 5]
# output a:
# [
#    [1,2,3,4,5],
#    [1,2,3,4,5],
#    [1,2,3,4,5],
#    [1,2,3,4,5],
#    [1,2,3,4,5],
# ]
a[0][0] = 5
# output a:
# [
#    [5,2,3,4,5],
#    [5,2,3,4,5],
#    [5,2,3,4,5],
#    [5,2,3,4,5],
#    [5,2,3,4,5],
# ]

出现上面巨大bug的原因就是，内存中事实上只创建了a[0]，后面的几列由于使用的是*操作符，都没有创建新的内存空间，本质上他们是同一块内存块。

copy和deepcopy

同样的问题还会出现在数组拷贝的时候。

a = [[1,2,3], [4,5,6]]
b = a.copy()
a[0][0] = [9]
print(a, b)

上面的代码使用list的copy方法，把a复制了一份给b，按照字面意思理解，也就是说重新开辟了一块儿内存空间，并把a的内容copy进去，这样a和b就完全是两个独立的内存空间了。

但事实上上面的代码，修改了a[0][0]之后，b[0][0]紧跟着也变成了9.这就有点匪夷所思了。这是由于拷贝的深度有限，list默认的copy在一维数组使用并没有太大问题，但一旦数组内包含了其他深一层的引用，copy只会复制最上层，这样对于两块内存块来说，再往下一层，本质上还是使用了同一块内存块。所以就发生了上面匪夷所思的问题。

解决问题的办法是使用深拷贝,python
的list并没有实现deepcopy，但我们可以在copy模块中找到他。

import copy
a = [[1,2,3], [4,5,6]]
b = copy.deepcopy(a)

然后从最外层到最内层，完完全全的拷贝了a，a与b再也不会有哪一个元素共同同一块儿内存了。

总结

python对list的实现和功能的设计恰到好处，既不感到臃肿，又绝对够用，毕竟他是python数据结构的核心。在某些情况下你也可以选择不使用list，这个时候可以参见python的collections模块，寻找其他适合你的集合类型。