AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Python 实现数据结构中的单链表，循环单链表，双链表

2022-04-22 118
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 元素域 data 用来存放具体的数据。链接域 prev 用来存放上一个节点的位置。链接域 next 用来存放下一个节点的位置。变量 p 指向链表的头节点（首节点）的位置，从 p 出发能找到表中的任意节点。

元素域 data 用来存放具体的数据。

链接域 prev 用来存放上一个节点的位置。

链接域 next 用来存放下一个节点的位置。

变量 p 指向链表的头节点（首节点）的位置，从 p 出发能找到表中的任意节点。


单链表


# -*- coding: utf-8 -*-
from __future__ import print_function
class SingleNode(object):
    """节点"""
    def __init__(self, data):
        # 标识数据域
        self.data = data
        # 标识链接域
        self.next = None
class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        # 私有属性头结点
        self.__head = node
    # is_empty() 链表是否为空
    def is_empty(self):
        return self.__head is None
    # length() 链表长度
    def length(self):
        # 数目
        count = 0
        # 当前节点
        current = self.__head
        while current is not None:
            count += 1
            # 当前节点往后移
            current = current.next
        return count
    # travel() 遍历整个链表
    def travel(self):
        # 访问的当前节点
        current = self.__head
        print('[', end=' ')
        while current is not None:
            print(current.data, end=' ')
            current = current.next
        print(']')
    # add(item) 链表头部添加元素
    def add(self, item):
        node = SingleNode(item)
        # 新节点的下一个节点为旧链表的头结点
        node.next = self.__head
        # 新链表的头结点为新节点
        self.__head = node
    # append(item) 链表尾部添加元素
    def append(self, item):
        node = SingleNode(item)
        if self.is_empty():
            # 为空节点时
            self.__head = node
        else:
            # 让指针指向最后节点
            current = self.__head
            while current.next is not None:
                current = current.next
            # 最后节点的下一个为新添加的node
            current.next = node
    # insert(index, item) 指定位置（从0开始）添加元素
    def insert(self, index, item):
        if index <= 0:
            # 在前方插入
            self.add(item)
        elif index > (self.length() - 1):
            # 在最后添加
            self.append(item)
        else:
            # 创建新节点
            node = SingleNode(item)
            # 遍历次数
            count = 0
            # 插入节点位置的上一个节点
            prev = self.__head
            # 查找到插入节点的上一个节点
            while count < (index - 1):
                count += 1
                prev = prev.next
            # 新节点的下一个节点为上一个节点的下一个节点
            node.next = prev.next
            # 上一个节点的下一个节点为新的节点
            prev.next = node
    # remove(item) 删除节点
    def remove(self, item):
        current = self.__head
        prev = None
        while current is not None:
            if current.data == item:
                # 找到要删除的节点元素
                if not prev:
                    # 没有上一个元素，比如删除头结点
                    self.__head = current.next
                else:
                    # 上一个节点的下一个节点指向当前节点的下一个节点
                    prev.next = current.next
                return  # 返回当前节点
            else:
                # 没找到，往后移
                prev = current
                current = current.next
    # search(item) 查找节点是否存在
    def search(self, item):
        # 当前节点
        current = self.__head
        while current is not None:
            if current.data == item:
                # 找到了
                return True
            else:
                current = current.next
        return False
if __name__ == '__main__':
    print('test:')
    single_link_list = SingleLinkList()
    print('--------判断是否为空-------')
    print(single_link_list.is_empty())
    print('-----------长度------------')
    print(single_link_list.length())
    single_link_list.append(2)
    single_link_list.append(3)
    single_link_list.append(5)
    print('-----------遍历------------')
    single_link_list.travel()
    single_link_list.add(1)
    single_link_list.add(0)
    single_link_list.insert(4, 4)
    single_link_list.insert(-1, -1)
    print('-----------遍历------------')
    single_link_list.travel()
    print('-----------查找------------')
    print(single_link_list.search(49))
    print('-----------删除------------')
    single_link_list.remove(-1)
    print('-----------遍历------------')
    single_link_list.travel()
    print('-----------长度------------')
    print(single_link_list.length())
复制代码


单向循环链表


# -*- coding: utf-8 -*-
from __future__ import print_function
class SingleNode(object):
    """节点"""
    def __init__(self, data):
        # 标识数据域
        self.data = data
        # 标识链接域
        self.next = None
