線性表分為順序表和鏈表。
順序表：將表中元素順序地存在一大塊連續(xù)的存儲(chǔ)區(qū)內(nèi)盗舰。元素間的順序關(guān)系由它們的存儲(chǔ)順序自然決定。
鏈表：將表中元素存放在通過鏈接結(jié)構(gòu)構(gòu)造起來的一系列存儲(chǔ)塊中。
順序表
優(yōu)點(diǎn)
定位元素訪問時(shí)間復(fù)雜度為O(1)。
缺點(diǎn)
加入/刪除操作代價(jià)高凤薛。（除了尾端插入和刪除時(shí)間復(fù)雜度為O(1)）姓建。如果程序中需要巨大線性表诞仓，可能造成存儲(chǔ)管理方面的困難缤苫。
部分操作代碼python：
#修改順序表自身，將其元素順序倒置
#算法復(fù)雜度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
單鏈表
每個(gè)節(jié)點(diǎn)里只儲(chǔ)存一個(gè)表元素墅拭。多鏈表暫不討論活玲。每個(gè)節(jié)點(diǎn)是一個(gè)二元組，存儲(chǔ)著elem和next谍婉。節(jié)點(diǎn)之間通過節(jié)點(diǎn)鏈接建立起單向的順序聯(lián)系舒憾。
定義一個(gè)簡單的表節(jié)點(diǎn)類：
#方法的第二參數(shù)用next_是為了避免與Python標(biāo)準(zhǔn)函數(shù)next重名
class LNode:
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_
加入元素
表首加入
- 創(chuàng)建一個(gè)新節(jié)點(diǎn)q并存入數(shù)據(jù)
- 原鏈表首節(jié)點(diǎn)head的鏈接存入新節(jié)點(diǎn)的next
- 修改表頭變量，使之指向新節(jié)點(diǎn)
#時(shí)間復(fù)雜度O(1)
q = LNode(13) //elem=13,next_=None
q.next = head.next
head = q
一般情況的元素插入
- 創(chuàng)建一個(gè)新節(jié)點(diǎn)q并存入數(shù)據(jù)
- 把之前的節(jié)點(diǎn)pre的next存入新節(jié)點(diǎn)q的next
- 修改pre的next穗熬，使之指向新節(jié)點(diǎn)q
#時(shí)間復(fù)雜度O(n)
q = LNode(13)
q.next = pre.next
pre.next = q
刪除元素
刪除表首元素
丟棄不用的節(jié)點(diǎn)將被Pyhton解釋器自動(dòng)回收
#O時(shí)間復(fù)雜度(1)
head = head.next
一般情況的元素刪除
#時(shí)間復(fù)雜度O(n)
pre.next = pre.next.next
掃描定位和遍歷
按下標(biāo)定位掃描
Pyhton慣例镀迂，鏈表首節(jié)點(diǎn)的元素應(yīng)該看作下標(biāo)為0。確定第i個(gè)元素所在的節(jié)點(diǎn)：
#如果一個(gè)表頭指針的值為None說明它所引用的鏈表已經(jīng)結(jié)束了
#輔助變量p為掃描指針
#每一個(gè)掃描循環(huán)必須用一個(gè)掃描指針作為控制變量
#每步迭代前都要檢查其值是否為None
#在Python中‘p is not None’可以簡寫成‘p’
p = head
while p is not None and i > 0:
i -= 1
p = p.next
按元素定位掃描
假設(shè)需要在鏈表里找到滿足謂詞pred的元素：
p = head
while p is not None and not pred(p.elem):
p = p.next
遍歷
完整的掃描稱作遍歷唤蔗。
Example1 建立一個(gè)鏈表
#節(jié)點(diǎn)元素取整數(shù)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 求鏈表長度：
#時(shí)間復(fù)雜度O(n)
def get_length(head):
p, n = head, 0
while p is not None:
n += 1
p = p.next
return n
單鏈表類定義探遵、初始化函數(shù)與常用操作
#定義節(jié)點(diǎn)類
class LNode:
def __init__(self, elem, next_= None):
self.elem = elem
self.next_ = next_
#定義鏈表類
class LinkedList:
#初始化函數(shù)，定義一個(gè)空鏈表
def __init__(self):
self._head = None
#prepend在頭鏈表加入新節(jié)點(diǎn)
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 " "
