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

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

2022-04-22 125
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 元素域 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
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
62 4
三三是该溜子
|
5天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
16 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
1月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
56 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
108 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
33 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
40 2
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
50 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
73 0
白子寰
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
白子寰
27 0
星霜旅人
|
2月前
|
存储
数据结构（单链表）
数据结构（单链表）
星霜旅人
23 0

热门文章

最新文章

  • 1
    【C语言】深入浅出：C语言链表的全面解析
  • 2
    使用Python实现智能食品库存管理的深度学习模型
  • 3
    Python实现常用办公文件格式转换
  • 4
    猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
  • 5
    pyenv 管理多个 Python 版本(1)
  • 6
    Python的标准库
  • 7
    利用Python内置函数实现的冒泡排序算法
  • 8
    使用Python实现智能食品消费习惯分析的深度学习模型
  • 9
    使用Python实现深度学习模型的分布式训练
  • 10
    在 Python 中，如何将日期时间类型转换为字符串？
  • 1
    【Python进阶（七）】——Series数据结构
    185
  • 2
    Redis数据结构精讲：选择与应用实战指南
    1334
  • 3
    深入浅出数据结构之布隆过滤器
    72
  • 4
    数据结构/C++：位图 & 布隆过滤器
    48
  • 5
    数据结构/C++：哈希表
    84
  • 6
    数据结构/C++：红黑树
    46
  • 7
    数据结构/C++：AVL树
    49
  • 8
    栈的基本应用
    63
  • 9
    栈与队列理解
    48
  • 10
    数据结构/C++：二叉搜索树
    53

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • Python语言基础 - 列表、元组、字典、集合
  • Python语言基础 - 函数、面向对象、异常处理
  • 【Python入门】Python数据处理编程基础
  • 【科技少年】Python基础语法
  • Python语言基础 - 语法入门

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • Python第五讲——关于爬虫如何做js逆向的思路

    • 相关实验场景

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

    • 推荐镜像

    更多
  • python-release
  • nodejs-release
  • deepin-cd
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)