鏈表是編程中的一種常用數(shù)據(jù)結(jié)構(gòu)，具有很強(qiáng)的靈活性衡瓶。由于python中不存在有指針徘公，這里將使用python中的引用來實(shí)現(xiàn)鏈表。
實(shí)現(xiàn)節(jié)點(diǎn)類
節(jié)點(diǎn)類最基本的功能包括：更新數(shù)據(jù)哮针，查詢數(shù)據(jù)关面，更新后繼節(jié)點(diǎn)和查詢后繼節(jié)點(diǎn)。
#節(jié)點(diǎn)類
class Node(object):
#初始化十厢，需要傳入節(jié)點(diǎn)的數(shù)據(jù)
def __init__(self, data):
self.data = data
self.next = None
#返回節(jié)點(diǎn)的數(shù)據(jù)
def get_data(self):
return self.data
#更新節(jié)點(diǎn)的數(shù)據(jù)
def set_data(self, new_data):
self.data = new_data
#返回后繼節(jié)點(diǎn)
def get_next(self):
return self.next
#變更后繼節(jié)點(diǎn)
def set_next(self, new_next):
self.next = new_next
實(shí)現(xiàn)鏈表
鏈表的主要功能包括：節(jié)點(diǎn)的增加等太、刪除和查詢，返回鏈表的長(zhǎng)度蛮放，返回鏈表是否為空等缩抡。
#鏈表類
class Linked_list(object):
#初始化，頭結(jié)點(diǎn)為空
def __init__(self):
self.head = None
#添加節(jié)點(diǎn)包颁，添加的新節(jié)點(diǎn)作為新的頭結(jié)點(diǎn)
def add(self, data):
new_node = Node(data)
new_node.set_next() = self.head
self.head = new_node
#包含查詢瞻想，傳入值，返回該值在鏈表中是否存在
def search(self, data):
checking = self.head #從頭結(jié)點(diǎn)開始查詢
while checking != None :
if checking.get_data() == data: #查找到娩嚼，返回True
return True
checking = checking.get_next() #查詢下一個(gè)節(jié)點(diǎn)
return False #遍歷到最后也未能找到蘑险，返回False
#刪除節(jié)點(diǎn)，將第一個(gè)具有傳入值的節(jié)點(diǎn)從鏈表中刪除
def remove(self, data):
checking = self.head #從頭結(jié)點(diǎn)開始查詢
previous = None #記錄前一個(gè)節(jié)點(diǎn)岳悟，頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為None
while checking != None :
if checking.get_data() == data: #查找到佃迄，跳出查找循環(huán)
break
previous = checking # 更新前一個(gè)節(jié)點(diǎn)
checking = checking.get_next() #查詢下一個(gè)節(jié)點(diǎn)
if previous == None：#如果頭結(jié)點(diǎn)便是查找的節(jié)點(diǎn)
self.head = checking.get_next()
else: # 查找的節(jié)點(diǎn)不在頭結(jié)點(diǎn)，即贵少，存在前驅(qū)節(jié)點(diǎn)
previous.set_next(checking.get_next())
#判斷鏈表是否為空
def isEmpty(self):
return self.head == None
#返回鏈表長(zhǎng)度
def size(self):
count = 0
counting = self.head #從頭結(jié)點(diǎn)開始計(jì)數(shù)
while counting != None :
count += 1
counting = counting.get_next()
return count
實(shí)現(xiàn)有序鏈表
有序鏈表是非常常用的鏈表和屎。有序鏈表在實(shí)現(xiàn)中與普通鏈表的差別體現(xiàn)在插入節(jié)點(diǎn)和查詢節(jié)點(diǎn)的操作上。
下面是一個(gè)頭結(jié)點(diǎn)小春瞬，尾節(jié)點(diǎn)大的有序鏈表：
#有序鏈表類
class Ordered_linked_list(object):
#初始化，頭結(jié)點(diǎn)為空
def __init__(self):
self.head = None
#添加節(jié)點(diǎn)
def add(self, data):
checking = self.head #從頭結(jié)點(diǎn)開始查詢
previous = None #記錄前一個(gè)節(jié)點(diǎn)套啤，頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為None
while checking != None :
if checking.get_data() > data: #查找到可以插入的位置宽气，跳出循環(huán)
break
previous = checking # 更新前一個(gè)節(jié)點(diǎn)
checking = checking.get_next() #查詢下一個(gè)節(jié)點(diǎn)
new_node = Node(data) #創(chuàng)建新節(jié)點(diǎn)
if previous == None: #插入在頭結(jié)點(diǎn)位置
new_node.set_next() = self.head
self.head = new_node
else ： #插入在中間或者尾部
previous.set_next(new_node)
new_node.set_next(checking)
#包含查詢随常，傳入值，返回該值在鏈表中是否存在
def search(self, data):
checking = self.head #從頭結(jié)點(diǎn)開始查詢
while checking != None :
if checking.get_data() == data: #查找到萄涯，返回True
return True
elif checking.get_data() > data: #過了需要查詢的值
return False
checking = checking.get_next() #查詢下一個(gè)節(jié)點(diǎn)
return False #遍歷到最后也未能找到绪氛，返回False
#刪除節(jié)點(diǎn)，將第一個(gè)具有傳入值的節(jié)點(diǎn)從鏈表中刪除
def remove(self, data):
checking = self.head #從頭結(jié)點(diǎn)開始查詢
previous = None #記錄前一個(gè)節(jié)點(diǎn)涝影，頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為None
while checking != None :
if checking.get_data() == data: #查找到枣察，跳出查找循環(huán)
break
previous = checking # 更新前一個(gè)節(jié)點(diǎn)
checking = checking.get_next() #查詢下一個(gè)節(jié)點(diǎn)
if previous == None：#如果頭結(jié)點(diǎn)便是查找的節(jié)點(diǎn)
self.head = checking.get_next()
else: # 查找的節(jié)點(diǎn)不在頭結(jié)點(diǎn)，即燃逻，存在前驅(qū)節(jié)點(diǎn)
previous.set_next(checking.get_next())
#判斷鏈表是否為空
def isEmpty(self):
return self.head == None
#返回鏈表長(zhǎng)度
def size(self):
count = 0
counting = self.head #從頭結(jié)點(diǎn)開始計(jì)數(shù)
while counting != None :
count += 1
counting = counting.get_next()
return count
