Python实现单向链表(上):小白写法的15种增删改查操作

举报
泽宇-Li 发表于 2020/10/27 16:36:16 2020/10/27
【摘要】 大体思路需要写两个类:Node类:用于创建结点,并将结点以(人类)能看懂的字符串形式输出,而不是显示内存地址LinkedList类:用于将各结点连成链表,并实现对链表进行操作的一些方法代码创建Node类:class Node: def __init__(self, data, next=None): self.data = data # 数据,当前结点的元素 ...

大体思路

需要写两个类:

  1. Node类:用于创建结点,并将结点以(人类)能看懂的字符串形式输出,而不是显示内存地址

  2. LinkedList类:用于将各结点连成链表,并实现对链表进行操作的一些方法

代码

创建Node类:

class Node:
    def __init__(self, data, next=None):
        self.data = data # 数据,当前结点的元素
        self.next = None # 指针,指向下一个结点

    def __repr__(self): # 把结点表示为一个字符串
        return "NodeValue({})".format(self.data)1234567

调用测试:

n = Node(1)print(n) # 因为写了__repr__方法,所以输出的是Node(1),而不是内存地址12

创建LinkedList类:

准备工作:初始化方法 & 打印字符串方法
想要达到的输出效果类似于:
NodeValue(1) --> NodeValue(3) --> NodeValue(4) --> END

class LinkedList:
    def __init__(self):
        self.head = None # 初始化头结点

    ## 打印链表
    def __repr__(self):
        cursor = self.head
        string_repr = ""
        while cursor:
            string_repr += f"{cursor} --> "
            cursor = cursor.next
        return string_repr + "END"123456789101112
「查」:方法

1. is_empty() 判断链表是否为空

    def is_empty(self):
        return self.head == None12

2. length() 返回链表长度

    def length(self):
        if self.head is None:
            return 0
        cursor = self.head
        count = 0
        while cursor:
            count += 1
            cursor = cursor.next
        return count123456789

3. exist(data) 判断结点是否存在

    def exist(self, data):
        """
        :return: True or False
        :rtype: Boolean
        """
        cursor = self.head        while cursor:
            if cursor.data == data:
                return True
            else:
                cursor = cursor.next
        return False123456789101112

4. travel() 遍历整个链表

    def travel(self):
        if self.head is None:
            return None
        cursor = self.head        while cursor:
            print(cursor)
            cursor = cursor.next1234567

5. getitem(index) 根据索引,得到链表中该位置的值

    def getitem(self, index):
        current = self.head        if current is None:
            raise IndexError("This is an empty linked list.")
        for i in range(1, index):
            # 目标超过链表范围
            if current.next is None:
                raise  IndexError("Index out of range")
            current = current.next
        return current12345678910

6. search(data) 返回该结点出现的左数第一个的位置,不存在返回-1

    def search(self, data):
        if self.exist(data) == False:
            return -1
        else:
            cursor = self.head
            count = 0
            while cursor:
                count += 1
                if cursor.data == data:
                    return count                else:
                    cursor = cursor.next123456789101112
「增」:方法

7. insert_head(data) 在链表头部添加元素

    def insert_head(self, data):
        new_node = Node(data)  # 创建一个新结点
        if self.head: # 如果已存在头部结点
            # 让新创建的结点的next指向原本的头结点
            # 也就是说,新结点成为了原本的头结点的上一个结点
            new_node.next = self.head
        self.head = new_node # 重置头结点1234567

8. append(data) 在链表尾部添加元素

    def append(self, data):
        if self.head is None:
            # 如果链表目前为空,则在头结点添加该元素
            self.insert_head(data)
        else:
            cursor = self.head            while cursor.next: # 遍历链表
                cursor = cursor.next
                # 创建一个新结点添加到链表尾部
            cursor.next = Node(data)12345678910

9. insert(pos, data) 在链表中的指定位置添加元素

    def insert(self, pos, data):
        """
        :param pos: 要插入结点的位置,从0开始。
                    pos > 0,代表是从左开始数的位置
                    pos = 0,代表在头部添加
                    pos < 0,代表是从右开始数的位置,倒数从-1开始
                    也就是说 链表长度 + 倒数下标 = 正数下标
        :type pos: int
        :param data: 要插入的结点值
        :type data: int
        """
        if pos > 0:
            if self.head is None:
                # 如果链表目前为空,则在头结点添加该元素
                self.insert_head(data)
            else:
                new_node = Node(data)  # 创建一个新结点

                # 通过循环,得到新结点的上一个结点
                pre = self.head
                count = 0
                while count < (pos-1):
                    count += 1
                    pre = pre.next
                # 让新结点指向原本该位置的结点
                new_node.next = pre.next
                # 让上一个结点指向新结点
                pre.next = new_node        elif pos == 0:
            self.insert_head(data)
        elif pos < 0:
            if self.head is None:
                # 如果链表目前为空,则在头结点添加该元素
                self.insert_head(data)
            else:
                new_node = Node(data)
                # 通过循环,得到新结点正数顺序的上一个结点
                leftpos = self.length() + pos
                pre = self.head
                count = 0
                while count < (leftpos - 1):
                    count += 1
                    pre = pre.next
                # 让新结点指向原本该位置的结点
                new_node.next = pre.next
                # 让上一个结点指向新结点
                pre.next = new_node1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
「删」:方法

10. delete_head() 删除头结点

    def delete_head(self):
        temp = self.head        if self.head:
            self.head = temp.next
            temp.next = None12345

11. delete_tail() 删除尾结点

    cursor = self.head        if self.head:
            if self.head.next is None:
                self.head = None
            else:
                while cursor.next.next:
                    cursor = cursor.next
                cursor.next, cursor = None, cursor.next
        elif self.head == None:
            return "This is an empty linked list."12345678910

12. remove(data) 删除结点,若存在值相等的结点,仅删除左起第一个

    def remove(self, data):
        """
        :return: 返回删除结点后的链表;若传入的数据在链表中不存在,则返回原链表
        """
        if self.exist(data) == False:
            return self        else:
            pre = self.head
            cursor = pre.next
            count = 0
            while cursor:
                if cursor.data == data:
                    # 删除,也就是让该结点的上一结点直接连到该结点的下一结点
                    pre.next = cursor.next
                    cursor.next = None
                    return self                else:
                    pre = pre.next
                    cursor = cursor.next12345678910111213141516171819

13. removeall(data) 删除结点,若存在值相等的结点,删除所有

    def removeall(self, data):
        """
        :return: 返回删除结点后的链表;若传入的数据在链表中不存在,则返回原链表
        """
        while self.exist(data):
            self.remove(data)
        return self1234567
「改」:方法

14. setitem(index, data) 根据索引,为链表中该位置的值重新赋值

    def setitem(self, index, data):
        current = self.head        if current is None:
            raise IndexError("This is an empty linked list.")
        for i in range(1, index):
            # 目标超过链表范围
            if current.next is None:
                raise  IndexError("Index out of range")
            current = current.next
        current.data = data12345678910

其他方法

15. linklist(object) 传入对象,一次性将序列中的所有元素构建成一个链表

    def linklist(self, object):
        self.head = Node(object[0])
        temp = self.head        for i in object[1:]:
            node = Node(i)
            # 将上一个结点指向下一个结点
            temp.next = node
            temp = temp.next



【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200