03-Question 3 (15 points)

AI悦创原创大约 4 分钟...约 1130 字

Suppose you implemented a basic (singly) LinkedList class in Python. This Linked ist class contains three attributes, ie., size, head, and tail. This LinkedList can be used to manipulate an unordered list of numeric values, with function insert(self, value, index), remove (self, value, index), traverse (self), is_empty(self), and size (self). The traverse function could print a sequence of values by visiting each node in the Linked ist from head to tail.

假设你用Python实现了一个基本的LinkedList类。这个Linked ist类包含三个属性，即。大小，头和尾巴。这个LinkedList可以用来操作数值的无序列表，使用函数insert(self, value, index)， remove (self, value, index)， traverse (self)， is_empty(self)和size (self)。traverse函数可以通过从头到尾访问Linked ist中的每个节点来打印值序列。

Each node in the LinkedList is a Node object containing two attributes, i.e., value and next.

LinkedList中的每个节点都是一个node对象，包含两个属性，即value和next。

Based on the above information, answer the following sub-questions.

根据以上信息，回答以下子问题。

3.1 (10 points) Modify the given LinkedList class in the most efficient way so that it can hold a sequence of ordered numeric values. You should at least implement a new insert (self, value) function, which inserts a new Node with the given value and maintains an ordered list of values in ascending order in the LinkedList.

(10分)以最有效的方式修改给定的LinkedList类，以便它可以保存有序的数值序列。您至少应该实现一个新的insert (self, value)函数，它用给定的值插入一个新的Node，并在LinkedList中按升序维护一个有序的值列表。

For instance, if I execute the following lines of code:

例如，如果我执行以下几行代码:

test list = LinkedList()
test_list.insert(1)
test_ list.traverse()
test_list.insert(5)
test_list.traverse()
test list.insert(3)
test list.traverse()

The terminal will print out three lines:

终端将打印出三行:

1,5

1,3,5

答案

1.0

# -*- coding: utf-8 -*-
# @Time    : 2023/3/7 09:58
# @Author  : AI悦创
# @FileName: answer.py
# @Software: PyCharm
# @Blog    ：https://bornforthis.cn/
class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None


class LinkedList:
    def __init__(self):
        self.size = 0
        self.head = None
        self.tail = None

    def insert(self, value):
        new_node = Node(value)
        if self.head is None:
            # Case when list is empty
            self.head = new_node
            self.tail = new_node
        elif self.head.value > value:
            # Case when new node should be the new head
            new_node.next = self.head
            self.head = new_node
        elif self.tail.value <= value:
            # Case when new node should be the new tail
            self.tail.next = new_node
            self.tail = new_node
        else:
            # General case when new node should be inserted in the middle
            current = self.head
            while current.next is not None and current.next.value < value:
                current = current.next
            new_node.next = current.next
            current.next = new_node
        self.size += 1

    def remove(self, value):
        current = self.head
        previous = None
        while current is not None:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                if current.next is None:
                    self.tail = previous
                self.size -= 1
                return True
            previous = current
            current = current.next
        return False

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.value, end=" ")
            current = current.next
        print()

    def is_empty(self):
        return self.size == 0

    def size(self):
        return self.size


test_list = LinkedList()
test_list.insert(1)
test_list.traverse()  # 1
test_list.insert(5)
test_list.traverse()  # 1 5
test_list.insert(3)
test_list.traverse()  # 1 3 5

2.0

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

class LinkedList:
    def __init__(self):
        self.size = 0
        self.head = None
        self.tail = None

    def insert(self, value):
        new_node = Node(value)
        if self.head is None:
            # 当列表为空时，新节点变为头和尾
            self.head = new_node
            self.tail = new_node
        elif self.head.value > value:
            # 当新节点的值小于当前头的值时，将新节点作为新头
            new_node.next = self.head
            self.head = new_node
        elif self.tail.value <= value:
            # 当新节点的值大于或等于当前尾的值时，将新节点作为新尾
            self.tail.next = new_node
            self.tail = new_node
        else:
            # 一般情况，将新节点插入到中间
            current = self.head
            while current.next is not None and current.next.value < value:
                current = current.next
            new_node.next = current.next
            current.next = new_node
        self.size += 1

    def remove(self, value):
        current = self.head
        previous = None
        while current is not None:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                if current.next is None:
                    self.tail = previous
                self.size -= 1
                return True
            previous = current
            current = current.next
        return False

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.value, end=" ")
            current = current.next
        print()

    def is_empty(self):
        return self.size == 0

    def size(self):
        return self.size

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh