pythonselfnext_Python数据结构——链表（一）单链表

之前学C时学到可以通过指针指向某一节点实现空间上不连贯的单位逻辑上连贯&＃xff0c;也就是所谓的链表&＃xff0c;Python中不存在指针的概念&＃xff0c;可以通过定义类来实现类似链表的效果。

写下来做个总结

定义节点

class node(object):

def __init__(self,item):

self.item &＃61; item

self.next &＃61; None

item代表存储的内容&＃xff0c;next用来模拟指针。

创建单链表类

length&＃xff1a;链表长度

head&＃xff1a;链表头节点

count&＃xff1a;现有节点数

class singlechainlist(object):

def __init__(self,length:int):

self.length &＃61; length

self.head &＃61; node(None)

self.count &＃61; 0

def __num_node(self,x:int):

self.count &＃43;&＃61; x

def search(self,x:node): # search for the node and return the precvious node

if self.head.next &＃61;&＃61; x:

return self.head

else:

temp &＃61; self.head.next

while temp.next !&＃61; x:

temp &＃61; temp.next

return temp

def add_node(self,node:node): # add at the end of chain

if self.count &＃61;&＃61; self.length:

print(&＃39;cannot exceed max length&＃39;)

else:

self.find_tail().next &＃61; node

self.__num_node(1)

def find_tail(self,x&＃61;None): # find the last node

if x is None:

x &＃61; self.head

if x.next is None:

return x

else:

temp &＃61; x.next

if temp.next is None:

return temp

else:

return self.find_tail(temp)

def del_node(self,x&＃61;None):

if self.head.next is None:

print(&＃39;no node any more!&＃39;)

else:

if x is None:

self.search(self.find_tail()).next&＃61;None

self.__num_node(-1)

else:

self.search(x).next &＃61; x.next

x &＃61; None

self.__num_node(-1)

def insert_node(self,x:node,y:node):

if self.count &＃61;&＃61; self.length:

print(&＃39;cannot exceed max length&＃39;)

else:

if self.head.next is None:

self.head.next &＃61; y

self.__num_node(1)

else:

self.search(x).next &＃61; y

y.next &＃61; x

self.__num_node(1)

def get_chain(self):

chain &＃61; [self.head]

while chain[-1].next !&＃61; None:

chain.append(chain[-1].next)

return chain

现在实现的功能&＃xff1a;

在末尾加节点

在链表中插入节点

查找节点

删除节点

获取完整链表