python 实现单链表的基础操作：插入、删除、遍历、获取元素等 |
您所在的位置：网站首页 › 单链表取值代码 › python 实现单链表的基础操作：插入、删除、遍历、获取元素等 |
python 实现单链表的基础操作：插入、删除、遍历、获取元素等
|
回顾一下单链表的知识，并用python实现单链表的基础操作：插入，删除，遍历，判空，清空链表，求长度， 获取元素，判断元素是否存在等。 链表通过指针将零散的内存块连接在一起，链表的每个节点存储有该节点的值和下一个节点的地址。 链表的第一个节点为基节点，最后一个节点是尾节点。头节点记录了链表的基地址，最后一个节点的指针指向None。 链表的插入，删除操作的时间复杂度都是O(1), 单链表的遍历时间复杂度是O(n)。
定义链表的同时也要定义链表节点Node，节点存储值item和指针_next, 也可理解为引用，指向的是下一个节点的地址。 看了下王争老师的代码，对链表的插入和删除操作考虑都比较全面。 动手写了一遍之后，发现根据某个值删除节点的操作有点意思。 因为不知道这个值在哪里，所以需要挨个遍历链表，删除该节点时，将删除的节点的值赋值为下一个节点的值，然后删除下一个节点。 就像是如果要我死，就让我变成A，然后杀了A的原主。 我没有了，而A还活着。但其实我就是A。 def delete_by_value(self, value: int): if not self.head or not value: return fake_head = Node(-1) fake_head.next = self.head prev, current = fake_head, self.head while current: if current.item != value: prev.next = current prev = prev.next current = current.next if prev.next: # current.item == value prev.next = prev.next.next self.head = fake_head.next 全部代码 class Node: """链表节点""" def __init__(self, item: int, next=None): self.item = item self.next = next class LinkedList: """链表""" def __init__(self): self.head = None def find_by_value(self, value: int): # 根据值查找节点 p = self.head while p and p.item != value: p = p.next return p def find_by_index(self, position: int): # 根据索引位置查找节点，需要挨个遍历 p = self.head index = 0 while p and index != position: p = p.next index += 1 return p def insert_value_to_head(self, value: int): node = Node(value) self.insert_node_to_head(node) def insert_node_to_head(self, node): if node: node.next = self.head self.head = node def insert_node_after(self, node, new_node): if not node or not new_node: return new_node.next = node.next node.next = new_node def insert_value_after(self, node, value): new_node = Node(value) self.insert_node_after(node, new_node) def insert_node_before(self, node, new_node): if not self.head or not node or not new_node: return if node == self.head: self.insert_node_to_head(new_node) return p = self.head while p and p.next != node: p = p.next if not p: return new_node.next = node p.next = new_node def insert_value_before(self, value: int, node): new_node = Node(value) self.insert_node_before(node, new_node) def delete_by_node(self, node): # 删除某个节点 if not self.head or not node: return # 不是最后一个节点，可以直接删除, 删除的复杂度为O(1) if node.next: node.item = node.next.item node.next = node.next.next p = self.head while p and p.next != node: p = p.next if not p: return p.next = node.next def delete_by_value(self, value: int): # 删除某个值对应的节点 if not self.head or not value: return fake_head = Node(-1) fake_head.next = self.head prev, current = fake_head, self.head while current: if current.item != value: prev.next = current prev = prev.next current = current.next if prev.next: # current.item == value prev.next = prev.next.next self.head = fake_head.next def __repr__(self): # 打印链表，重写repr或者str函数 a = [] p = self.head while p: a.append(p.item) p = p.next return " ".join(map(str, a)) if __name__ == '__main__': l = LinkedList() for i in range(10): l.insert_value_to_head(i) node = l.find_by_value(5) l.insert_value_before(20, node) l.insert_value_after(node, 24) print(l) l.delete_by_value(4) print(l)以下是一些基础代码，不知道为什么看代码有点幼稚。 判空判断链表是否是空链表只需要判断头节点是否为None即可。 如果为None表示头节点没有指向下一个节点。 def is_empty(self): """判断是否为空链表，头节点为None则是空""" return self._head is None 求链表长度从头节点开始遍历，直到最后的空节点None。 def length(self): """求链表的长度""" p = self._head count = 0 while p: count += 1 p = p._next return count 向链表尾部追加元素如果链表是空链表，则该节点为头节点，否则依次遍历到最后一个值p，然后 p._next = node 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 向链表头部插入元素头插法。其实就是把该元素设置为头节点 分为头插，尾插，中间插入 插入元素的核心是node._next = pre._next , pre._next = node, 先后次序一定要注意。先让待插入的node指向p._next, 再让p指向node |
【本文地址】
今日新闻 |
推荐新闻 |