Python链表创建案例怎么写？

本文目录导读：

1. 单向链表
2. 双向链表
3. 快速创建链表（常用于算法题）
4. 带常用操作的链表类

我来给你介绍几种Python链表创建的常见案例：

单向链表

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
    # 在末尾添加节点
    def append(self, val):
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    # 在开头添加节点
    def prepend(self, val):
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
    # 删除指定值的节点
    def delete(self, val):
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next
    # 打印链表
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.val))
            current = current.next
        print(' -> '.join(elements))
# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.display()  # 输出: 0 -> 1 -> 2 -> 3
ll.delete(2)
ll.display()  # 输出: 0 -> 1 -> 3

双向链表

class DoublyListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    def append(self, val):
        new_node = DoublyListNode(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node
    def prepend(self, val):
        new_node = DoublyListNode(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    def display_forward(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.val))
            current = current.next
        print(' -> '.join(elements))
    def display_backward(self):
        elements = []
        current = self.tail
        while current:
            elements.append(str(current.val))
            current = current.prev
        print(' -> '.join(elements))
# 使用示例
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(0)
dll.display_forward()   # 输出: 0 -> 1 -> 2 -> 3
dll.display_backward()  # 输出: 3 -> 2 -> 1 -> 0

快速创建链表（常用于算法题）

# 从列表快速创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head
# 打印链表（用于测试）
def print_linked_list(head):
    current = head
    while current:
        print(current.val, end=' -> ')
        current = current.next
    print('None')
# 使用示例
arr = [1, 2, 3, 4, 5]
head = create_linked_list(arr)
print_linked_list(head)  # 输出: 1 -> 2 -> 3 -> 4 -> 5 -> None

带常用操作的链表类

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def __len__(self):
        return self.size
    def __str__(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.val))
            current = current.next
        return ' -> '.join(elements)
    def insert(self, index, val):
        if index < 0 or index > self.size:
            raise IndexError("Index out of range")
        new_node = ListNode(val)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
        self.size += 1
    def remove(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        if index == 0:
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            current.next = current.next.next
        self.size -= 1
    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        current = self.head
        for _ in range(index):
            current = current.next
        return current.val
    def find(self, val):
        current = self.head
        index = 0
        while current:
            if current.val == val:
                return index
            current = current.next
            index += 1
        return -1
# 使用示例
ll = LinkedList()
ll.insert(0, 10)
ll.insert(1, 20)
ll.insert(1, 15)
print(ll)  # 输出: 10 -> 15 -> 20
print(len(ll))  # 输出: 3
print(ll.get(1))  # 输出: 15
print(ll.find(20))  # 输出: 2
ll.remove(1)
print(ll)  # 输出: 10 -> 20

这些案例覆盖了链表的基本操作，你可以根据实际需求选择合适的实现方式，在算法题中,通常使用第三种快速创建链表的方式会更方便。

标签： 链表