深入链表(most on lists)

The list data type has some more methods. Here are all of the methods of list objects:

list.append(x)

Add an item to the end of the list; equivalent to a[len(a):] = [x].

list.extend(L)

Extend the list by appending all the items in the given list; equivalent to a[len(a):] = L.

list.insert(i, x)

Insert an item at a given position. The first argument is the index of the element before which to insert, so a.insert(0, x) inserts at the front of the list, and a.insert(len(a), x) is equivalent to a.append(x).

list.remove(x)

Remove the first item from the list whose value is x. It is an error if there is no such item.

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

list.index(x)

Return the index in the list of the first item whose value is x. It is an error if there is no such item.

list.count(x)

Return the number of times x appears in the list.

list.sort()

Sort the items of the list, in place.

list.reverse()

Reverse the elements of the list, in place.

使用链表作为栈

链表方法使得链表可以很方便的做为一个堆栈来使用，堆栈是这样的数据结构，最先进入的元素最后一个被释放（后进先出）。用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如：

>>> stack = [3, 4, 5]

>>> stack.append(6)

>>> stack.append(7)

>>> stack

[3, 4, 5, 6, 7]

>>> stack.pop()

7

>>> stack

[3, 4, 5, 6]

>>> stack.pop()

6

>>> stack.pop()

5

>>> stack

[3, 4]

Using Lists as Queues

你也可以把链表当做队列使用，队列是这样的数据结构，最先进入的元素最先释放（先进先出）。使用 append()方法可以把元素添加到队列最后，以0为参数调用 pop() 方法可以把最先进入的元素释放出来。例如：

>>> queue = ["Eric", "John", "Michael"]

>>> queue.append("Terry")           # Terry arrives

>>> queue.append("Graham")          # Graham arrives

>>> queue.pop(0)

'Eric'

>>> queue.pop(0)

'John'

>>> queue

['Michael', 'Terry', 'Graham']

It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

lists可能不是高效的（对于fifo结构，因为需要移动整个结构）。

To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends. For example:

>>> from collections import deque

>>> queue = deque(["Eric", "John", "Michael"])

>>> queue.append("Terry")           # Terry arrives

>>> queue.append("Graham")          # Graham arrives

>>> queue.popleft()                 # The first to arrive now leaves

'Eric'

>>> queue.popleft()                 # The second to arrive now leaves

'John'

>>> queue                           # Remaining queue in order of arrival

deque(['Michael', 'Terry', 'Graham'])

del 语句

有一个方法可从链表中删除指定索引的元素：del语句。这个方法也可以从链表中删除切片（之前我们是把一个空链表赋给切片）。例如：

>>> a = [-1, 1, 66.6, 333, 333, 1234.5]

>>> del a[0]

>>> a

[1, 66.6, 333, 333, 1234.5]

>>> del a[2:4]

>>> a

[1, 66.6, 1234.5]

del 也可以用于删除整个变量：

>>> del a

此后再引用这个名字会发生错误（至少要到给它赋另一个值为止）。后面我们还会发现del的其它用法。