class SingleCircleLinkList(object):
    """单向循环链表"""
    def __init__(self, node=None):
        # 私有属性头结点
        self.__head = node
        if node:
            # 不是构造空的链表
            # 头结点的下一个节点指向头结点
            node.next = node
    # is_empty() 链表是否为空
    def is_empty(self):
        return self.__head is None
    # length() 链表长度
    def length(self):
        if self.is_empty():
            # 空链表
            return 0
        count = 1  # 数目
        # 当前节点
        current = self.__head
        # 当前节点的下一个节点不是头结点则继续增加
        while current.next != self.__head:
            count += 1
            # 当前节点往后移
            current = current.next
        return count
    # travel() 遍历整个链表
    def travel(self):
        # 访问的当前节点
        if self.is_empty():
            return False
        current = self.__head
        print('[ ', end='')
        while current.next != self.__head:
            print(current.data, end=' ')
            current = current.next
        # 打印最后一个元素
        print(current.data, end=' ')
        print(']')
    # add(item) 链表头部添加元素
    def add(self, item):
        node = SingleNode(item)
        if self.is_empty():
            # 空链表
            self.__head = node
            node.next = node
        else:
            # 非空链表添加
            current = self.__head
            # 查找最后一个节点
            while current.next != self.__head:
                current = current.next
            # 新节点的下一个节点为旧链表的头结点
            node.next = self.__head
            # 新链表的头结点为新节点
            self.__head = node
            # 最后节点的下一个节点指向新节点
            current.next = node
    # append(item) 链表尾部添加元素
    def append(self, item):
        node = SingleNode(item)
        if self.is_empty():
            # 为空节点时
            self.__head = node
            node.next = node
        else:
            # 让指针指向最后节点
            current = self.__head
            while current.next != self.__head:
                current = current.next
            # 最后节点的下一个为新添加的node
            current.next = node
            # 新节点下一个节点指向头结点
            node.next = self.__head
    # insert(index, item) 指定位置（从0开始）添加元素
    def insert(self, index, item):
        if index <= 0:
            # 在前方插入
            self.add(item)
        elif index > (self.length() - 1):
            # 在最后添加
            self.append(item)
        else:
            # 创建新节点
            node = SingleNode(item)
            # 遍历次数
            count = 0
            # 插入节点位置的上一个节点
            prev = self.__head
            # 查找到插入节点的上一个节点
            while count < (index - 1):
                count += 1
                prev = prev.next
            # 新节点的下一个节点为上一个节点的下一个节点
            node.next = prev.next
            # 上一个节点的下一个节点为新的节点
            prev.next = node
    # remove(item) 删除节点
    def remove(self, item):
        if self.is_empty():
            return False
        current = self.__head
        prev = None
        while current.next != self.__head:
            if current.data == item:
                # 找到要删除的节点元素
                if current == self.__head:
                    # 删除结点,先找尾节点
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    # 头结点指向当前节点的下一个节点
                    self.__head = current.next
                    # 尾节点的下一个节点指向头结点
                    rear.next = self.__head
                else:
                    # 中间节点，上一个节点的下一个节点指向当前节点的下一个节点
                    prev.next = current.next
                return  # 返回当前节点
            else:
                # 没找到，往后移
                prev = current
                current = current.next
        # 循环结束current指向尾节点
        if current.data == item:
            if prev:
                # 如果删除最后一个节点
                prev.next = current.next
            else:
                # 删除只含有一个头结点的链表的头结点
                self.__head = None
    # search(item) 查找节点是否存在
    def search(self, item):
        # 当前节点
        if self.is_empty():
            # 空链表直接返回False
            return False
        current = self.__head
        while current.next != self.__head:
            if current.data == item:
                # 找到了
                return True
            else:
                current = current.next
        # 判断最后一个元素
        if current.data == item:
            return True
        return False
if __name__ == '__main__':
    print('test:')
    single_circle_link_list = SingleCircleLinkList()
    print('--------判断是否为空-------')
    print(single_circle_link_list.is_empty())
    print('-----------长度------------')
    print(single_circle_link_list.length())
    single_circle_link_list.append(2)
    single_circle_link_list.append(3)
    single_circle_link_list.append(5)
    #
    print('-----------遍历------------')
    single_circle_link_list.travel()
    #
    single_circle_link_list.add(1)
    single_circle_link_list.add(0)
    single_circle_link_list.insert(4, 4)
    single_circle_link_list.insert(-1, -1)
    #
    print('-----------遍历------------')
    single_circle_link_list.travel()
    #
    print('-----------查找------------')
    print(single_circle_link_list.search(4))
    #
    print('-----------删除------------')
    single_circle_link_list.remove(4)
    print('-----------遍历------------')
    single_circle_link_list.travel()
    print('-----------长度------------')
    print(single_circle_link_list.length())
复制代码


双向链表


# -*- coding: utf-8 -*-
from __future__ import print_function
class DoubleNode(object):
    """节点"""
    def __init__(self, data):
        # 标识数据域
        self.data = data
        # 标识前一个链接域
        self.prev = None
        # 标识后一个链接域
        self.next = None
