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

简介: 元素域 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())
复制代码


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


目录
相关文章
|
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
|
9天前
|
Python
Python 中如何循环某一特定列的所有行数据
Python 中如何循环某一特定列的所有行数据
22 2
|
23天前
|
存储 前端开发 索引
11个Python循环技巧
本文介绍了在Python中使用循环创建多个列表的方法,并提供了丰富的代码示例。内容涵盖根据固定数量、条件、数据类型、属性、索引范围、哈希值等不同条件创建列表的技巧,展示了如何灵活运用循环和列表推导式,提高代码的灵活性与可维护性,加速开发流程并提升程序性能。
|
2月前
|
搜索推荐 Python
Python基础编程:冒泡排序和选择排序的另一种while循环实现
这篇文章介绍了Python中冒泡排序和选择排序的实现,提供了使用while循环的替代方法,并展示了排序算法的运行结果。
20 2
Python基础编程:冒泡排序和选择排序的另一种while循环实现
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
7天前
|
索引 Python
Python技巧:用enumerate简化循环操作
Python技巧:用enumerate简化循环操作
11 0
|
8天前
|
Python
python如何循环某一特定列的所有行数据
python如何循环某一特定列的所有行数据
21 0
|
2月前
|
前端开发 JavaScript 数据库
python Django教程 之模板渲染、循环、条件判断、常用的标签、过滤器
python Django教程 之模板渲染、循环、条件判断、常用的标签、过滤器
|
2月前
|
C语言 Python
Python 实现循环的最快方式(for、while 等速度对比)
Python 实现循环的最快方式(for、while 等速度对比)
下一篇
无影云桌面