Python中链表的搜索和查找操作

2023-04-11 00:00:00 操作查找链表

链表的搜索和查找操作可以分为两种，分别是按索引（或位置）进行的搜索和按值进行的搜索。

按索引进行搜索的操作比较简单，只需要从头节点开始依次遍历，直到找到目标节点或到达链表尾部即可。而按值进行搜索的操作则需要依次遍历每一个节点的值，直到找到目标值或到达链表尾部。

下面是Python中链表按索引进行搜索和按值进行搜索的代码示例：

按索引进行搜索：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def get_node(self, index):
        if index < 0 or not self.head:
            return None

        curr = self.head
        i = 0
        while curr and i < index:
            curr = curr.next
            i += 1

        return curr if i == index else None

按值进行搜索：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def search(self, value):
        curr = self.head
        while curr:
            if curr.data == value:
                return curr
            curr = curr.next

        return None

其中，get_node()方法中的index表示要搜索的索引，search()方法中的value表示要搜索的值。两种搜索方式都采用了遍历链表的方法实现，时间复杂度为O(n)。

相关文章