用python实现单链表的基础操作
1 问题
用python实现单链表的基础操作：插入，删除，遍历，判空，清空链表，求长度，获取元素，判断元素是否存在。
2 方法
解决问题的步骤采用如下方式：
使用函数和类的方法来实现单链表的基本操作
插入操作时使用头插法
删除操作时，删除头节点一行代码即可，其他位置的需要判断+遍历
通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。
代码清单 1
| class Node: """链表节点初始化""" def __init__(self, item): self.item = item self._next = None class LinkList: """链表及其相关操作""" def __init__(self): self._head = None def is_empty(self): """判断是否为空链表，头节点为None则是空""" return self._head is None def length(self): """求链表的长度""" p = self._head count = 0 while p: count += 1 p = p._next return count def append(self, item): """向链表尾部添加元素, 考虑是否是空链表""" node = Node(item) p = self._head if not p: self._head = node else: while p._next: p = p._next p._next = node def add(self, item): """向链表头部插入元素""" node = Node(item) node._next = self._head self._head = node def insert(self, position, item): """向链表中插入元素""" # 头插 or 尾插 or 中间插入 if position <= 0: self.add(item) elif position >= self.length(): self.append(item) else: pre = self._head count = 0 while count < position - 1: count += 1 pre = pre._next node = Node(item) node._next = pre._next pre._next = node def get_item(self, position): """获取某位置的元素""" if position < 0 or position >= self.length(): return None p = self._head count = 0 while count != position: p = p._next count += 1 return p.item def exixt_value(self, item): """某个值是否存在""" p = self._head while p: if p.item == item: return True else: p = p._next return False def remove(self, item): """删除元素""" p = self._head pre = None while p: if p.item == item: # 是否头节点 if not pre: self._head = p._next else: pre._next = p._next break else: pre = p p = p._next def clear(self): """删除链表""" self._head = None def travel(self): """列表遍历""" p = self._head while p: print(p.item, end=" ") p = p._next print() if __name__ == '__main__': linklist = LinkList() linklist.append(2) linklist.append(3) linklist.append(4) linklist.append(5) print(linklist.length()) linklist.travel() linklist.add(1) linklist.add(0) linklist.travel() linklist.insert(2, 8) linklist.insert(2, 9) linklist.travel() print(linklist.get_item(2), linklist.get_item(12), linklist.get_item(4)) print(linklist.exixt_value(9), linklist.exixt_value(20)) linklist.remove(9) linklist.remove(5) linklist.travel() linklist.clear() linklist.travel() |
3 结语
针对用python实现单链表的基础操作，通过python运行实验，证明该方法是有效的，这种设置方法代码较多，因此未来还需继续改善这种方法以适应更多场景。