class DoubleLinkList(object):
    """双链表"""
    def __init__(self, node=None):
        # 私有属性头结点
        self.__head = node
    # is_empty() 链表是否为空
    def is_empty(self):
        return self.__head is None
    # length() 链表长度
    def length(self):
        count = 0  # 数目
        # 当前节点
        current = self.__head
        while current is not None:
            count += 1
            # 当前节点往后移
            current = current.next
        return count
    # travel() 遍历整个链表
    def travel(self):
        # 访问的当前节点
        current = self.__head
        print('[ ', end='')
        while current is not None:
            print(current.data, end=' ')
            current = current.next
        print(']')
    # add(item) 链表头部添加元素
    def add(self, item):
        node = DoubleNode(item)
        # 新节点的下一个节点为旧链表的头结点
        node.next = self.__head
        # 新链表的头结点为新节点
        self.__head = node
        # 下一个节点的上一个节点指向新增的节点
        node.next.prev = node
    # append(item) 链表尾部添加元素
    def append(self, item):
        node = DoubleNode(item)
        if self.is_empty():
            # 为空节点时
            self.__head = node
        else:
            # 让指针指向最后节点
            current = self.__head
            while current.next is not None:
                current = current.next
            # 最后节点的下一个为新添加的node
            current.next = node
            # 新添加的结点上一个节点为当前节点
            node.prev = current
    # search(item) 查找节点是否存在
    def search(self, item):
        # 当前节点
        current = self.__head
        while current is not None:
            if current.data == item:
                # 找到了
                return True
            else:
                current = current.next
        return False
    # insert(index, item) 指定位置（从0开始）添加元素
    def insert(self, index, item):
        if index <= 0:
            # 在前方插入
            self.add(item)
        elif index > (self.length() - 1):
            # 在最后添加
            self.append(item)
        else:
            # 创建新节点
            node = DoubleNode(item)
            current = self.__head
            # 遍历次数
            count = 0
            # 查找到插入节点的上一个节点
            while count < index:
                count += 1
                current = current.next
            # 新节点的下一个节点指向当前节点
            node.next = current
            # 新节点的上一个节点指向当前节点的上一个节点
            node.prev = current.prev
            # 当前节点的上一个节点的下一个节点指向新节点
            current.prev.next = node
            # 当前节点的上一个节点指向新节点
            current.prev = node
    # remove(item) 删除节点
    def remove(self, item):
        current = self.__head
        while current is not None:
            if current.data == item:
                # 找到要删除的节点元素
                if current == self.__head:
                    # 头结点
                    self.__head = current.next
                    if current.next:
                        # 如果不是只剩下一个节点
                        current.next.prev = None
                else:
                    # 当前节点的上一个节点的下一个节点指向当前节点的下一个节点
                    current.prev.next = current.next
                    if current.next:
                        # 如果不是删除最后一个元素，当前节点的下一个节点的上一个节点指向当前节点的上一个节点
                        current.next.prev = current.prev
                return  # 返回当前节点
            else:
                # 没找到，往后移
                current = current.next
if __name__ == '__main__':
    print('test:')
    double_link_list = DoubleLinkList()
    print('--------判断是否为空-------')
    print(double_link_list.is_empty())
    print('-----------长度------------')
    print(double_link_list.length())
    double_link_list.append(2)
    double_link_list.append(3)
    double_link_list.append(5)
    print('-----------遍历------------')
    double_link_list.travel()
    double_link_list.add(1)
    print('-----------遍历------------')
    double_link_list.travel()
    double_link_list.add(0)
    print('-----------遍历------------')
    double_link_list.travel()
    double_link_list.insert(4, 4)
    print('-----------遍历------------')
    double_link_list.travel()
    double_link_list.insert(-1, -1)
    print('-----------遍历------------')
    double_link_list.travel()
    print('-----------查找------------')
    print(double_link_list.search(4))
    print('-----------删除------------')
    double_link_list.remove(5)
    double_link_list.remove(-1)
    print('-----------遍历------------')
    double_link_list.travel()
    print('-----------长度------------')
    print(double_link_list.length())
复制代码


需要代码的可以直接在这里下载：代码传送门


