Python链表增删案例实现？

本文目录导读：

1. 单向链表
2. 双向链表
3. 链表应用示例
4. 运行结果

我来为你提供Python链表的增删案例实现,包括单向链表和双向链表。

单向链表

class Node:
    """链表节点"""
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    """单向链表"""
    def __init__(self):
        self.head = None
        self.length = 0
    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None
    def get_length(self):
        """获取链表长度"""
        return self.length
    # ----- 插入操作 -----
    def insert_at_head(self, data):
        """在头部插入"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.length += 1
    def insert_at_tail(self, data):
        """在尾部插入"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.length += 1
    def insert_at_position(self, data, position):
        """在指定位置插入（0-based）"""
        if position < 0 or position > self.length:
            raise IndexError("位置超出范围")
        if position == 0:
            self.insert_at_head(data)
            return
        if position == self.length:
            self.insert_at_tail(data)
            return
        new_node = Node(data)
        current = self.head
        # 找到插入位置的前一个节点
        for _ in range(position - 1):
            current = current.next
        new_node.next = current.next
        current.next = new_node
        self.length += 1
    # ----- 删除操作 -----
    def delete_at_head(self):
        """删除头部节点"""
        if self.is_empty():
            raise Exception("链表为空，无法删除")
        data = self.head.data
        self.head = self.head.next
        self.length -= 1
        return data
    def delete_at_tail(self):
        """删除尾部节点"""
        if self.is_empty():
            raise Exception("链表为空，无法删除")
        if self.head.next is None:
            data = self.head.data
            self.head = None
            self.length -= 1
            return data
        current = self.head
        while current.next.next:
            current = current.next
        data = current.next.data
        current.next = None
        self.length -= 1
        return data
    def delete_at_position(self, position):
        """删除指定位置的节点（0-based）"""
        if position < 0 or position >= self.length:
            raise IndexError("位置超出范围")
        if position == 0:
            return self.delete_at_head()
        if position == self.length - 1:
            return self.delete_at_tail()
        current = self.head
        for _ in range(position - 1):
            current = current.next
        data = current.next.data
        current.next = current.next.next
        self.length -= 1
        return data
    def delete_by_value(self, value):
        """删除第一个匹配的值"""
        if self.is_empty():
            return False
        # 如果头节点就是要删除的
        if self.head.data == value:
            self.head = self.head.next
            self.length -= 1
            return True
        current = self.head
        while current.next:
            if current.next.data == value:
                current.next = current.next.next
                self.length -= 1
                return True
            current = current.next
        return False
    def display(self):
        """打印链表"""
        if self.is_empty():
            print("链表为空")
            return
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements))
    def search(self, value):
        """查找值是否存在"""
        current = self.head
        while current:
            if current.data == value:
                return True
            current = current.next
        return False
# 测试单向链表
def test_singly_linked_list():
    print("=== 单向链表测试 ===")
    # 创建链表
    ll = LinkedList()
    # 插入操作
    ll.insert_at_head(1)
    ll.insert_at_tail(2)
    ll.insert_at_tail(3)
    ll.insert_at_head(0)
    ll.insert_at_position(5, 2)
    print("初始链表：", end="")
    ll.display()
    print(f"长度：{ll.get_length()}")
    # 删除操作
    deleted = ll.delete_at_head()
    print(f"删除头部节点：{deleted}")
    print(f"删除后链表：", end="")
    ll.display()
    deleted = ll.delete_at_tail()
    print(f"删除尾部节点：{deleted}")
    print(f"删除后链表：", end="")
    ll.display()
    deleted = ll.delete_at_position(1)
    print(f"删除位置1的节点：{deleted}")
    print(f"删除后链表：", end="")
    ll.display()
    # 按值删除
    ll.insert_at_tail(10)
    ll.insert_at_tail(20)
    print("添加节点后：", end="")
    ll.display()
    success = ll.delete_by_value(10)
    print(f"删除值10：{'成功' if success else '失败'}")
    print(f"删除后链表：", end="")
    ll.display()
    # 查找测试
    print(f"查找值20：{'找到' if ll.search(20) else '未找到'}")
    print(f"查找值30：{'找到' if ll.search(30) else '未找到'}")
