python实现链表
2021-06-16 09:04
标签：内存 lin 定义函数 ever 定义 数组 ret src += 链表不需要在内存存储一个连续的地方，通常就像一个链一样 它的每个节点包含本身和下一个元素的地址，以此来把两个元素进行关联，这就是一个链表 链表分单项和双向，一般单项就够用了。 链表是一个存储的数据结构，C语言中存数据用的是数组，存储所有的元素都是在内存中，每一个元素在内存中相连的位置，如果想删除一个元素，那么后边所有的元素都要向前移动一个位置，这样就提高了时间复杂度，如果是链表里的元素，如果删了一个数，那么把前一个的元素指向被删除元素的后一个元素就可以了，时间复杂度是O(1)，数组里面的时间复杂度是O(n),效率不一样，所以这是链表存在的意义，比数组操作的效率高。 用于C语言中代替数组存储数据，效率会高一些 但是在python中直接用list就可以 链表里是用指针指向下一个元素的地址，但是python里没有指针，那就 用变量存一下下一个元素的地址,代替指针 链表可以用类的实例表示，实例有value和next属性，next指向下一个实例 定义节点 class p():pass 实例化一个实例，用a来执行它 a=P() a指向P类的一个实例的地址 self.next=P()，指向下一个元素 最后一个元素的下一个指针域指向None 数据域 指针域（下一个节点的地址） 最后一个元素的指针域是None就结束了 代码： #encoding=utf-8 class Node: def __init__(self,value=None,next=None):#next(指针域) self.value=value self.next=next n1=Node(1) n2=Node(2) n3=Node(3) n1.next=n2 n2.next=n3 print "n1.value:",n1.value print "n2.value:",n2.value print "n2.value:",n3.value print "######################" print "n1.next.value:",n1.next.value print "n2.next.value:",n2.next.value print "n3.next:",n3.next 结果： def printLinkedList(node): while True: if node.next != None: print node.value else: print node.value break node = node.next#从当前节点跳到下一个节点 printLinkedList(n1) 原理：判断最后一个元素的值是不是None 结果： 或者： 代码： def printLinkedValue(node): while node is not None: print node.value node = node.next return "" print printLinkedValue(n1) 结果： D:\>python test.py 1 2 3 代码： def printLinkedList(node): #递归 #自己调用自己，并且有结束的条件，这是递归的原则 if node.next is None: print node.value return print node.value printLinkedList(node.next) #return "" printLinkedList(n1) 结果： D:\>python test.py 1 2 3 拆解： n1:1 def printReversedLinkedList(node):
if node.next is None:
print (node.value)
return
printReversedLinkedList(node.next)
print (node.value)
return None printReversedLinkedList(n1) 结果： n1-->n2--n3(打印3，返回)---打印一个2---》1 递归的时候是往回捣~~ 相当于每次执行递归时，记个账本，最后一点点往前算账~~ 练习代码： class LinkedList(object):
def __init__(self,head=None):
self.head = head
#重写__len__函数计算链表长度
def __len__(self):
count = 0
if self.head == None: print "b"*10 return count
print "c"*10
node =self.head
print "d"*10
while node: print "e"*10 count +=1 node = node.next print "f"*10
return count a=LinkedList(n1) print len(a) 结果： D:\>python test.py cccccccccc dddddddddd eeeeeeeeee ffffffffff eeeeeeeeee ffffffffff eeeeeeeeee ffffffffff 3 练习代码：
def append(self,node):
if self.head == None: self.head = node return node
cur_node = self.head
while cur_node.next != None: print cur_node.value cur_node = cur_node.next
cur_node.next=node
return cur_node.value
结果： D:\>python test.py 1 2 3 4 4 练习代码：
def find(self,value):
if self.head == None: return
cur_node = self.head
while cur_node: if cur_node.value == value: print cur_node.value return cur_node else: cur_node = cur_node.next
a=LinkedList(n1) print a.find(3) 结果： D:\>python test.py 3 <__main__.node object at>
练习代码：
def insertFront(self,data):
if self.head == None: self.head = Node(data) return self.head
else: tmp = self.head self.head=Node(data) self.head.next = tmp
return self.head
a=LinkedList(n1) print a.insertFront(5) print a.insertFront(5).value 结果： D:\>python test.py <__main__.node object at> 5 练习代码：
def delete(self,value):
if self.head==None: return None
elif self.head.value == value: self.head = self.head.next
else: fro_node = None cur_node = self.head while cur_node: if cur_node.value != value:
fro_node=cur_node cur_node = cur_node.next else: fro_node.next =
cur_node.next return cur_node.value
return None a=LinkedList(n1) print a.delete(3) 结果： D:\>python test.py 3 练习代码：
def get_all(self):
list=[]
if self.head == None: return None
else: cur_node = self.head while cur_node: list.append(cur_node.value) cur_node = cur_node.next return list
a=LinkedList(n1) print a.get_all() 结果： D:\>python test.py [1, 2, 3] #encoding=utf-8 class Node(object):
def __init__(self,value=None,next=None):
self.value=value
self.next=next
n1=Node(1) n2=Node(2) n3=Node(3) n1.next=n2 n2.next=n3 class LinkedList(object):
def __init__(self,head=None):
self.head = head
def __len__(self):
count = 0
if self.head == None: return count
node =self.head
while node: count +=1 node = node.next
return count
def append(self,node):
if self.head == None: self.head = node return node cur_node = self.head
while cur_node.next != None: print cur_node.value cur_node = cur_node.next
cur_node.next=node
return cur_node.value
def find(self,value):
if self.head == None: return
cur_node = self.head
while cur_node: if cur_node.value == value: print cur_node.value return cur_node else: cur_node = cur_node.next
def insertFront(self,data):
if self.head == None: self.head = Node(data) return self.head
else: tmp = self.head self.head=Node(data) self.head.next = tmp
return self.head
def delete(self,value):
if self.head==None: return None
elif self.head.value == value: self.head = self.head.next
else: fro_node = None cur_node = self.head while cur_node: if cur_node.value != value: fro_node=cur_node cur_node = cur_node.next else: fro_node.next =
cur_node.next return cur_node.value
return None
def get_all(self):
list=[]
if self.head == None: return None
else: cur_node = self.head while cur_node: list.append(cur_node.value) cur_node = cur_node.next return list
a=LinkedList(n1) print a.get_all() python实现链表 标签：内存 lin 定义函数 ever 定义 数组 ret src += 原文地址：https://www.cnblogs.com/xiaxiaoxu/p/9727017.html链表：
链表存在的用意义：
链表定义：
定义节点类：
定义函数 打印出所有节点的值：
使用while循环判断，节点.next是否为空，不空，就打印
递归方式正序输出：
printLinkedList(n2)
n2:2
printLinkedList(n3)
n3:3 递归方式逆序输出
递归逆序图解：
链表类：
在链表末尾加入一个节点：
查找一个节点：
插入一个节点：
删除列表中的某个值对应的节点：
获取有所节点的值：
所有练习代码: