链表
链表是计算机的一种数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
如上图,一个简单的单向链表。可见节点由数据和指针构成。
在python中没有指针,我们要用引用来代替指针,下文用指针来说,但是在这不是指针,是引用。
1 class node(): 2 def __init__(self,data=0,next=None): 3 self.data=data 4 self.next=next
如上图,创建了节点
之后我们要让节点连起来,组成链表
1 class linklist(): 2 def __init__(self): 3 self.head=None 4 self.len=0
在链表中,头结点很重要,一般会从头结点开始遍历链表
我参考了一些其他的博客,总结得出,我们对链表主要有以下的操作:
1.在链表尾添加节点
2.在链表中插入节点
3.在链表中删除节点
4.在链表中搜索节点
5.在链表中修改节点
6.遍历输出链表数据
1.在链表尾添加节点(和数组中append()函数作用相同)
思路:找到尾节点,让尾结点next的指针为新节点
如果链表为空,直接添加新节点
1 def append_node(self,data): 2 newnode=node(data,None) 3 temp=self.head 4 if self.head==None: 5 self.head=newnode 6 else : 7 while temp.next!=None: 8 temp=temp.next 9 temp.next=newnode 10 self.len+=1
2.在链表中插入节点
思路:新节点指向插入位置的节点,插入位置前一个节点指向新节点。如果插入到首位,只用执行前半句
1 def insert(self,number,newdata): 2 temp = self.head 3 j = 0 4 newnode=node(newdata) 5 if self.len < number: 6 print("error") 7 else: 8 while j < number-1: 9 temp = temp.next 10 j += 1 11 newnode.next=temp.next 12 temp.next=newnode 13 self.len+=1
3.在链表中删除节点
思路:让删除节点前节点指向删除节点指向的节点,清除删除节点所占用的内存。(在python中不会内存管理,第二句就不执行了)
1 def del_node(self,number):#首项为0 2 temp=self.head 3 j=0 4 if self.len<number: 5 print("error") 6 else: 7 while j<number-1: 8 temp = temp.next 9 j+=1 10 temp.next=temp.next.next 11 self.len-=1
4.在链表中搜索节点
思路:从头结点开始遍历链表。
1 def search_node(self,data): 2 temp = self.head 3 j = 0 4 while temp.next!=None: 5 temp = temp.next 6 j += 1 7 if temp.data==data: 8 break 9 return j
5.在链表中修改节点
思路:从头结点开始遍历链表,找到目标节点后修改其数据。
1 def change_data(self,number,newdata): 2 temp = self.head 3 j = 0 4 if self.len < number: 5 print("error") 6 else: 7 while j < number: 8 temp = temp.next 9 j += 1 10 temp.data=newdata
6.遍历输出链表数据
思路:从头结点开始遍历链表并输出数据。
1 def print_list(self): 2 temp=self.head 3 while temp.next!=None: 4 print(temp.data,"-> ",end="") 5 temp=temp.next 6 print(temp.data)
完整代码:
1 class node(): 2 def __init__(self,data=0,next=None): 3 self.data=data 4 self.next=next 5 6 class linklist(): 7 def __init__(self): 8 self.head=None 9 self.len=0 10 11 def append_node(self,data): 12 newnode=node(data,None) 13 temp=self.head 14 if self.head==None: 15 self.head=newnode 16 else : 17 while temp.next!=None: 18 temp=temp.next 19 temp.next=newnode 20 self.len+=1 21 22 def print_list(self): 23 temp=self.head 24 while temp.next!=None: 25 print(temp.data,"-> ",end="") 26 temp=temp.next 27 print(temp.data) 28 29 def del_node(self,number):#首项为0 30 temp=self.head 31 j=0 32 if self.len<number: 33 print("error") 34 else: 35 while j<number-1: 36 temp = temp.next 37 j+=1 38 temp.next=temp.next.next 39 self.len-=1 40 41 def search_node(self,data): 42 temp = self.head 43 j = 0 44 while temp.next!=None: 45 temp = temp.next 46 j += 1 47 if temp.data==data: 48 break 49 return j 50 51 def change_data(self,number,newdata): 52 temp = self.head 53 j = 0 54 if self.len < number: 55 print("error") 56 else: 57 while j < number: 58 temp = temp.next 59 j += 1 60 temp.data=newdata 61 62 def insert(self,number,newdata): 63 temp = self.head 64 j = 0 65 newnode=node(newdata) 66 if self.len < number: 67 print("error") 68 else: 69 while j < number-1: 70 temp = temp.next 71 j += 1 72 newnode.next=temp.next 73 temp.next=newnode 74 self.len+=1 75 76 a=linklist() 77 for i in range (0,10): 78 a.append_node(i) 79 print("append_node: ",end="") 80 a.print_list() 81 print("del_node(2): ",end="") 82 a.del_node(2) 83 a.print_list() 84 print("search_node(5): ",end="") 85 print(a.search_node(5)) 86 print("change_data(4,999): ",end="") 87 a.change_data(4,999) 88 a.print_list() 89 print("a.insert(4,19909)): ",end="") 90 a.insert(4,19909) 91 a.print_list()