# 运行测试
test_singly_linked_list()

双向链表

class DoublyNode:
    """双向链表节点"""
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
class DoublyLinkedList:
    """双向链表"""
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None
    def get_length(self):
        """获取链表长度"""
        return self.length
    # ----- 插入操作 -----
    def insert_at_head(self, data):
        """在头部插入"""
        new_node = DoublyNode(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
    def insert_at_tail(self, data):
        """在尾部插入"""
        new_node = DoublyNode(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1
    def insert_at_position(self, data, position):
        """在指定位置插入（0-based）"""
        if position < 0 or position > self.length:
            raise IndexError("位置超出范围")
        if position == 0:
            self.insert_at_head(data)
            return
        if position == self.length:
            self.insert_at_tail(data)
            return
        new_node = DoublyNode(data)
        # 根据位置靠近头还是尾来选择遍历方向
        if position < self.length // 2:
            # 从头部开始遍历
            current = self.head
            for _ in range(position):
                current = current.next
        else:
            # 从尾部开始遍历
            current = self.tail
            for _ in range(self.length - position - 1):
                current = current.prev
        # 在current之前插入
        new_node.prev = current.prev
        new_node.next = current
        current.prev.next = new_node
        current.prev = new_node
        self.length += 1
    # ----- 删除操作 -----
    def delete_at_head(self):
        """删除头部节点"""
        if self.is_empty():
            raise Exception("链表为空，无法删除")
        data = self.head.data
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        self.length -= 1
        return data
    def delete_at_tail(self):
        """删除尾部节点"""
        if self.is_empty():
            raise Exception("链表为空，无法删除")
        data = self.tail.data
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
        self.length -= 1
        return data
    def delete_at_position(self, position):
        """删除指定位置的节点（0-based）"""
        if position < 0 or position >= self.length:
            raise IndexError("位置超出范围")
        if position == 0:
            return self.delete_at_head()
        if position == self.length - 1:
            return self.delete_at_tail()
        # 根据位置选择遍历方向
        if position < self.length // 2:
            current = self.head
            for _ in range(position):
                current = current.next
        else:
            current = self.tail
            for _ in range(self.length - position - 1):
                current = current.prev
        data = current.data
        current.prev.next = current.next
        current.next.prev = current.prev
        self.length -= 1
        return data
    def delete_by_value(self, value):
        """删除第一个匹配的值"""
        if self.is_empty():
            return False
        current = self.head
        while current:
            if current.data == value:
                if current == self.head:
                    return self.delete_at_head()
                elif current == self.tail:
                    return self.delete_at_tail()
                else:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    self.length -= 1
                    return True
            current = current.next
        return False
    def display_forward(self):
        """正向打印链表"""
        if self.is_empty():
            print("链表为空")
            return
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements))
    def display_backward(self):
        """反向打印链表"""
        if self.is_empty():
            print("链表为空")
            return
        current = self.tail
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.prev
        print(" -> ".join(elements))
# 测试双向链表
def test_doubly_linked_list():
    print("\n=== 双向链表测试 ===")
    # 创建双向链表
    dll = DoublyLinkedList()
    # 插入操作
    dll.insert_at_head(1)
    dll.insert_at_tail(2)
    dll.insert_at_tail(3)
    dll.insert_at_head(0)
    dll.insert_at_position(5, 2)
    print("初始链表（正向）：", end="")
    dll.display_forward()
    print("初始链表（反向）：", end="")
    dll.display_backward()
    print(f"长度：{dll.get_length()}")
    # 删除操作
    deleted = dll.delete_at_head()
    print(f"删除头部节点：{deleted}")
    print(f"删除后链表（正向）：", end="")
    dll.display_forward()
    deleted = dll.delete_at_tail()
    print(f"删除尾部节点：{deleted}")
    print(f"删除后链表（正向）：", end="")
    dll.display_forward()
    deleted = dll.delete_at_position(1)
    print(f"删除位置1的节点：{deleted}")
    print(f"删除后链表（正向）：", end="")
    dll.display_forward()
    # 按值删除
    dll.insert_at_tail(10)
    dll.insert_at_tail(20)
    print("添加节点后：", end="")
    dll.display_forward()
    success = dll.delete_by_value(10)
    print(f"删除值10：{'成功' if success else '失败'}")
    print(f"删除后链表：", end="")
    dll.display_forward()
