Python数据结构与算法之链表,无序链表详解

Python数据结构与算法之链表，无序链表详解

介绍

链表是一种基础的数据结构，是由一系列节点组成的线性结构。它的每个节点都包括两个部分，一个是存储数据的部分，另一个是指向下一个节点的部分。链表有很多种不同的形式，其中无序链表是其中最基础同时也是最简单的一种。无序链表可以用于存储任意类型的数据，不同于数组，它没有固定的大小限制。

实现无序链表的基本结构

链表由节点(node)组成，每个节点由data和next两个属性组成，其中data用于存储数据，next用于存储下一个节点的引用。构建一个无序链表可以通过创建一个LinkedList类，并提供如下方法实现。

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

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

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

    def display(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            current = current.next

在上面的代码中，我们定义一个Node类用于存储数据，LinkedList类用于管理链表。在LinkedList类中，我们通过add方法向链表中添加节点，并通过display方法遍历链表中的所有节点，将每个节点的数据打印出来。

示例

下面我们来看一些实例，看看如何使用无序链表。

示例1：

我们需要存储一些数据，并进行遍历展示。

my_list = LinkedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)

my_list.display()   # 54 26 93 17 77 31

在这个例子中，我们创建了一个名为my_list的链表，并在其中添加了6个元素。然后我们通过调用display方法遍历链表，并将其中的元素打印出来。

示例2：

在下面的例子中，我们需要实现一个remove方法。这样我们就可以使用链表来管理我们的数据，实现增删查改的功能。

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

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

    def find(self, data):
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def remove(self, data):
        previous = None
        current = self.head
        while current:
            if current.data == data:
                if previous:
                    previous.next = current.next
                else:
                    self.head = current.next
                return True
            previous = current
            current = current.next
        return False

在这个例子中，我们重载了LinkedList类中的方法，在add方法中我们添加了一个节点到链表中，在find方法中我们查找指定值的节点是否存在，若存在则返回True，若不存在则返回False。在remove方法中，我们先查找要删除数据的前驱节点，然后删除数据。

我们可以使用下面的代码测试一下remove方法。

my_list = LinkedList()
my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)

my_list.display()      # 54 26 93 17 77 31
my_list.remove(31)
my_list.remove(77)
my_list.remove(54)

my_list.display()      # 26 93 17

在这个例子中，我们创建了一个名为my_list的链表，并在其中添加了6个元素。然后我们删除元素中的31、77和54。最后通过调用display方法来遍历链表并展示删除元素后的链表。

总结

无序链表是一个基础的数据结构，本文中介绍了如何实现无序链表，并给出了两个实例。通过实现这些方法，我们可以方便地对链表进行增删查改的操作。