文章标签：
Python
关键词：
Python数据结构
Python循环
数据结构链表
数据结构单链表
单链表链表
alwaysbeta
目录
相关文章
职说测试
|
2月前
|
测试技术 Python
Python接口自动化测试框架（基础篇）-- 流程控制之循环语句for&while
本文介绍了Python中的循环语句，包括while和for循环的使用，range()函数的运用，以及continue、break和pass关键字的说明，同时提出了关于while循环是否能与成员运算符结合使用的思考。
职说测试
36 1
Python接口自动化测试框架（基础篇）-- 流程控制之循环语句for&while
土木林森
|
2月前
|
Python
揭秘Python编程核心：一篇文章带你深入掌握for循环与while循环的奥秘！
【8月更文挑战第21天】Python中的循环结构——for循环与while循环，是编程的基础。for循环擅长遍历序列或集合中的元素，如列表或字符串；而while循环则在未知循环次数时特别有用，基于某个条件持续执行。本文通过实例展示两种循环的应用场景，比如用for循环计算数字平方和用while循环计算阶乘。此外，还通过案例分析比较了两者在处理用户输入任务时的不同优势，强调了根据实际需求选择合适循环的重要性。
土木林森
40 0
y53t27ieobnpw
|
9天前
|
Python
Python 中如何循环某一特定列的所有行数据
Python 中如何循环某一特定列的所有行数据
y53t27ieobnpw
22 2
互联网课堂
|
23天前
|
存储 前端开发 索引
11个Python循环技巧
本文介绍了在Python中使用循环创建多个列表的方法，并提供了丰富的代码示例。内容涵盖根据固定数量、条件、数据类型、属性、索引范围、哈希值等不同条件创建列表的技巧，展示了如何灵活运用循环和列表推导式，提高代码的灵活性与可维护性，加速开发流程并提升程序性能。
互联网课堂
21 4
职说测试
|
2月前
|
搜索推荐 Python
Python基础编程：冒泡排序和选择排序的另一种while循环实现
这篇文章介绍了Python中冒泡排序和选择排序的实现，提供了使用while循环的替代方法，并展示了排序算法的运行结果。
职说测试
20 2
Python基础编程：冒泡排序和选择排序的另一种while循环实现
小徐在进步
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
19 2
gudanhero2018
|
7天前
|
索引 Python
Python技巧：用enumerate简化循环操作
Python技巧：用enumerate简化循环操作
gudanhero2018
11 0
y53t27ieobnpw
|
8天前
|
Python
python如何循环某一特定列的所有行数据
python如何循环某一特定列的所有行数据
y53t27ieobnpw
21 0
1288912195458132
|
2月前
|
前端开发 JavaScript 数据库
python Django教程 之模板渲染、循环、条件判断、常用的标签、过滤器
python Django教程 之模板渲染、循环、条件判断、常用的标签、过滤器
1288912195458132
22 1
Python大数据分析
|
2月前
|
C语言 Python
Python 实现循环的最快方式（for、while 等速度对比）
Python 实现循环的最快方式（for、while 等速度对比）
Python大数据分析
43 0

热门文章

最新文章

  • 1
    5分钟构建API接口服务 | python小知识
  • 2
    《利用Python进行数据分析·第2版》第8章 数据规整：聚合、合并和重塑
  • 3
    python中函数基本运用
  • 4
    Python 类的使用一
  • 5
    linux python eclipse 安装
  • 6
    Python安装setuptools遇到的MARKER_EXPR错误
  • 7
    python实战：分析网站的m3u8文件下载ts文件并解密
  • 8
    python实例[判断操作系统类型]
  • 9
    python rabbitmq send messages
  • 10
    笨办法学 Python · 续 练习 40：SQL 读取
  • 1
    数据结构第二课 -----线性表之单向链表
    44
  • 2
    数据结构第三课 -----线性表之双向链表
    32
  • 3
    链表练习题-2
    42
  • 4
    链表练习题-1
    26
  • 5
    高效删除链表倒数节点最优实现
    38
  • 6
    链表面试题的总结和思路分享
    28
  • 7
    数据结构奇妙旅程之顺序表和链表
    23
  • 8
    19. 删除链表的倒数第 N 个结点
    41
  • 9
    链表的插入、删除和查询—C语言
    49
  • 10
    数据结构基础：双链表结构、实现
    39

    • 相关课程

    更多
  • Python Web开发基础
  • Python爬虫实战
  • Python常用数据科学库
  • Python网络爬虫实战
  • Python完全自学手册图文教程
  • Python基础快速入门实战教程

    • 相关电子书

    更多
  • From Python Scikit-Learn to Sc
  • Data Pre-Processing in Python:
  • 双剑合璧-Python和大数据计算平台的结合

    • 相关实验场景

    更多
  • Python新手入门
  • Python入门
  • Python选择及循环结构
  • Python新手入门（Anolis OS）
  • Python网络通信程序典型应用
  • 云端Python及基本操作

    • 推荐镜像

    更多
  • python-release
  • nodejs-release
  • golang
    • 下一篇
    无影云桌面