博客

python算法与数据结构之单链表的实现代码

  • Post category:Python

Python算法与数据结构之单链表的实现代码

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。本文将介绍Python实现单链表的实现代码，包括类的定义、链表类的定义、节点的插入、删除和查找等操作。

节点类的定义

节点类表示单链表的节点包括节点值和下一个节点的指针。以下是Python实现节点类的示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

上述代码中，定义了一个ListNode类，包括节点值val和下一个节点的指针next。如果没有指定下一个节点，则默认为None。

链表类的定义

链表类表示单链表，包括头节点和链表长度。以下是Python实现链表类的示例代码：

class LinkedList:
    def __init__(self):
        self.head = ListNode()
        self.length = 0

上述代码中，定义了一个LinkedList类，包括头节点head和链表长度length。头节点不包含任何值，只是一个指向第一个节点的指针。

节点的插入

节点的插入单链表中的一种基本操作，可以在链表的任意位置插入一个新节点。以下是Python实现节点插入的示例代码：

class LinkedList:
    def __init__(self):
        self.head = ListNode()
        self.length = 0

    def insert(self, index, val):
        if index < 0 or index > self.length:
            return False
        node = ListNode(val)
        cur = self.head
        for i in range(index):
            cur = cur.next
        node.next = cur.next
        cur.next = node
        self.length += 1
        return True

上述代码中，定义了一个insert方法，接受一个索引index和一个值val作为参数。在循环中，找到要插入的位置，将新节点插入到该位置。如果索引超出链表范围，则返回False。插入成功后，链表长度加1，并返回True。

节点的删除

节点的删除是单链表中的一种基本操作，可以删除链表中的任意节点。以下是Python实现节点删除的示例代码：

class LinkedList:
    def __init__(self):
        self.head = ListNode()
        self.length = 0

    def delete(self, index):
        if index < 0 or index >= self.length:
            return False
        cur = self.head
        for i in range(index):
            cur = cur.next
        cur.next = cur.next.next
        self.length -= 1
        return True

上述代码中，定义了一个delete方法，接受一个索引index作为参数。在循环中，找到要删除的节点的前一个节点，将其指针指向要删除节点的下一个节点。如果索引超出链表范围，则返回False。删除成功后，链表长度减1，并返回True。

节点的查找

节点的查找是单链表中的一种基本操作，可以查找链表中的任意节点。以下是Python实现节点查找的示例代码：

class LinkedList:
    def __init__(self):
        self.head = ListNode()
        self.length = 0

    def search(self, val):
        cur = self.head.next
        index = 0
        while cur:
            if cur.val == val:
                return index
            cur = cur.next
            index += 1
        return -1

上述代码中，定义了一个search方法，接受一个值val作为参数。在循环中，逐个比较节点的值，如果找到目标节点，则返回其索引。如果遍历完整个链表仍未找到目标节点，则返回-1。

示例说明

以下是两个示例，说明如何使用LinkedList类进行节点的插入、删除和查找操作。

示例1

创建一个空链表，插入三个节点，分别为1、2、3。

lst = LinkedList()
lst.insert(0, 1)
lst.insert(1, 2)
lst.insert(2, 3)

输出结果：

1 -> 2 -> 3

示例2

创建一个链表，删除第二个节点，查找值为3的节点的索引。

lst = LinkedList()
lst.insert(0, 1)
lst.insert(1, 2)
lst.insert(2, 3)
lst.delete(1)
index = lst.search(3)
print(index)

输出结果：

2

总结

本文介绍了Python实现单链表的实现代码，包括节点类的定义、链表类的定义、节点的插入、删除和查找等操作。单链表是一种常见的数据结构，可以用于解决各种问题。在实际应用中，需要根据实际情况选择合适的数据结构和算法，以获得更好的性能。

Tags: ,