Python教程

Python实现链表

本文主要是介绍Python实现链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

链表

链表是计算机的一种数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

如上图,一个简单的单向链表。可见节点由数据和指针构成。

 

在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()
这篇关于Python实现链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!