用python实现单链表的基础操作

本是古典何须时尚 2024-02-05 12:29 59阅读 0赞

**1** **问题**

用python实现单链表的基础操作：插入，删除，遍历，判空，清空链表，求长度，获取元素，判断元素是否存在。

**2** **方法**

解决问题的步骤采用如下方式：

1.  使用函数和类的方法来实现单链表的基本操作
2.  插入操作时使用头插法
3.  删除操作时，删除头节点一行代码即可，其他位置的需要判断+遍历

通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class Node: &nbsp; &nbsp;"""链表节点初始化""" &nbsp; &nbsp;def __init__(self, item): &nbsp; &nbsp; &nbsp; &nbsp;self.item = item &nbsp; &nbsp; &nbsp; &nbsp;self._next = None class LinkList: &nbsp; &nbsp;"""链表及其相关操作""" &nbsp; &nbsp;def __init__(self): &nbsp; &nbsp; &nbsp; &nbsp;self._head = None &nbsp; &nbsp;def is_empty(self): &nbsp; &nbsp; &nbsp; &nbsp;"""判断是否为空链表，头节点为None则是空""" &nbsp; &nbsp; &nbsp; &nbsp;return self._head is None &nbsp; &nbsp;def length(self): &nbsp; &nbsp; &nbsp; &nbsp;"""求链表的长度""" &nbsp; &nbsp; &nbsp; &nbsp;p = self._head &nbsp; &nbsp; &nbsp; &nbsp;count = 0 &nbsp; &nbsp; &nbsp; &nbsp;while p: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;count += 1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p._next &nbsp; &nbsp; &nbsp; &nbsp;return count &nbsp; &nbsp;def append(self, item): &nbsp; &nbsp; &nbsp; &nbsp;"""向链表尾部添加元素, 考虑是否是空链表""" &nbsp; &nbsp; &nbsp; &nbsp;node = Node(item) &nbsp; &nbsp; &nbsp; &nbsp;p = self._head &nbsp; &nbsp; &nbsp; &nbsp;if not p: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;self._head = node &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while p._next: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p._next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p._next = node &nbsp; &nbsp;def add(self, item): &nbsp; &nbsp; &nbsp; &nbsp;"""向链表头部插入元素""" &nbsp; &nbsp; &nbsp; &nbsp;node = Node(item) &nbsp; &nbsp; &nbsp; &nbsp;node._next = self._head &nbsp; &nbsp; &nbsp; &nbsp;self._head = node &nbsp; &nbsp;def insert(self, position, item): &nbsp; &nbsp; &nbsp; &nbsp;"""向链表中插入元素""" &nbsp; &nbsp; &nbsp; &nbsp;# 头插 or 尾插 or 中间插入 &nbsp; &nbsp; &nbsp; &nbsp;if position &lt;= 0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;self.add(item) &nbsp; &nbsp; &nbsp; &nbsp;elif position &gt;= self.length(): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;self.append(item) &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre = self._head &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;count = 0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while count &lt; position - 1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;count += 1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre = pre._next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;node = Node(item) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;node._next = pre._next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre._next = node &nbsp; &nbsp;def get_item(self, position): &nbsp; &nbsp; &nbsp; &nbsp;"""获取某位置的元素""" &nbsp; &nbsp; &nbsp; &nbsp;if position &lt; 0 or position &gt;= self.length(): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return None &nbsp; &nbsp; &nbsp; &nbsp;p = self._head &nbsp; &nbsp; &nbsp; &nbsp;count = 0 &nbsp; &nbsp; &nbsp; &nbsp;while count != position: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p._next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;count += 1 &nbsp; &nbsp; &nbsp; &nbsp;return p.item &nbsp; &nbsp;def exixt_value(self, item): &nbsp; &nbsp; &nbsp; &nbsp;"""某个值是否存在""" &nbsp; &nbsp; &nbsp; &nbsp;p = self._head &nbsp; &nbsp; &nbsp; &nbsp;while p: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if p.item == item: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return True &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p._next &nbsp; &nbsp; &nbsp; &nbsp;return False &nbsp; &nbsp;def remove(self, item): &nbsp; &nbsp; &nbsp; &nbsp;"""删除元素""" &nbsp; &nbsp; &nbsp; &nbsp;p = self._head &nbsp; &nbsp; &nbsp; &nbsp;pre = None &nbsp; &nbsp; &nbsp; &nbsp;while p: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if p.item == item: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# 是否头节点 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if not pre: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;self._head = p._next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre._next = p._next &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;break &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pre = p &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p._next &nbsp; &nbsp;def clear(self): &nbsp; &nbsp; &nbsp; &nbsp;"""删除链表""" &nbsp; &nbsp; &nbsp; &nbsp;self._head = None &nbsp; &nbsp;def travel(self): &nbsp; &nbsp; &nbsp; &nbsp;"""列表遍历""" &nbsp; &nbsp; &nbsp; &nbsp;p = self._head &nbsp; &nbsp; &nbsp; &nbsp;while p: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;print(p.item, end=" ") &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p._next &nbsp; &nbsp; &nbsp; &nbsp;print() if __name__ == '__main__': &nbsp; &nbsp;linklist = LinkList() &nbsp; &nbsp;linklist.append(2) &nbsp; &nbsp;linklist.append(3) &nbsp; &nbsp;linklist.append(4) &nbsp; &nbsp;linklist.append(5) &nbsp; &nbsp;print(linklist.length()) &nbsp; &nbsp; &nbsp;linklist.travel() &nbsp; &nbsp; &nbsp;linklist.add(1) &nbsp; &nbsp;linklist.add(0) &nbsp; &nbsp;linklist.travel() &nbsp; &nbsp; &nbsp;linklist.insert(2, 8) &nbsp; &nbsp;linklist.insert(2, 9) &nbsp; &nbsp;linklist.travel() &nbsp; &nbsp; &nbsp;print(linklist.get_item(2), linklist.get_item(12), linklist.get_item(4)) &nbsp; &nbsp; &nbsp; &nbsp;print(linklist.exixt_value(9), linklist.exixt_value(20)) &nbsp; &nbsp; &nbsp; &nbsp;linklist.remove(9) &nbsp; &nbsp;linklist.remove(5) &nbsp; &nbsp;linklist.travel() &nbsp; &nbsp; &nbsp;linklist.clear() &nbsp; &nbsp;linklist.travel() &nbsp;</td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

针对用python实现单链表的基础操作，通过python运行实验，证明该方法是有效的，这种设置方法代码较多，因此未来还需继续改善这种方法以适应更多场景。