Python实现单向链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python实现单向链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9610字，纯文字阅读大概需要14分钟。

内容图文

一、释义：

1.单向链表由节点组成；

2.每个节点包含两个域，元素域和链接域。元素域存放数据，链接域存放下一个节点的地址信息；

3.每个节点指向下一个节点，最后一个节点指向空。

二、特点：

1.链表方向是单向的，对链表的访问(如查询)，需要从头节点开始逐个往下寻找；

2.增跟删效率较高，不用移动其它节点，这里可比较于顺序表。

三、图解：

1.单向链表(single_linked)：

 2.节点(Node)：

 3.加深理解：

 四、定义链表的一些属性及方法：

1.empty()  # 判断链表为空

2.append()  # 尾部添加元素

3.add()  # 头部添加元素

4.insert()  # 指定位置添加元素

5.remove()  # 删除节点

6.search()  # 查找节点是否存在

7.travel()  # 遍历链表

8.length()  # 返回链表长度

 五、python实现链表：

1.定义节点：

class Node(object):
    """定义节点"""
    def __init__(self, elem):
        self.elem = elem  # 初始化元素区
        self.next = None  # 初始化链接区，默认指向空

2.定义链表：

1 class SingleLinked(object):
2     """定义单向链表"""
3 
4     # 初始化链表
5     def __init__(self, node=None):
6         self.__head = node  # 默认头节点为空

3.判断空：

1 # 判断链表为空
2     def empty(self):
3         # 头节点为空则链表为空
4         return self.__head is None

4.尾部添加元素：

 1 # 尾部添加元素
 2     def append(self, item):
 3         node = Node(item)
 4         # 如果链表为空，则添加节点为头节点
 5         if self.empty():
 6             self.__head = node
 7         else:
 8             cur = self.__head  # 定义游标
 9             # 如果游标的下一个节点不为空，则游标往下走
10             while cur.next is not None:
11                 cur = cur.next
12             cur.next = node

5.头部添加元素：

1 # 头部添加元素
2     def add(self, item):
3         node = Node(item)
4         if self.empty():
5             self.__head = node
6         else:
7             # 注意这两句的顺序不能换
8             node.next = self.__head
9             self.__head = node

6.指定位置添加元素：

 1 # 指定位置添加元素
 2     def insert(self, pos, item):
 3 
 4         # 如果pos <= 0,则视为头节点位置插入
 5         if pos <= 0:
 6             self.add(item)
 7             return True
 8         # 如果pos>=链表的长度，则视为尾添加
 9         elif pos >= self.length():
10             self.append(item)
11             return True
12         # 其余则为链表区域内位置插入
13         else:
14             node = Node(item)  # 实例化一个节点
15             cur = self.__head  # 定义游标
16             location = 0  # 定义链表位置并初始化
17             # 如果没有找到指定的位置，游标继续往下走
18             while pos != location + 1:
19                 cur = cur.next
20                 location += 1
21             # 退出循环则找到相应位置，添加节点
22             node.next = cur.next
23             cur.next = node
24             return True

7.删除节点：

 1 # 删除节点
 2     def remove(self, item):
 3         if self.empty():
 4             return False
 5         cur = self.__head  # 定义cur游标
 6         pre = None  # 定义pre游标，为cur的前一个位置
 7         while cur is not None:
 8             if cur.elem == item:
 9                 # 头节点情况
10                 if cur == self.__head:
11                     # 将头节点的下一个节点赋给头节点
12                     self.__head = cur.next
13                     return True
14                 # 非头节点情况
15                 else:
16                     # 删除操作
17                     pre.next = cur.next
18                     return True
19             # 移动游标
20             else:
21                 # 这两句顺序不能反
22                 pre = cur
23                 cur = cur.next
24         return False

8.查找节点是否存在：

 1  # 查找节点是否存在
 2     def search(self, item):
 3         if self.empty():
 4             return False
 5         else:
 6             cur = self.__head  # 定义游标
 7             while cur is not None:
 8                 if cur.elem == item:
 9                     return True
10                 else:
11                     cur = cur.next  # 游标后移
12             return False

9.遍历链表：

 1 # 遍历链表
 2     def travel(self):
 3         if self.empty():
 4             return None
 5         else:
 6             elem_list = []  # 元素列表
 7             cur = self.__head
 8             # 如果游标不为空，则打印游标对应的元素，游标向后移动
 9             while cur is not None:
10                 elem_list.append(cur.elem)
11                 cur = cur.next  # 游标下移
12             return elem_list

10.返回链表长度：

 1  # 返回链表长度
 2     def length(self):
 3         if self.empty():
 4             return 0
 5         else:
 6             cur = self.__head
 7             count = 0
 8             while cur is not None:
 9                 count += 1
10                 cur = cur.next
11             return count

