python单向链表实例详解

使用python实现单向链表，供大家参考，具体内容如下

单向链表：是将所有的数据作为一个个节点，将所有的节点链接在一起。每一个节点中又分为： 存储数据区，链接区

存储数据区： 存储具体的数据

链接区： 指向下一个节点

分析实现：

1、 分析：根据链表的特性，首先要存放有数据的容器，还要有存放节点的容器
2、 节点类中：要有数据区和next区
3、 链表类中：存放所有节点

单链表操作

1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在

代码实现

# Functions ?函数声明
class Node():
? ? """
? ? 存放节点类
? ? 每次调用该类，实例化一个节点
? ? 默认每个节点中有数据区，next区。
? ? 数据区为该数据，next区为空
? ? """
? ? def __init__(self, item,next=None):
? ? ? ? self.item = item
? ? ? ? self.next = next
? ? ? ? pass

class Linklist():
? ? """
? ? 存放数据类
? ? 将所有的节点存放起来的容器
? ? 首先，默认链表为空，在这里需要有一个头节点，默认头节点为空

? ? """
? ? def __init__(self, head=None):
? ? ? ? self.head = head

? ? def is_empty(self):
? ? ? ? return self.head == None

? ? def append(self, item):
? ? ? ? """
? ? ? ? 往链表尾部添加数据
? ? ? ? 1、实例化游标：使用游标指向每一个数据，检索数据和判断数据next是否为空
? ? ? ? 2、移动游标，从头节点开始，每次使用self.next移动，以为next指向的就是下一个数据
? ? ? ? 3、添加数据，首先判断链表是否为空，为空的情况下，直接将头节点等于node数据
? ? ? ? 4、如果不为空，需要从头节点开始，移动游标，判断游标指向的next是否为空
? ? ? ? 5、使用循环不停的移动节点，当遇到节点中的next为空的情况下停止移动
? ? ? ? 6、循环条件： 当 条件 != None, 进入循环获取，当cur为空时就不会进入循环，所以在这里要使用 cur != None
? ? ? ? """
? ? ? ? # 首先要实例化一个节点
? ? ? ? node = Node(item)
? ? ? ? # 如果链表为空
? ? ? ? if self.is_empty():
? ? ? ? ? ? # 直接将头节点的next添加node
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? # 实例化一个游标
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? while cur.next != None:
? ? ? ? ? ? ? ? # 移动游标，得到最后一个游标的数据
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # 将移动后的数据的下一个next添加上 node
? ? ? ? ? ? cur.next=node
? ? ? ? ? ? pass

? ? def travel(self):
? ? ? ? """遍历数据"""
? ? ? ? # 实例化一个游标
? ? ? ? cur = self.head
? ? ? ? # 数据链为空的情况
? ? ? ? if self.is_empty():
? ? ? ? ? ? print('')
? ? ? ? else:
? ? ? ? ? ? # 获取每个数据区中的数据
? ? ? ? ? ? # 移动游标，每移动一次，输出一次数据区内的数据
? ? ? ? ? ? while cur != None:
? ? ? ? ? ? ? ? print(cur.item, end=' ')
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? print()

? ? def length(self):
? ? ? ? """返回链表的长度"""
? ? ? ? # 实例化游标
? ? ? ? cur = self.head
? ? ? ? # 计数，这里对空链表进行判断，如果是链表，则不会进入循环，直接输出 0
? ? ? ? count = 0
? ? ? ? # 移动游标，获取下一个数据，然后让count +=1
? ? ? ? while cur != None:
? ? ? ? ? ? # 计数
? ? ? ? ? ? count+=1
? ? ? ? ? ? # 移动游标
? ? ? ? ? ? cur = cur.next
? ? ? ? return count

