單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節(jié)點包含兩個域，一個信息域，用來存儲數據，一個是鏈接域，這個鏈接指向鏈表中的下一個節(jié)點，而最后一個節(jié)點的鏈接域則指向一個空值。
image.png
- 表元素elem 用來存放數據
- 鏈接域next用來存放下一個節(jié)點的位置（python 中的標識）
- 變量p指向鏈表的頭節(jié)點的位置，從p出發(fā)能到鏈表的任意節(jié)點。
節(jié)點實現：
class Node(object):
def __init__(self,elem):
self.elem = elem
self.next = None
單鏈表的操作：
- is_empty()鏈表是否為空
- length() 鏈表長度
- trave() 遍歷整個鏈表
- add(item) 在鏈表頭部添加元素
- append(item) 在鏈表尾部添加元素
- insert(pos, item) 在鏈表pos位置添加元素
- remove(item) 刪除元素
- search(item) 查找元素
單鏈表的實現
class SingleLinkList(object):
def __init__():
self.__head = None
def is_empty(self):
return self.__head == None
def length(self):
cur = self.__head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel():
cur = self.__head
while cur != None:
print(cur.elem,end = " ")
cur = cur.next
頭部添加元素
image.png
def add(item):
node = Node(item):
node.next = self.__head
self.__head = node
尾部添加元素
def append(item)
node = Node(item)
cur = self.__head
if self.is__empty():
self.__head = node
else:
while cur != None:
cur = cur.next
cur.next = node
指定位置添加元素
image.png
def insert(self, pos, item):
if pos <= 0:
self.add(item)
elif pos >= self.length():
self.append(item)
else:
node = Node(item)
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
node.next = pre.next
pre.next = node
刪除節(jié)點
image.png
def remove(item):
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
#當刪除之后要結束當前循環(huán)
break
else:
pre = cur
cur = cur.next
def search(item):
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
鏈表與順序表的對比
- 鏈表失去了順序表隨機讀取的優(yōu)點
- 鏈表增加了節(jié)點的指針域，空間開銷比較大
- 鏈表對存儲空間的使用要相對靈活
- 鏈表的主要耗時工作是遍歷，刪除和插入操作本身的復雜度是O(1)
- 順序表查找很快，主要耗時操作是拷貝覆蓋，除了目標元素在尾部的特殊情況，順序表在進行插入和刪除時需要對操作點之后的所有元素進行前后以為操作。
鏈表與順序表的各種操作復雜度對比：
image.png