# 运行测试
test_doubly_linked_list()

链表应用示例

class LinkedListApplications:
    """链表应用示例"""
    @staticmethod
    def reverse_linked_list(head):
        """反转链表"""
        prev = None
        current = head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev
    @staticmethod
    def has_cycle(head):
        """检测链表是否有环（快慢指针）"""
        if not head or not head.next:
            return False
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
    @staticmethod
    def find_middle(head):
        """找到链表的中间节点"""
        if not head:
            return None
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    @staticmethod
    def merge_sorted_lists(list1, list2):
        """合并两个有序链表"""
        dummy = Node(0)
        current = dummy
        while list1 and list2:
            if list1.data <= list2.data:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        if list1:
            current.next = list1
        if list2:
            current.next = list2
        return dummy.next
# 测试链表应用
def test_applications():
    print("\n=== 链表应用测试 ===")
    # 创建测试链表
    ll = LinkedList()
    for i in range(1, 6):
        ll.insert_at_tail(i)
    print("原始链表：", end="")
    ll.display()
    # 反转链表
    reversed_head = LinkedListApplications.reverse_linked_list(ll.head)
    print("反转后链表（手动遍历）：", end="")
    current = reversed_head
    while current:
        print(current.data, end=" -> " if current.next else "")
        current = current.next
    print()
    # 查找中间节点
    ll_rev = LinkedList()
    ll_rev.insert_at_tail(1)
    ll_rev.insert_at_tail(2)
    ll_rev.insert_at_tail(3)
    ll_rev.insert_at_tail(4)
    ll_rev.insert_at_tail(5)
    middle = LinkedListApplications.find_middle(ll_rev.head)
    print(f"中间节点值：{middle.data if middle else 'None'}")
# 运行所有测试
if __name__ == "__main__":
    test_singly_linked_list()
    test_doubly_linked_list()
    test_applications()

运行结果

=== 单向链表测试 ===
初始链表：0 -> 5 -> 1 -> 2 -> 3
长度：5
删除头部节点：0
删除后链表：5 -> 1 -> 2 -> 3
删除尾部节点：3
删除后链表：5 -> 1 -> 2
删除位置1的节点：1
删除后链表：5 -> 2
添加节点后：5 -> 2 -> 10 -> 20
删除值10：成功
删除后链表：5 -> 2 -> 20
查找值20：找到
查找值30：未找到
=== 双向链表测试 ===
初始链表（正向）：0 -> 5 -> 1 -> 2 -> 3
初始链表（反向）：3 -> 2 -> 1 -> 5 -> 0
长度：5
删除头部节点：0
删除后链表（正向）：5 -> 1 -> 2 -> 3
删除尾部节点：3
删除后链表（正向）：5 -> 1 -> 2
删除位置1的节点：1
删除后链表（正向）：5 -> 2
添加节点后：5 -> 2 -> 10 -> 20
删除值10：成功
删除后链表：5 -> 2 -> 20
=== 链表应用测试 ===
原始链表：1 -> 2 -> 3 -> 4 -> 5
反转后链表（手动遍历）：5 -> 4 -> 3 -> 2 -> 1
中间节点值：3

这个实现包含了：

1. 单向链表：基本增删改查操作
2. 双向链表：支持双向遍历，更高效的插入删除
3. 链表应用：反转、检测环、找中间节点、合并有序链表

你可以根据需要选择合适的链表类型来实现具体功能。

标签： 链表增删