六、整体代码：

  1 class Node(object):
  2     """定义节点"""
  3     def __init__(self, elem):
  4         self.elem = elem  # 初始化元素区
  5         self.next = None  # 初始化链接区，默认指向空
  6 
  7 
  8 class SingleLinked(object):
  9     """定义单向链表"""
 10 
 11     # 初始化链表
 12     def __init__(self, node=None):
 13         self.__head = node  # 默认头节点为空
 14 
 15     # 判断链表为空
 16     def empty(self):
 17         # 头节点为空则链表为空
 18         return self.__head is None
 19 
 20     # 尾部添加元素
 21     def append(self, item):
 22         node = Node(item)
 23         # 如果链表为空，则添加节点为头节点
 24         if self.empty():
 25             self.__head = node
 26         else:
 27             cur = self.__head  # 定义游标
 28             # 如果游标的下一个节点不为空，则游标往下走
 29             while cur.next is not None:
 30                 cur = cur.next
 31             cur.next = node
 32 
 33     # 头部添加元素
 34     def add(self, item):
 35         node = Node(item)
 36         if self.empty():
 37             self.__head = node
 38         else:
 39             # 注意这两句的顺序不能换
 40             node.next = self.__head
 41             self.__head = node
 42 
 43     # 指定位置添加元素
 44     def insert(self, pos, item):
 45 
 46         # 如果pos <= 0,则视为头节点位置插入
 47         if pos <= 0:
 48             self.add(item)
 49             return True
 50         # 如果pos>=链表的长度，则视为尾添加
 51         elif pos >= self.length():
 52             self.append(item)
 53             return True
 54         # 其余则为链表区域内位置插入
 55         else:
 56             node = Node(item)  # 实例化一个节点
 57             cur = self.__head  # 定义游标
 58             location = 0  # 定义链表位置并初始化
 59             # 如果没有找到指定的位置，游标继续往下走
 60             while pos != location + 1:
 61                 cur = cur.next
 62                 location += 1
 63             # 退出循环则找到相应位置，添加节点
 64             node.next = cur.next
 65             cur.next = node
 66             return True
 67 
 68     # 删除节点
 69     def remove(self, item):
 70         if self.empty():
 71             return False
 72         cur = self.__head  # 定义cur游标
 73         pre = None  # 定义pre游标，为cur的前一个位置
 74         while cur is not None:
 75             if cur.elem == item:
 76                 # 头节点情况
 77                 if cur == self.__head:
 78                     # 将头节点的下一个节点赋给头节点
 79                     self.__head = cur.next
 80                     return True
 81                 # 非头节点情况
 82                 else:
 83                     # 删除操作
 84                     pre.next = cur.next
 85                     return True
 86             # 移动游标
 87             else:
 88                 # 这两句顺序不能反
 89                 pre = cur
 90                 cur = cur.next
 91         return False
 92 
 93     # 查找节点是否存在
 94     def search(self, item):
 95         if self.empty():
 96             return False
 97         else:
 98             cur = self.__head  # 定义游标
 99             while cur is not None:
100                 if cur.elem == item:
101                     return True
102                 else:
103                     cur = cur.next  # 游标后移
104             return False
105 
106     # 遍历链表
107     def travel(self):
108         if self.empty():
109             return None
110         else:
111             elem_list = []  # 元素列表
112             cur = self.__head
113             # 如果游标不为空，则打印游标对应的元素，游标向后移动
114             while cur is not None:
115                 elem_list.append(cur.elem)
116                 cur = cur.next  # 游标下移
117             return elem_list
118 
119     # 返回链表长度
120     def length(self):
121         if self.empty():
122             return 0
123         else:
124             cur = self.__head
125             count = 0
126             while cur is not None:
127                 count += 1
128                 cur = cur.next
129             return count
130 
131 
132 if __name__ == '__main__':
133     single_linked = SingleLinked()
134     print('-----尾部添加元素-----')
135     single_linked.append(1)
136     single_linked.append(2)
137     single_linked.append(78)
138     print('-----遍历链表-----')
139     ret = single_linked.travel()
140     print(ret)
141     print('-----查看链表长度-----')
142     res = single_linked.length()
143     print(res)
144     print('-----头部添加元素-----')
145     single_linked.add(9)
146     single_linked.add(10)
147     print(res)
148     print('-----遍历链表-----')
149     ret = single_linked.travel()
150     print(ret)
151     print('-----查找节点是否存在-----')
152     ret = single_linked.search(1)
153     print(ret)
154     print('-----遍历链表-----')
155     print(single_linked.travel())
156     print('-----删除节点-----')
157     res2 = single_linked.remove(10)
158     res3 = single_linked.remove(56)
159     res4 = single_linked.remove(79)
160     print(ret, res, res4)
161     print('-----遍历链表-----')
162     print(single_linked.travel())
163  

内容总结

以上是互联网集市为您收集整理的Python实现单向链表全部内容，希望文章能够帮你解决Python实现单向链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端