python 实现单链表的基础操作：插入、删除、遍历、获取元素等

ゞ浴缸里的玫瑰 2022-11-17 13:37 601阅读 0赞

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

链表通过指针将零散的内存块连接在一起，链表的每个节点存储有该节点的值和下一个节点的地址。

链表的第一个节点为基节点，最后一个节点是尾节点。头节点记录了链表的基地址，最后一个节点的指针指向None。

链表的插入，删除操作的时间复杂度都是O(1), 单链表的遍历时间复杂度是O(n)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70]

定义链表的同时也要定义链表节点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

#### 向链表头部插入元素 ####

头插法。其实就是把该元素设置为头节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 1]

def add(self, item):
            """向链表头部插入元素"""
            node = Node(item)
            node._next = self._head
            self._head = node

#### 向链表中插入元素 ####

分为头插，尾插，中间插入

插入元素的核心是`node._next = pre._next , pre._next = node`, 先后次序一定要注意。先让待插入的node指向p.\_next, 再让p指向node  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 2]

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

#### 删除元素 ####

删除头节点一行代码即可。  
其他位置的需要判断+遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 3]

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())  # 4
        linklist.travel()  # 2 3 4 5
        linklist.add(1)
        linklist.add(0)
        linklist.travel()   # 0 1 2 3 4 5
        linklist.insert(2, 8)
        linklist.insert(2, 9)
        linklist.travel()   # 0 1 9 8 2 3 4 5
        print(linklist.get_item(2), linklist.get_item(12), linklist.get_item(4))    # 9 None 2
        print(linklist.exixt_value(9), linklist.exixt_value(20))    # True False
        linklist.remove(9)
        linklist.remove(5)
        linklist.travel()   # 0 1 8 2 3 4
        linklist.clear()
        linklist.travel()  # 空

#### 完整代码 ####

""" 链表基本操作：创建空链表，删除链表，判断是否为空，添加元素，删除元素，遍历，定位，链表长度 """
    
    
    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())  # 4
        linklist.travel()  # 2 3 4 5
        linklist.add(1)
        linklist.add(0)
        linklist.travel()   # 0 1 2 3 4 5
        linklist.insert(2, 8)
        linklist.insert(2, 9)
        linklist.travel()   # 0 1 9 8 2 3 4 5
        print(linklist.get_item(2), linklist.get_item(12), linklist.get_item(4))    # 9 None 2
        print(linklist.exixt_value(9), linklist.exixt_value(20))    # True False
        linklist.remove(9)
        linklist.remove(5)
        linklist.travel()   # 0 1 8 2 3 4
        linklist.clear()
        linklist.travel()  # 空

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70]: /images/20221022/11f5ef5f28de4841bb8b248d5e54c8d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 1]: /images/20221022/ceacc7ba124e477c8b0d647aaaac79f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 2]: /images/20221022/2430f86a800441e88da04f5ecfe298eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 3]: /images/20221022/47770b47dc144d86996ff421ecf8f7f9.png