本文實例講述了Python數(shù)據(jù)結(jié)構(gòu)與算法之鏈表定義與用法。分享給大家供大家參考，具體如下：

本文將為大家講解：

(1)從鏈表節(jié)點的定義開始，以類的方式，面向?qū)ο蟮乃枷脒M行鏈表的設(shè)計

(2)鏈表類插入和刪除等成員函數(shù)實現(xiàn)時需要考慮的邊界條件，

prepend(頭部插入)、pop(頭部刪除)、append(尾部插入)、pop_last(尾部刪除)

2.1 插入：

空鏈表

鏈表長度為1

插入到末尾

2.2 刪除

空鏈表

鏈表長度為1

刪除末尾元素

(3)從單鏈表到單鏈表的一眾變體：

帶尾節(jié)點的單鏈表

循環(huán)單鏈表

雙鏈表

1. 鏈表節(jié)點的定義

class LNode:

def __init__(self, elem, next_=None):

self.elem = elem

self.next = next_

2. 單鏈表的實現(xiàn)

重點理解插入、刪除的實現(xiàn)及其需要考慮的邊界條件：

class LinkedListUnderflow(ValueError):

pass

class LList:

def __init__(self):

self._head = None

def is_empty(self):

return self._head is None

def prepend(self, elem):

self._head = LNode(elem, self._head)

def pop(self):

if self._head is None:

raise LinkedListUnderflow('in pop')

e = self._head.elem

self._head = self._head.next

return e

def append(self, elem):

if self._head is None:

self._head = LNode(elem)

return

p = self._head

while p.next is not None:

p = p.next

p.next = LNode(elem)

def pop_last(self):

if self._head is None:

raise LinkedListUnderflow('in pop_last')

p = self._head

if p.next is None:

e = p.elem

self._head = None

return e

while p.next.next is not None:

p = p.next

e = p.next.elem

p.next = None

return e

簡單總結(jié)：

(0)能夠訪問 p.next.next 的前提是 p.next 不為空；

(1)尾部插入，如果鏈表不為空，需且僅需改變的是尾部節(jié)點的指針；

(2)尾部刪除，如果鏈表長度不為空，需且僅需改變的是倒數(shù)第二個節(jié)點的指針。

單鏈表的簡單變形：具有尾部節(jié)點的單鏈表

class LList1(LList):

def __init__(self):

LList.__init__(self)

self._rear = None

...

我們僅需重寫的是：頭部的插入、尾部的插入、尾部的刪除

def prepend(self, elem):

if self._head is None:

self._head = LNode(elem)

self._rear = self._head

else:

self._head = LNode(elem, self._head)

def append(self, elem):

if self._head is None:

self._head = LNode(elem)

self._rear = self._head

else:

self._rear.next = LNode(elem)

self._rear = self._rear.next

def pop_last(self):

if self._head is None:

raise LinkedListUnderflow('in pop_last')

p = self._head

if p.next is None:

e = p.elem

self._head = None

return e

while p.next.next is not None:

p = p.next

e = p.next.elem

self._rear = p

p.next = None

return e

單鏈表的變體：循環(huán)單鏈表

class LCList:

def __init__(self):

self._rear = None

def prepend(self, elem):

if self._rear is None:

self._rear = LNode(elem)

self._rear.next = self._rear

else:

self._rear.next = LNode(elem, self._rear.next)

def append(self, elem):

self.prepend(elem)

self_rear = self._rear.next

def pop(self):

if self._rear is None:

raise LinkedListUnderflow('in pop')

p = self._rear.next

if p is None:

self._rear = None

else:

self._rear.next = p.next

return p.elem

def printall(self):

if self._rear is None:

raise ...

p = self._rear.next

while True:

print(p.elem)

if p is self._rear:

break

p = p.next

希望本文所述對大家Python程序設(shè)計有所幫助。

總結(jié)

以上是生活随笔為你收集整理的python定义链表节点_Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。