Python实现单向链表（Singly linked list）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python实现单向链表（Singly linked list），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3637字，纯文字阅读大概需要6分钟。

内容图文

概念介绍

在计算机科学中，链表代表着一种多个数据元素的线性集合。链表的顺序不由其在内存中的物理位置决定，而是通过每一个元素指向另一个元素来实现。链表中，一个实体对象为一个节点（Node），每个节点同时保存其数据（data）和一个引用（reference）指向另一个节点。特别需要说明的是，链表这种数据类型必须有一个元素为链首元素（空链表除外）。
由于没有物理位置上的先后顺序（在内存中随机存储），链表与其他数据结构相比，随机读写（random access）更低效。而修改或删除链表中的节点却更高效（修改节点之间的指向）。

链表节点数据结构实现

首先是实现其节点数据类型，每个节点初始化时，传入数据属性（data），而next属性为指向下一个节点（默认为空）。然后实现每个属性的get和set方法。

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

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next

链表数据结构实现

下面一一介绍链表的初始化，打印方法（print），插入，删除，增加，获取链表长度，检查是否为空等类方法。记住，链表中的每个元素为上面介绍的节点类。
初始化构造方法构造一个空的链表，其链首节点为空。

class UnorderedList:
    def __init__(self):
        self.head = None

__str__方法的实现方式是：将链表中的节点从链首开始遍历，每个节点的数据成员（data）append进一个list，最后返回str(list)。

    def __str__(self):
        print_list = []
        current = self.head
        while current is not None:
            print_list.append(current.get_data())
            current = current.get_next()
        return str(print_list)

查看是否为空时，直接检查链首节点是否为空即可。

    def is_empty(self):
        return self.head is None

size方法同样是遍历链表，并使用count变量计数。

    def size(self):
        current = self.head
        count = 0
        while current is not None:
            count += 1
            current = current.get_next()
        return count

以上是基本的查询大小，初始化，查看是否唯恐，打印等操作，不涉及到增删改查。下面来重点介绍链表的增删改查。方法有add(self, item)：item为数据元素，可以用来构造Node类实例；remove(self, item)：删除数据成员为item的指定节点；search(self, item)：查找数据成员为item的指定节点；append(self, item)：将数据成员为item的节点添加到链表尾部；index(self, item)：类比Python的List对象，给链表中的节点标记索引；insert(self, pos, item)：在指定位置插入数据成员为item的节点，pos同index方法的返回值；pop(self, index=None)：参考List的pop方法，移除指定位置的节点并返回其数据成员。下面依次实现其API方法。


add方法很简单，构造以item为数据成员的Node实例，并将其指向链首节点temp.set_next(self.head)，然后将temp节点赋值给链首节点。

    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp

remove方法的实现就有点复杂，比如有一个链表是如下图所示，我们要找到数据元素为17的节点，并将它删除，然后将剩下的链表重新连接起来。

我们需要依次遍历每个节点，直到找到数据元素为17的节点，然后将17之前的节点和17之后的节点连接起来。17之后的节点可以用current.get_next()（current为当前节点，即为17所在的节点）方法，但17之前的节点却没有方法获取，因为我们没有set_previous的方法，且此时链表是单向的，从链首直到链尾。因此，可以用一个变量（previous）保存当前链表节点的前一个节点。每次移动当前链表时，当前链表的上一个链表也随之移动。如下图。

因此，实现方法如下面的代码，首先查找指定要移除的节点。若当前节点的上一个节点为None，则当前节点为链首节点，移除链首节点时，只需将链首节点赋值为当前节点的下一个节点，self.head = current.get_next()。若当前节点的上一个节点（previous）不为空，则直接将previous的下一个节点设置为当前节点的下一个节点，改变previous的指向，则当前节点被移除，previous.set_next(current.get_next())。

    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()
        if previous is None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

内容总结

以上是互联网集市为您收集整理的Python实现单向链表（Singly linked list）全部内容，希望文章能够帮你解决Python实现单向链表（Singly linked list）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端