Python数据结构与算法之列表（链表，linkedlist）简单实现

在Python中，列表是一种非常常用的数据类型。除了Python内置的列表，我们还可以使用链表（linkedlist）来实现列表。链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在本文中，我们将详细介绍如何使用Python实现链表，并演示如何使用链表实现列表。

链表的实现

在Python中，我们可以使用类来实现链表。每个节点可以表示为一个类的实例，包含数据和指向下一个节点的指针。链表本身也可以表示为一个类的实例，包含指向链表头部的指针。下面是一个简单的链表实现：

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

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

上述代码中，我们定义了一个Node类表示链表的节点，包含数据和指向下一个节点的指针。我们还定义了一个LinkedList类表示链表本身，包含指向链表头部的指针。

链表的操作

链表支持许多操作，例如添加元素、删除元素、访问元素等。下面是一些常用的链表操作。

添加元素

要向链表中添加元素，我们可以使用append()函数或insert()函数。append()函数用于在链表末尾添加元素，而insert()函数用于在指定位置添加元素。例如：

# 向链表中添加元素
class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    def insert(self, prev_node, data):
        if prev_node is None:
            print("Previous node is not in the list")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

上述代码中，我们定义了LinkedList类的append()函数和insert()函数。append()函数用于在链表末尾添加元素，如果链表为空，则将新节点设置为链表头部。insert()函数用于在指定位置添加元素，如果指定的前一个节点不存在，则输出错误信息。

删除元素

要从链表中删除元素，我们可以使用remove()函数或pop()函数。remove()函数用于删除指定的元素，而pop()函数用于删除指定位置的元素。例如：

# 从链表中删除元素
class LinkedList:
    def __init__(self):
        self.head = None

    def remove(self, key):
        curr_node = self.head
        if curr_node is not None and curr_node.data == key:
            self.head = curr_node.next
            curr_node = None
            return
        prev_node = None
        while curr_node is not None and curr_node.data != key:
            prev_node = curr_node
            curr_node = curr_node.next
        if curr_node is None:
            return
        prev_node.next = curr_node.next
        curr_node = None

    def pop(self, pos=None):
        if self.head is None:
            return
        curr_node = self.head
        if pos == 0:
            self.head = curr_node.next
            curr_node = None
            return
        prev_node = None
        count = 0
        while curr_node is not None and count != pos:
            prev_node = curr_node
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return
        prev_node.next = curr_node.next
        curr_node = None

上述代码中，我们定义了LinkedList类的remove()函数和pop()函数。remove()函数用于删除指定的元素，如果指定的元素不存在，则不进行任何操作。pop()函数用于删除指定位置的元素，如果指定的位置不存在，则不进行任何操作。

访问元素

要访问链表中的元素，我们可以使用get()函数。get()函数用于获取指定位置的元素。例如：

# 访问链表中的元素
class LinkedList:
    def __init__(self):
        self.head = None

    def get(self, pos):
        curr_node = self.head
        count = 0
        while curr_node is not None and count != pos:
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return None
        return curr_node.data

上述代码中，我们定义了LinkedList类的get()函数。get()函数用于获取指定位置的元素，如果指定的位置不存在，则返回None。

示例说明

下面是两个示例，演示了如何使用链表实现列表。

示例1：创建、访问和修改列表

下面是一个示例，演示了如何使用链表实现列表的创建、访问和修改：

# 创建、访问和修改列表
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    def get(self, pos):
        curr_node = self.head
        count = 0
        while curr_node is not None and count != pos:
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return None
        return curr_node.data

    def set(self, pos, data):
        curr_node = self.head
        count = 0
        while curr_node is not None and count != pos:
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return
        curr_node.data = data

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)

print(my_list.get(0))  # 输出：1
print(my_list.get(2))  # 输出：3

my_list.set(1, 4)
print(my_list.get(1))  # 输出：4

上述代码中，我们首先定义了Node类和LinkedList类，分别表示链表的节点和链表本身。然后，我们创建了一个包含3个元素的链表my_list，并使用get()函数访问了链表中的元素。接着，我们使用set()函数修改了链表中的元素，并使用get()函数验证了修改结果。

示例2：添加元素、删除元素和遍历链表

下面是一个示例，演示了如何使用链表实现列表的添加元素、删除元素和遍历：

# 添加元素、删除元素和遍历链表
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    def remove(self, key):
        curr_node = self.head
        if curr_node is not None and curr_node.data == key:
            self.head = curr_node.next
            curr_node = None
            return
        prev_node = None
        while curr_node is not None and curr_node.data != key:
            prev_node = curr_node
            curr_node = curr_node.next
        if curr_node is None:
            return
        prev_node.next = curr_node.next
        curr_node = None

    def traverse(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)

my_list.traverse()  # 输出：1 2 3

my_list.remove(2)

my_list.traverse()  # 输出：1 3

上述代码中，我们首先定义了Node类和LinkedList类，分别表示链表的节点和链表本身。然后，我们创建了一个包含3个元素的链表my_list，并使用traverse()函数遍历了链表中的元素。接着，我们使用remove()函数删除了链表中的元素，并使用traverse()函数验证了删除结果。

总之，链表是一种非常重要的数据结构，可以用于实现列表等数据类型。我们可以使用类来实现链表，使用append()函数和insert()函数向链表中添加元素，使用remove()函数和pop()函数从链表中删除元素，使用get()函数访问链表中的元素，使用traverse()函数遍历链表中的元素。