python单链表实现代码实例

下面是python单链表实现代码实例的完整攻略：

什么是单链表

单链表是数据结构中最简单的一种形式，每个节点包含两个信息：当前节点的值（value）和指向下一个节点的引用（next）。单链表的第一个节点被称为头节点，而最后一个节点被称为尾节点。

单链表的实现

在Python中，可以通过定义一个链表类来实现单链表。该类至少应该具有以下方法：

• __init__(): 初始化链表。
• is_empty(): 返回链表是否为空。
• length(): 返回链表的长度。
• travel(): 遍历链表并打印每个节点。
• add(value): 在链表头部添加一个节点。
• append(value): 在链表尾部添加一个节点。
• insert(index, value): 在指定位置插入一个节点。
• remove(value): 删除链表中第一个值为value的节点。
• pop(): 删除链表中最后一个节点，并返回其值。

其中，__init__()方法应该初始化一个头节点，指向下一个节点的引用为None。

下面是一个Python单链表的实现代码示例：

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

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

    def is_empty(self):
        return self.head.next == None

    def length(self):
        count = 0
        current = self.head.next
        while current != None:
            count += 1
            current = current.next
        return count

    def travel(self):
        current = self.head.next
        while current != None:
            print(current.value, end=' ')
            current = current.next
        print()

    def add(self, value):
        node = Node(value)
        node.next = self.head.next
        self.head.next = node

    def append(self, value):
        node = Node(value)
        current = self.head
        while current.next != None:
            current = current.next
        current.next = node

    def insert(self, index, value):
        if index <= 0:
            self.add(value)
        elif index >= self.length():
            self.append(value)
        else:
            node = Node(value)
            current = self.head.next
            count = 0
            while count < index - 1:
                count += 1
                current = current.next
            node.next = current.next
            current.next = node

    def remove(self, value):
        current = self.head.next
        previous = self.head
        while current != None:
            if current.value == value:
                previous.next = current.next
                return
            previous = current
            current = current.next

    def pop(self):
        if self.is_empty():
            return None
        current = self.head
        while current.next.next != None:
            current = current.next
        popped_node = current.next
        current.next = None
        return popped_node.value

上述代码实现了一个单链表类，具有添加、删除、插入、遍历等操作。下面给出两个使用示例：

示例1：创建一个链表并遍历

l = LinkedList()
l.append(1)
l.add(2)
l.insert(1, 3)
l.travel()

输出：

2 3 1

示例2：从一个链表中删除一个节点

l = LinkedList()
l.append(1)
l.add(2)
l.insert(1, 3)
l.remove(2)
l.travel()

输出：

2 1