Python的链表

Python技术
2023-05-06 17:03

　　Python可以使用列表来实现链表的功能。链表相关操作包含:

　　1. 节点类:

　　- 用于存储节点信息。包含值和下一节点引用

　　- 语法:

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

　　2. 链表类:

　　- 包含头节点head和链表长度length

　　- 提供节点增删改和遍历方法

　　- 语法:

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

　　3. append(val):

　　- 在末尾添加新节点

　　- 先创建新节点,判断头节点是否存在

　　- 不存在直接将新节点设为头节点,存在遍历至尾节点,将尾节点的next设为新节点

　　- 语法:

python
    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.length += 1
            return 
        
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node
        self.length += 1

　　4. prepend(val):

　　- 在头部添加新节点

　　- 创建新节点,新节点的next设为头节点head

　　- 将head更新为新节点

　　- 语法:

python
    def prepend(self, val):
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        self.length += 1

　　5. insert(index, val):

　　- 在指定索引处插入新节点

　　- 先判断索引是否合理,找到前一个节点和当前节点

　　- 前一个节点的next指向新节点,新节点的next指向当前节点

　　- 语法:

python
    def insert(self, index, val):
        if index < 0 or index > self.length:  
            return 

        if index == 0:  
            self.prepend(val)
            return

        new_node = Node(val)
        count = 0
        cur = self.head 

        while count < index - 1:  
            cur = cur.next
            count += 1

        new_node.next = cur.next
        cur.next = new_node
        self.length += 1

　　示例:

python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None
        self.length = 0  
        
    # append prepend insert方法...

linked_list = LinkedList()  
linked_list.append(1)  
linked_list.append(2)
linked_list.insert(1, 3)

　　链表是一种重要的数据结构,要理解链表与数组的区别。要会创建节点和链表类,实现增删改操作。

　　要熟练掌握append、prepend和insert等方法。要在项目中根据需求选择链表解决问题。

Python的链表