线性表分为顺序表和链表。
顺序表：将表中元素顺序地存在一大块连续的存储区内。元素间的顺序关系由它们的存储顺序自然决定。
链表：将表中元素存放在通过链接结构构造起来的一系列存储块中。
顺序表
优点
定位元素访问时间复杂度为O(1)。
缺点
加入/删除操作代价高。（除了尾端插入和删除时间复杂度为O(1)）。如果程序中需要巨大线性表，可能造成存储管理方面的困难。
部分操作代码python：
#修改顺序表自身，将其元素顺序倒置
#算法复杂度O(n)
def reverse(self):
elems = self.elements
i, j = 0, len(elems)-1
while i < j:
elems[i], elems[j] = elems[j], elems[i]
i, j = i+1, j-1
单链表
每个节点里只储存一个表元素。多链表暂不讨论。每个节点是一个二元组，存储着elem和next。节点之间通过节点链接建立起单向的顺序联系。
定义一个简单的表节点类：
#方法的第二参数用next_是为了避免与Python标准函数next重名
class LNode:
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_
加入元素
表首加入
- 创建一个新节点q并存入数据
- 原链表首节点head的链接存入新节点的next
- 修改表头变量，使之指向新节点
#时间复杂度O(1)
q = LNode(13) //elem=13,next_=None
q.next = head.next
head = q
一般情况的元素插入
- 创建一个新节点q并存入数据
- 把之前的节点pre的next存入新节点q的next
- 修改pre的next，使之指向新节点q
#时间复杂度O(n)
q = LNode(13)
q.next = pre.next
pre.next = q
删除元素
删除表首元素
丢弃不用的节点将被Pyhton解释器自动回收
#O时间复杂度(1)
head = head.next
一般情况的元素删除
#时间复杂度O(n)
pre.next = pre.next.next
扫描定位和遍历
按下标定位扫描
Pyhton惯例，链表首节点的元素应该看作下标为0。确定第i个元素所在的节点：
#如果一个表头指针的值为None说明它所引用的链表已经结束了
#辅助变量p为扫描指针
#每一个扫描循环必须用一个扫描指针作为控制变量
#每步迭代前都要检查其值是否为None
#在Python中‘p is not None’可以简写成‘p’
p = head
while p is not None and i > 0:
i -= 1
p = p.next
按元素定位扫描
假设需要在链表里找到满足谓词pred的元素：
p = head
while p is not None and not pred(p.elem):
p = p.next
遍历
完整的扫描称作遍历。
Example1 建立一个链表
#节点元素取整数1到10的值
llist = LNode(1)
p = llist
for i in range(2,11):
p.next = LNode(i)
p = p.next
Example2 依次输出链表中各元素：
p = head
while p is not None:
print(p.elem)
p = p.next
Example3 求链表长度：
#时间复杂度O(n)
def get_length(head):
p, n = head, 0
while p is not None:
n += 1
p = p.next
return n
单链表类定义、初始化函数与常用操作
#定义节点类
class LNode:
def __init__(self, elem, next_= None):
self.elem = elem
self.next_ = next_
#定义链表类
class LinkedList:
#初始化函数，定义一个空链表
def __init__(self):
self._head = None
#prepend在头链表加入新节点
def prepend(self, elem):
self._head = LNode(elem, self._head)
def append(self, elem):
p = self._head
if p is None:
p = LNode(elem)
return
while p.next is not None:
p = p.next
p.next = LNode(elem)
def printall(self):
p = self._head
while p is not None:
print p.elem, " "
p = p.next
print " "
