本文和大家分享的主要是python中單向鏈表相關(guān)內(nèi)容，一起來(lái)看看吧，希望對(duì)大家學(xué)習(xí)python有所幫助。

　　單向鏈表

　　單向鏈表也叫單鏈表，是鏈表中最簡(jiǎn)單的一種形式，它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)信息域（元素域）和一個(gè)鏈接域。這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值。

?。?nbsp;表元素域elem用來(lái)存放具體的數(shù)據(jù)。

　?。?nbsp;鏈接域next用來(lái)存放下一個(gè)節(jié)點(diǎn)的位置（python中的標(biāo)識(shí)）

　　． 變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置，從p出發(fā)能找到表中的任意節(jié)點(diǎn)。

　　節(jié)點(diǎn)實(shí)現(xiàn)

　　class Node(object):

　　"""單鏈表的結(jié)點(diǎn)"""

　　def __init__(self,item):

　　# item存放數(shù)據(jù)元素

　　self.item = item

　　# next是下一個(gè)節(jié)點(diǎn)的標(biāo)識(shí)

　　self.next = None

　　單鏈表的操作

　?。?is_empty() 鏈表是否為空

　?。?length() 鏈表長(zhǎng)度

　　． travel() 遍歷整個(gè)鏈表

　?。?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):

　　"""鏈表長(zhǎng)度"""

　　# cur初始時(shí)指向頭節(jié)點(diǎn)

　　cur = self.__head

　　count = 0

　　# 尾節(jié)點(diǎn)指向None，當(dāng)未到達(dá)尾部時(shí)

　　while cur != None:

　　count += 1

　　# 將cur后移一個(gè)節(jié)點(diǎn)

　　cur = cur.next

　　return count

　　def travel(self):

　　"""遍歷鏈表"""

　　cur = self.__head

　　while cur != None:

　　print(cur.item,end = ' ')

　　cur = cur.next

　　print("")

　　頭部添加元素

　． 表元素域elem用來(lái)存放具體的數(shù)據(jù)。

　?。?nbsp;鏈接域next用來(lái)存放下一個(gè)節(jié)點(diǎn)的位置（python中的標(biāo)識(shí)）

　?。?nbsp;變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置，從p出發(fā)能找到表中的任意節(jié)點(diǎn)。

　　節(jié)點(diǎn)實(shí)現(xiàn)

　　class Node(object):

　　"""單鏈表的結(jié)點(diǎn)"""

　　def __init__(self,item):

　　# item存放數(shù)據(jù)元素

　　self.item = item

　　# next是下一個(gè)節(jié)點(diǎn)的標(biāo)識(shí)

　　self.next = None

　　單鏈表的操作

　?。?is_empty() 鏈表是否為空

　?。?length() 鏈表長(zhǎng)度

　　． travel() 遍歷整個(gè)鏈表

　?。?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):

　　"""鏈表長(zhǎng)度"""

　　# cur初始時(shí)指向頭節(jié)點(diǎn)

　　cur = self.__head

　　count = 0

　　# 尾節(jié)點(diǎn)指向None，當(dāng)未到達(dá)尾部時(shí)

　　while cur != None:

　　count += 1

　　# 將cur后移一個(gè)節(jié)點(diǎn)

　　cur = cur.next

　　return count

　　def travel(self):

　　"""遍歷鏈表"""

　　cur = self.__head

　　while cur != None:

　　print(cur.item,end = ' ')

　　cur = cur.next

　　print("")

　　頭部添加元素

　def insert(self, pos, item):

　　"""指定位置添加元素"""

　　# 若指定位置pos為第一個(gè)元素之前，則執(zhí)行頭部插入

　　if pos <= 0:

　　self.add(item)

　　# 若指定位置超過(guò)鏈表尾部，則執(zhí)行尾部插入

　　elif pos > (self.length()-1):

　　self.append(item)

　　# 找到指定位置

　　else:

　　node = Node(item)

　　count = 0

　　# pre用來(lái)指向指定位置pos的前一個(gè)位置pos-1，初始從頭節(jié)點(diǎn)開(kāi)始移動(dòng)到指定位置

　　pre = self.__head

　　while count < (pos-1):

　　count += 1

　　pre = pre.next

　　# 先將新節(jié)點(diǎn)node的next指向插入位置的節(jié)點(diǎn)

　　node.next = pre.next

　　# 將插入位置的前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)

　　pre.next = node

　　刪除節(jié)點(diǎn)

　def remove(self,item):

　　"""刪除節(jié)點(diǎn)"""

　　cur = self.__head

　　pre = None

　　while cur != None:

　　# 找到了指定元素

　　if cur.item == item:

　　# 如果第一個(gè)就是刪除的節(jié)點(diǎn)

　　if not pre:

　　# 將頭指針指向頭節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)

　　self.__head = cur.next

　　else:

　　# 將刪除位置前一個(gè)節(jié)點(diǎn)的next指向刪除位置的后一個(gè)節(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

 

 

來(lái)源：博客園