一、list的基本实现技术
在数据结构中，如果用python实现线性表，无疑要提到list，list是一种元素个数可变的线性表(而tuple是不变的表，不支持改变其内部状态的任何操作，其他与list性质类似)，采用分离式技术实现的动态顺序表，表中元素保存在一块连续存储区内。实现约束有如下两点：
1、基于下标(位置)的高效元素访问和更新，时间复杂度是O(1)
2、允许任意添加元素，不可以出现由于表满而无法加入新元素的情况；而且在添加新元素之后，表对象标识不变。
在python的官方实现中，list的实现策略如下：
1、在建立空表(或很小的表)时，系统分配一块能容纳8个元素的存储区；
2、在执行insert或append等操作来扩充表时，如果元素区满就换一块4倍大的存储区，把所有元素copy过去；
3、如果当前的表已经“很大”(这里阈值为50000)，系统将改变策略，换存储区时容量加倍，这是为了避免出现过多的空闲存储位置。
注：python没有提供检查一个list对象的当前存储块容量的操作，也没有设置容量的操作，一切与容量有关的处理都由Python解释器自动完成，这和c++、java等有很大的区别。优点是降低了编程的负担，避免人为操作可能引进的错误。但全部交给解释器来完成也限制了表的使用方式。
小练习：list的内置方法reverse，自己实现的方法：
def my_reverse(lst):
elems = lst
i,j = 0, len(elems)-1
while i <j:
elems[i], elems[j] = elems[j], elems[i] #这里交换元素写在一行，不需要设置中间的temp作为交换媒介
i,j = i+1, j-1
return elems
a = [1,2,3,4,5,"a"]
print a
print '\nafter my reverse',my_reverse(a)
二、单链表类的实现
单链表的基础知识就不往上贴了，下面贴个python实现的实现类
1、利用循环创建一个简单的单链表
# -*- coding:utf-8 -*-
'''
简单的循环调用一个长度为10的单链表
'''
class LNode: #实现单链表的节点类
def __init__(self,elem, next_=None):
self.elem = elem
self.next = next_ #以next_命名，避免与标准函数next重名，这是python的命名习惯 llist1 = LNode(1)
p = llist1 for i in range(2,11):
p.next = LNode(i)
p = p.next p = llist1 #把链表的指针重新指向第一个节点
while p:
print p.elem
p = p.next
2、单链表类的实现
# -*- coding:utf-8 -*-
__author__ = 'webber'
'''单链表类的实现''' class LNode: #实现单链表的节点类
def __init__(self,elem, next_=None):
self.elem = elem
self.next = next_ #以next_命名，避免与标准函数next重名，这是python的命名习惯 class LinkedListUnderflow(ValueError): #继承标准异常的子类ValueError
pass class LList:
def __init__(self):
self._head = None def is_empty(self):
return self._head is None def prepend(self,elem):
self._head = LNode(elem,self._head) def pop(self):
if self._head is None: #无结点，引发异常
raise LinkedListUnderflow("in pop")
ele = self._head.elem
self._head = self._head.next
return ele def pop_last(self): #这里有两个特殊情况，表为空，或者表中只有一个元素，pop掉最后一个元素的时间复杂度为O(n)
if self._head is None: #空表，无结点，引发异常
raise LinkedListUnderflow("in pop_last")
p = self._head
if p.next is None: #表中只有一个元素
ele = p.elem
self._head = None
return ele
while p.next.next is not None: #直到p.next是最后的结点
p = p.next
ele = p.next.elem
p.next = None
return ele def append(self, elem):
if self._head is None:
self._head = LNode(elem)
return
p = self._head
while p.next:
p = p.next
p.next = LNode(elem) def printall(self):
p = self._head
while p:
print p.elem,
if p.next:
print ",",
p = p.next
print "" mlist1 = LList()
print mlist1.is_empty()
for i in range(10):
mlist1.prepend(i)
for i in range(11,20):
mlist1.append(i)
mlist1.printall()
print mlist1.is_empty()
for i in range(5):
mlist1.pop()
print "pop 5 个数据之后："
mlist1.printall()
3、表的遍历
python语言为内部汇集类型提供的遍历机制是迭代器，标准使用方式是放在for语句头部，在循环体中逐个处理汇集对象的元素，用yield实现。可在上面的单链表类中添加如下方法：
def elements(self):
p = self._head
while p is not None:
yield p.elem #返回结点元素
p = p.next for i in mlist1.elements():
print i,
筛选生成器：下面是一个筛选生成器的方法，可以将单链表中所有符合条件的结点元素返回，这里需要注意两点：一是关于yield和return的用法区别，yield使这个方法变成一个迭代器，每一次循环迭代器使用next方法返回一个值，而return如果执行的话，整个函数就结束了。二是这里在调用该方法时需要一个“判断谓词参数”，在python中可以使用lambda表达式定制这个操作参数，方法和调用如下：
def filter(self,pred): #筛选生成器
p = self._head
while p:
if pred(p.elem):
yield p.elem
p = p.next for i in mlist1.filter(lambda i:i>10): #谓词参数，返回单链表中元素大于10的元素
print i,