数据结构必会|链表的思想和实现(Python)

简介: 链表的思想和实现

链表

1. 链表的概念

​ 链表的结构就像平时生活中所见到的锁链一样,是一种一环套着一环的结构。在数据结构的链表中,每一环都由“数据域”和“指针域”两部分构成。具体结构如下图所示:

在这里插入图片描述

​ 如图所示就是链表的结构,数据域用户存储当前结点的元素信息,指针域用于链接下一个结点,需要注意的是链表是无序的,也就是说我们只需要维持元素之间的相对位置,并不需要在连续的内存空间中维护这些位置信息。

2. 链表的创建

​ 链表的创建和它的原理一样,我们需要对每个结点进行初始化,结点中包含着数据域data和指针域next,有了结点之后还需要制定结点的指向函数使得结点之间能够链接起来,具体的实现方法如下:

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

    # 获取节点的值
    def getData(self):
        return self.data

    # 获取下一个节点地址
    def getNext(self):
        return self.next

    # 设置节点的值
    def setData(self, newData):
        self.data = newData

    # 设置节点指向
    def setNext(self, newnext):
        self.next = newnext
AI 代码解读

​ 测试结果如下:

# 设置结点的数据域
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)

# 设置结点指针指向的位置
temp1.next = temp2
temp2.next = temp3
temp1.setNext(temp3)

# 获取结点的值
temp2.getNext().getData()

# 输出
95
AI 代码解读

3. 链表功能的实现

​ 对于链表来说,除了创建链表之外,我们还需要创建一个类来实现链表的功能。

  • printlink:实现链表的打印;
  • length:实现链表长度的计算;
  • search:实现链表中元素的查找;
  • remove:实现链表中元素的移除。

​ 具体的实现方式如下:

class UnorderedList:
    # 没有元素构建一个空列表
    def __init__(self):
        self.head = None

    # 判断列表是否为空
    def isEmpty(self):
        return self.head == None

    # 添加节点
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    # 遍历链表
    def printlink(self):
        if self.head == None:
            print("该链表为空链表!")
        p = self.head
        while p != None:
            print(p.getData(), end="->")
            p = p.getNext()

    # 链表的长度
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    # 查找元素
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    # 移除元素
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())
AI 代码解读

​ 测试结果如下:

# 设置结点的数据域
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)

# 设置结点指针指向的位置
linklist = UnorderedList()
linklist.head = temp1
temp1.next = temp2
temp2.next = temp3

# 使用功能类中的add进行元素的添加
linklist.add(9)
# 打印链表长度
print(linklist.length())

# 输出
4
AI 代码解读

​ 使用循环构造链表:

link_list = UnorderedList()
for i in range(5):
    link_list.add(i)
node = link_list.head
node.getData()

# 输出
4
AI 代码解读
相关文章
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
21天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
82 25
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
134 66
Python 实现反转、合并链表有啥用?
大家好,我是V哥。本文介绍Python实现反转链表和合并链表的应用场景及代码实现。反转链表适用于时间序列数据展示、回文链表判断等;合并链表则用于大规模数据排序、数据库查询结果集合并等。通过迭代和递归方法实现反转链表,以及合并两个或多个有序链表的算法,帮助开发者解决实际问题。关注V哥,了解更多实用编程技巧。 先赞再看后评论,腰缠万贯财进门。
Python 中常见的数据结构
这些数据结构各有特点和适用场景,在不同的编程任务中发挥着重要作用。开发者需要根据具体需求选择合适的数据结构,以提高程序的效率和性能
153 59
Python编程数据结构的深入理解
深入理解 Python 中的数据结构是提高编程能力的重要途径。通过合理选择和使用数据结构,可以提高程序的效率和质量
174 59
Python 中的数据结构与其他编程语言数据结构的区别
不同编程语言都有其设计理念和应用场景,开发者需要根据具体需求和语言特点来选择合适的数据结构
121 55
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
44 5
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
76 20
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
114 33

热门文章

最新文章