? ? def add(self, item):
? ? ? ? """
? ? ? ? 头部添加数据
? ? ? ? 分析： 将数据添加到第一个节点当中
? ? ? ? 1、 需要先将node的next指向 原第一个节点，这原第一个节点就是self.head
? ? ? ? 2、 再讲self.head指向node进行连接
? ? ? ? """
? ? ? ? # 先实例化节点
? ? ? ? node = Node(item)
? ? ? ? # 将数据添加到头部当中
? ? ? ? node.next=self.head
? ? ? ? self.head=node

? ? def insert(self, index, item):
? ? ? ? """
? ? ? ? 指定位置添加数据
? ? ? ? 分析：
? ? ? ? 1、首先要找到，该位置的数据
? ? ? ? 2、将要添加的数据next等于 原位置的next数据
? ? ? ? 3、原数据的 next等于node新数据
? ? ? ? """
? ? ? ? if index<=0:
? ? ? ? ? ? # 如果输入的索引小于或者等于O，默认使用头插发
? ? ? ? ? ? self.add(item)
? ? ? ? elif index>self.length():
? ? ? ? ? ? # 如果输入的索引大于链表的长度,使用尾插法
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? # 实例化数据节点
? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? # 找到该数据的位置
? ? ? ? ? ? # 实例化一个游标
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? # 计数
? ? ? ? ? ? conent = 0
? ? ? ? ? ? while conent<(index-1):
? ? ? ? ? ? ? ? conent+=1
? ? ? ? ? ? ? ? cur = cur.next

? ? ? ? ? ? node.next=cur.next
? ? ? ? ? ? cur.next=node

? ? def search(self, item):
? ? ? ? """
? ? ? ? 查询指定的数据是否存在
? ? ? ? 分析： 查询指定的数据，需要对整个链表扫描，判断这个数据是否等的该节点中的数据
? ? ? ? """
? ? ? ? # 实例化一个游标
? ? ? ? cur = self.head
? ? ? ? # 进行判断是否相等
? ? ? ? while cur != None:
? ? ? ? ? ? # 判断
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? pass
? ? ? ? # 否则返回False
? ? ? ? return False

? ? def remove(self, item):
? ? ? ? """
? ? ? ? 移除指定的数据
? ? ? ? 分析：
? ? ? ? 1、删除数据，需要首先判断数据是否存在
? ? ? ? 2、找到该数据所在的位置，将该数据的上一个数据的next指向自己的next
? ? ? ? 3、如何获取该数据的指向，和上一个数据的指向
? ? ? ? 4、需要定义两个指针
? ? ? ? 5、先将两个指针相等，再讲一个指针先移动一次，再同时移动

? ? ? ? """
? ? ? ? # 先找到该数据
? ? ? ? cur = self.head
? ? ? ? por = None

? ? ? ? while cur != None:
? ? ? ? ? ? if cur.item==item:
? ? ? ? ? ? ? ? # 要判断是否为第一个节点
? ? ? ? ? ? ? ? if cur == self.head:
? ? ? ? ? ? ? ? ? ? self.head = cur.next
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? por.next = cur.next
? ? ? ? ? ? ? ? break
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? # 如果在当前节点中没有相等的，将节点进行移动
? ? ? ? ? ? ? ? # 移动要注意，现将两个游标相等，再讲另一个游标移动一次
? ? ? ? ? ? ? ? por = cur
? ? ? ? ? ? ? ? cur = cur.next

测试运行

# 程序的入口
if __name__ == "__main__":
? ? s = Linklist()
? ? s.append(100)
? ? s.append(200)
? ? s.append(300)
? ? s.add(1)
? ? s.add(12)
? ? s.insert(-1,6)
? ??
? ? s.travel() ? ? ? # ?6 12 1 100 200 300?
? ? print(s.length()) ?# 6
? ? print(s.search(11)) # False
? ? s.remove(12)
? ? s.travel() ? ? ? # 6 1 100 200 300?
? ? print(s.length()) ?# 5
? ? print(s.search(11)) # False
? ? pass

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

查看更多关于python单向链表实例详解的详细内容...