算法系列之链表基本原理---超市购物队列的故事

想了个生动的方式来解释链表基本原理

想象你在一个超市排队结账,每个人都是一个节点,每个人手里拿着一张票据(数据),而每个人的背上都贴着一个指示牌,指示牌指向下一个排队的人。这就是一个单向链表

1. 什么是链表?

在现实中,链表就像排队的人,每个人知道自己后面是谁,但不知道前面是谁。这个链表的特点是,每个人(节点)只知道下一个人(节点)的信息,而不知道前一个人。

2. 链表的类型

单向链表

  • 每个人(节点)只知道下一个人(节点)的信息。

双向链表

  • 每个人(节点)不仅知道下一个人(节点),还知道前一个人(节点)的信息,就像每个人都可以和前后两个人聊天。

循环链表

  • 最后一个人(节点)知道第一个人(节点),这样队伍就首尾相连,形成一个圈。

3. 链表的基本操作

3.1 创建链表

我们先创建一个空的队伍:

class Node:
    def __init__(self, data):
        self.data = data  # 票据(数据)
        self.next = None  # 指向下一个人的指示牌(指针)

class LinkedList:
    def __init__(self):
        self.head = None  # 队伍的第一个人(头节点)
3.2 在队伍尾部加入新的人

每当有新人加入队伍,我们需要找到队伍的末尾,然后把新人加进去:

def append(self, data):
    new_node = Node(data)  # 新人拿着票据
    if not self.head:  # 如果队伍是空的
        self.head = new_node  # 新人成为第一个人
        return
    last = self.head
    while last.next:  # 找到队伍的末尾
        last = last.next
    last.next = new_node  # 把新人加到队伍的末尾

 

3.3 在队伍头部插入新的人

如果你是VIP,你可以插队到队伍的最前面:

def insert_at_head(self, data):
    new_node = Node(data)  # 新人拿着票据
    new_node.next = self.head  # 新人指向原来的第一个人
    self.head = new_node  # 新人成为第一个人

 

3.4 删除特定的人

假设有人决定不排队了,我们需要把他从队伍中移除:

def delete_node(self, key):
    temp = self.head

    if temp is not None:
        if temp.data == key:
            self.head = temp.next  # 第一个人离开队伍
            temp = None
            return

    while temp is not None:
        if temp.data == key:  # 找到想要离开队伍的人
            break
        prev = temp
        temp = temp.next

    if temp == None:
        return

    prev.next = temp.next  # 把他从队伍中移除
    temp = None

 

3.5 打印队伍中的所有人

为了查看队伍中的所有人,我们从第一个人开始,依次看每个人的票据:

def print_list(self):
    temp = self.head
    while temp:
        print(temp.data, end=" -> ")  # 打印每个人的票据
        temp = temp.next
    print("None")

 

4. 链表的应用

链表在很多地方都有应用,比如:

  • 实现栈和队列:像超市排队一样,可以用链表实现先进先出的队列和后进先出的栈。
  • 内存管理:操作系统用链表来管理空闲内存块,就像管理空闲的停车位。
  • 图的表示:用链表来存储图的邻接表,每个节点都知道自己的邻居。

5. 链表的优缺点

优点

  • 动态大小:队伍可以根据需要动态调整长度。
  • 高效插入/删除:在队伍中插入或删除某个人非常高效。

缺点

  • 随机访问效率低:要找到某个人需要从第一个人开始一个个找下去。
  • 额外内存开销:每个人需要额外的空间来存储指示牌(指针)。

 

热门相关:天龙邪尊   逼婚首席:影后前妻很抢手   宠妻入骨:神秘老公有点坏   蓝白社   来自地狱的男人