博客

python的链表基础知识点

  • Post category:Python

Python的链表基础知识点

什么是链表

链表是一种数据结构，它由一系列节点构成，每个节点包含两个部分，一个是存放数据的变量，另一个是存放指向下一个节点的指针，通过指针可以找到下一个节点的位置，从而实现节点之间的关联。

链表有单向链表和双向链表之分，单向链表中每个节点只指向下一个节点，而双向链表中每个节点既指向前一个节点，也指向后一个节点。在Python中，链表通常使用class来表示。

如何创建链表

我们可以使用类来创建链表，每个节点都是这个类的一个实例对象。代码示例：

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

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

上面的代码中，Node类表示链表中的节点，val属性存放节点的数据，next属性存放指向下一个节点的指针。LinkedList类表示整个链表，它有一个head属性，指向链表的第一个节点。

如何向链表中添加节点

可以在LinkedList类中添加一个追加节点的方法add_node。代码示例：

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

    def add_node(self, val):
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

上面的add_node方法中，添加新节点的过程可以分为以下几个步骤：

  1. 创建一个新节点new_node
  2. 如果链表为空，即head为None，那么将head指向新节点，退出函数
  3. 否则从头节点向后遍历节点，找到最后一个节点last
  4. 将最后一个节点的next指向新节点

如何从链表中删除节点

可以在LinkedList类中添加一个删除节点的方法remove_node_by_value。代码示例：

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

    def add_node(self, val):
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def remove_node_by_value(self, val):
        if self.head is None:
            return
        if self.head.val == val:
            self.head = self.head.next
            return

        last = self.head
        while last.next:
            if last.next.val == val:
                last.next = last.next.next
                return
            last = last.next

上面的remove_node_by_value方法中，删除节点的过程可以分为以下几个步骤：

  1. 如果链表为空，即head为None，退出函数
  2. 如果要删除的节点是头节点，即head的值为要删除的值，那么将head指向head.next，就删除了头节点
  3. 否则从头节点向后遍历节点，找到要删除节点的前一个节点last
  4. 将找到的last节点的next指向要删除节点的下一个节点

示例说明

下面的代码展示了如何创建一个链表，并在其中添加和删除节点：

linked_list = LinkedList()
linked_list.add_node(1)
linked_list.add_node(2)
linked_list.add_node(3)
linked_list.add_node(4)
linked_list.add_node(5)
print("before removed:")
last = linked_list.head
while last:
    print(last.val)
    last = last.next
linked_list.remove_node_by_value(3)
print("after removed:")
last = linked_list.head
while last:
    print(last.val)
    last = last.next

上面的代码创建了一个链表，其中包含了5个节点，值分别为1, 2, 3, 4, 5。然后删除了值为3的节点，最后输出删除节点后的链表。

Tags: ,