Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

Python数据结构与算法之链表定义与用法实例详解

什么是链表？

链表是一种常见的数据结构，它由一个个的节点组成，每个节点包含两部分，一部分存储数据，一部分存储下一个节点在哪里的指针。通过节点之间的指针，就可以将节点串起来，形成一个链表。

链表和数组是两种截然不同的数据结构，数组的元素在内存中是连续存储的，而链表的节点却可以分散在内存的不同位置，这也是链表灵活性的一大体现，它可以根据实际情况灵活地分配空间，避免了数组因空间不足而无法存储的情况。同时，链表的节点插入和删除操作也比较方便，相对于数组，时间复杂度也更低。

在Python中，也有链表的实现方式，本文将介绍两种常见的链表：单链表和循环链表。

单链表

单链表的定义

单链表是最简单的一种链表，它的每个节点只包含一个指向下一个节点的指针，最后一个节点的指针指向NULL。

在Python中，我们可以通过定义一个Node类来实现单链表的节点，如下：

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

其中，data表示该节点存储的数据，next表示该节点指向的下一个节点。

单链表的用法实例

实例1：遍历单链表

下面是一个遍历单链表的示例代码，该代码会输出单链表中所有节点的数据:

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

def print_list(head):
    cur = head
    while cur is not None:
        print(cur.data)
        cur = cur.next

# 创建一个单链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 遍历单链表并输出每个节点的数据
print_list(head)

上面的代码首先创建了一个单链表，然后调用了print_list函数遍历该链表并输出每个节点的数据。

输出结果为：

1
2
3

实例2：向单链表中插入节点

下面是向单链表中插入节点的示例代码，该代码会向单链表的末尾插入一个新节点。

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

def insert_node(head, data):
    new_node = Node(data)
    cur = head
    while cur.next is not None:
        cur = cur.next
    cur.next = new_node

# 创建一个单链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 向单链表中插入新节点
insert_node(head, 4)

# 遍历单链表并输出每个节点的数据
print_list(head)

上面的代码首先创建了一个单链表，然后调用了insert_node函数向该链表末尾插入一个新节点。

输出结果为：

1
2
3
4

循环链表

循环链表的定义

循环链表和单链表类似，不同之处在于它的最后一个节点指针不为空，而是指向链表的头结点。

在Python中，我们可以通过定义一个Node类来实现循环链表的节点，如下：

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

循环链表的用法实例

实例1：遍历循环链表

下面是一个遍历循环链表的示例代码，该代码会输出循环链表中所有节点的数据。

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

def print_list(head):
    cur = head
    while cur.next != head:
        print(cur.data)
        cur = cur.next
    print(cur.data)

# 创建一个循环链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head

# 遍历循环链表并输出每个节点的数据
print_list(head)

上面的代码首先创建了一个循环链表，然后调用了print_list函数遍历该链表并输出每个节点的数据。

输出结果为：

1
2
3
1

实例2：向循环链表中插入节点

下面是向循环链表中插入节点的示例代码，该代码会向循环链表的末尾插入一个新节点。

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

def insert_node(head, data):
    new_node = Node(data)
    cur = head
    while cur.next != head:
        cur = cur.next
    cur.next = new_node
    new_node.next = head

# 创建一个循环链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head

# 向循环链表中插入新节点
insert_node(head, 4)

# 遍历循环链表并输出每个节点的数据
print_list(head)

上面的代码首先创建了一个循环链表，然后调用了insert_node函数向该链表末尾插入一个新节点。

输出结果为：

1
2
3
4
1