小工具知识网

当前位置: 首页 > 行业知识 > 数据结构:链表(Python语言实现)

行业知识

数据结构:链表(Python语言实现)

2026-11-21 15:48:43 来源:互联网转载

��表分为单链表、双链表、循环单链表和循环双链表。

()

本文以单链表为例,用python创建一个单链表数据结构,同时定义链表节点的增加、删除、查询和打印操作。

一、创建节点类

创建一个名为Node的节点类,节点类里面包含2个属性和1个方法。

()
  1. 节点类的属性

分别为data数据域属性和next指针域属性。

  1. 节点类的方法

has_value()方法,判断节点的值是否等于某个值。

# 创建节点类class Node:    def __init__(self, data):        self.data = data        self.next = None        return    def has_value(self, value):        if self.data == value:            return True        else:            return False

二、创建单链表类

创建一个名为singlelink的单链表类,其中包含3个属性和7个方法。

  1. 单链表类的属性

头结点head、尾节点tail和链表长度length。

  1. 单链表类的方法

(1)__init__():初始化方法。

(2)isempty():判断链表是否为空。

(3)add_node():在链表尾部添加一个节点。

(4)insert_node():在链表中的某个位置(从1开始)插入一个节点。

(5)delete_node_byid():通过位置(从1开始),在链表中删除对应的节点。

(6)find_node():查找某个值在链表中所在的位置(从1开始)。

(7)print_link():按顺序打印链表的值。

注意:insert_node()、delete_node_byid()和find_node()方法中的位置指从1开始计数,并非按python中列表索引值从0开始。

(一)__init__()

# 创建一个单链表类class singlelink:    # 初始化方法    def __init__(self):        self.head = None        self.tail = None        self.length = 0        return

(二)isempty()

    # 判断链表是否为空    def isempty(self):        if self.length == 0:            return True        else:            return False

(三)add_node()

    # 向链表尾部添加一个节点    def add_node(self, item):        if not isinstance(item, Node):  # 判断item是否是Node类型            item = Node(item)   # 创建新节点        if self.head is None:            self.head = item            self.tail = item        else:            self.tail.next = item            self.tail = item        self.length += 1        return

(四)insert_node()

# 在链表中插入一个结点    def insert_node(self, index, data):        if self.isempty():            print('this link is empty')            return        if index  self.length + 1:    # 插入序号不能大于长度或小于0            print('error: out of index')            return        item = Node(data)        if index == 1:            item.next = self.head            self.head = item            self.length += 1            return        j = 1        node = self.head        prev = self.head        while node.next and j   

(五)delete_node_byid()

# 通过索引,在链表中删除节点    def delete_node_byid(self, item_id):        if self.isempty():            print('this link is empty, Unable to delete')            return        if item_id  self.length:            print('error:out of index,Unable to delete')        id = 1        current_node = self.head        previous_node = None        while current_node is not None:            if id == item_id:                if previous_node is not None:                    previous_node.next = current_node.next                    return                else:                    self.head = current_node.next   # 删除头结点的情况                    return            previous_node = current_node            current_node = current_node.next            id += 1        self.length -= 1        return

(六)find_node()

# 通过数值,在链表中找到节点(返回该节点的所有位置)    def find_node(self, value):        current_node = self.head        node_id = 1        result = []        while current_node is not None:            if current_node.has_value(value):                result.append(node_id)            current_node = current_node.next            node_id += 1        return result

(七)print_link()

    def print_link(self):        currrent_node = self.head        while currrent_node is not None:            print(currrent_node.data)            currrent_node = currrent_node.next        return

创建单链表,并进行增加、删除、查询等操作

# 创建三个节点Node1 = Node('a')Node2 = Node('b')Node3 = Node('c')# 定义一个空链表link = singlelink()# 判断是否是空链表print(link.isempty())# 尾部添加结点for node in [Node1, Node2, Node3]:    link.add_node(node)# 在链表中插入位置link.insert_node(2, 'e')link.insert_node(4, 'f')link.insert_node(4, 'f')link.insert_node(8, 'h') # 无法插入# 打印链表link.print_link()print('*****************')# 删除元素link.delete_node_byid(2)link.print_link()print('*****************')# 查找元素node_ids = link.find_node('f') # 查询元素5的位置if len(node_ids) == 0:    print('链表中无此元素')else:    print(node_ids)

上一篇:金蝶云专业版怎么启动服务器

下一篇:红羽扇植物养护秘籍,打造绿意盎然家居的秘诀!