上一篇文章為:→3.1.0鏈表
單向鏈表
單向鏈表也叫單鏈表惊暴，是鏈表中最簡單的一種形式饼丘，它的每個節(jié)點(diǎn)包含兩個域，一個信息域（元素域）和一個鏈接域辽话。這個鏈接指向鏈表中的下一個節(jié)點(diǎn)肄鸽，而最后一個節(jié)點(diǎn)的鏈接域則指向一個空值。
day24_鏈表-01.png
- 表元素域elem用來存放具體的數(shù)據(jù)屡穗。
- 鏈接域next用來存放下一個節(jié)點(diǎn)的位置（python中的標(biāo)識）
- 變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置贴捡，從p出發(fā)能找到表中的任意節(jié)點(diǎn)。
節(jié)點(diǎn)實(shí)現(xiàn)
class SingleNode(object):
"""單鏈表的結(jié)點(diǎn)"""
def __init__(self,item):
# _item存放數(shù)據(jù)元素
self.item = item
# _next是下一個節(jié)點(diǎn)的標(biāo)識
self.next = None
單鏈表的操作
- is_empty() 鏈表是否為空
- length() 鏈表長度
- travel() 遍歷整個鏈表
- add(item) 鏈表頭部添加元素
- append(item) 鏈表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 刪除節(jié)點(diǎn)
- search(item) 查找節(jié)點(diǎn)是否存在
單鏈表的實(shí)現(xiàn)
class SingleLinkList(object):
"""單鏈表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判斷鏈表是否為空"""
return self._head == None
def length(self):
"""鏈表長度"""
# cur初始時指向頭節(jié)點(diǎn)
cur = self._head
count = 0
# 尾節(jié)點(diǎn)指向None村砂，當(dāng)未到達(dá)尾部時
while cur != None:
count += 1
# 將cur后移一個節(jié)點(diǎn)
cur = cur.next
return count
def travel(self):
"""遍歷鏈表"""
cur = self._head
while cur != None:
print cur.item,
cur = cur.next
print ""
頭部添加元素
day24_鏈表-02.png
def add(self, item):
"""頭部添加元素"""
# 先創(chuàng)建一個保存item值的節(jié)點(diǎn)
node = SingleNode(item)
# 將新節(jié)點(diǎn)的鏈接域next指向頭節(jié)點(diǎn)烂斋，即_head指向的位置
node.next = self._head
# 將鏈表的頭_head指向新節(jié)點(diǎn)
self._head = node
尾部添加元素
def append(self, item):
"""尾部添加元素"""
node = SingleNode(item)
# 先判斷鏈表是否為空，若是空鏈表础废，則將_head指向新節(jié)點(diǎn)
if self.is_empty():
self._head = node
# 若不為空汛骂，則找到尾部，將尾節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
else:
cur = self._head
while cur.next != None:
cur = cur.next
cur.next = node
指定位置添加元素
day24_鏈表-03.png
def insert(self, pos, item):
"""指定位置添加元素"""
# 若指定位置pos為第一個元素之前评腺，則執(zhí)行頭部插入
if pos <= 0:
self.add(item)
# 若指定位置超過鏈表尾部帘瞭，則執(zhí)行尾部插入
elif pos > (self.length()-1):
self.append(item)
# 找到指定位置
else:
node = SingleNode(item)
count = 0
# pre用來指向指定位置pos的前一個位置pos-1，初始從頭節(jié)點(diǎn)開始移動到指定位置
pre = self._head
while count < (pos-1):
count += 1
pre = pre.next
# 先將新節(jié)點(diǎn)node的next指向插入位置的節(jié)點(diǎn)
node.next = pre.next
# 將插入位置的前一個節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
pre.next = node
刪除節(jié)點(diǎn)
day24_鏈表-04.png
def remove(self,item):
"""刪除節(jié)點(diǎn)"""
cur = self._head
pre = None
while cur != None:
# 找到了指定元素
if cur.item == item:
# 如果第一個就是刪除的節(jié)點(diǎn)
if not pre:
# 將頭指針指向頭節(jié)點(diǎn)的后一個節(jié)點(diǎn)
self._head = cur.next
else:
# 將刪除位置前一個節(jié)點(diǎn)的next指向刪除位置的后一個節(jié)點(diǎn)
pre.next = cur.next
break
else:
# 繼續(xù)按鏈表后移節(jié)點(diǎn)
pre = cur
cur = cur.next
查找節(jié)點(diǎn)是否存在
def search(self,item):
"""鏈表查找節(jié)點(diǎn)是否存在蒿讥，并返回True或者False"""
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
測試
if __name__ == "__main__":
ll = SingleLinkList()
ll.add(1)
ll.add(2)
ll.append(3)
ll.insert(2, 4)
print "length:",ll.length()
ll.travel()
print ll.search(3)
print ll.search(5)
ll.remove(1)
print "length:",ll.length()
ll.travel()
鏈表與順序表的對比
鏈表失去了順序表隨機(jī)讀取的優(yōu)點(diǎn)蝶念，同時鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大芋绸，但對存儲空間的使用要相對靈活媒殉。
鏈表與順序表的各種操作復(fù)雜度如下所示：
| 操作 | 鏈表 | 順序表 |
|---|---|---|
| 訪問元素 | O(n) | O(1) |
| 在頭部插入/刪除 | O(1) | O(n) |
| 在尾部插入/刪除 | O(n) | O(1) |
| 在中間插入/刪除 | O(n) | O(n) |
注意雖然表面看起來復(fù)雜度都是 O(n)，但是鏈表和順序表在插入和刪除時進(jìn)行的是完全不同的操作摔敛。鏈表的主要耗時操作是遍歷查找廷蓉，刪除和插入操作本身的復(fù)雜度是O(1)。順序表查找很快马昙，主要耗時的操作是拷貝覆蓋桃犬。因?yàn)槌四繕?biāo)元素在尾部的特殊情況刹悴，順序表進(jìn)行插入和刪除時需要對操作點(diǎn)之后的所有元素進(jìn)行前后移位操作，只能通過拷貝和覆蓋的方法進(jìn)行攒暇。
