时间戳

首页 > 解决方案 > 无法在 LinkedList 的开头一次又一次地插入相同的元素

python - 无法在 LinkedList 的开头一次又一次地插入相同的元素

问题描述

代码：

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

def create_list():
    seq = input("Enter the sequence of integers: ").split()
    int_seq = [int(i) for i in seq]
    head = None
    tail = None
    for number in int_seq:
        if number == -1:
            break
        node = Node(number)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node

    return head, tail

def count_no_of_elements(head):
    if head is None:
        return 0
    curr = head
    counter = 0
    while curr:
        curr = curr.next
        counter += 1
    return counter

def insert_element(head, tail, elem, posn):
    no_of_elem = count_no_of_elements(head)
    if posn <= 0 or posn > no_of_elem + 1:
        return -1, -1

    if posn == 1:       # Insert at the beginning
        element = Node(elem)
        element.next = head
        head = element
        return head, tail

    else:           
        counter = 1
        curr = head
        while counter != (posn - 1):
            curr = curr.next
            counter += 1
        element = Node(elem)
        if curr.next is not None: # Insert in between
            element.next = curr.next 
            curr.next = element
        else:                      # Insert at the end
            curr.next = element
            tail = element
        return head, tail

def traverse_list(head):
    if head is None:
        return -1
    curr = head
    while curr:
        print(curr.data)
        curr = curr.next
    return head

使用序列创建列表后：1 3 5 7 9 2 4 8 6 0 -1，

我试图0在开头连续插入 3 次。

驱动代码：

list_head, list_tail = create_list()
# 1 3 5 7 9 2 4 8 6 0 -1

ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
if ins_hd != -1:
    trav = count_no_of_elements(ins_hd)
    print(trav)
    print('\n\n')
else:
    print(ins_hd)

if ins_hd != 1:
    trav = traverse_list(ins_hd)
print(in_tl.data)

插入代码第二次起不起作用。

实际输出：

11



0
1
3
5
7
9
2
4
8
6
0
0

我在这里想念什么？

标签： pythonpython-3.xlinked-list

解决方案

当您从函数中获取返回值时，您必须停止使用 head 和 tail 的旧值。您需要继续使用从插入中返回的新值。目前你不这样做：

ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
ins_hd, in_tl = insert_element(list_head, list_tail, 0, 1)
# ...

将其更改为使用相同的变量：

list_head, list_tail = insert_element(list_head, list_tail, 0, 1)
list_head, list_tail = insert_element(list_head, list_tail, 0, 1)
# ...

在这些语句之后的代码中也使用list_head, 和list_tail.

使其更加面向对象

我还建议为您的链表创建一个类，以便它保持其头部和尾部的变化值作为其状态的一部分。这使得代码更简洁，尤其是当您开始在同一代码中使用多个链表时：

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

class LinkedList:
    def __init__(self, int_seq=[]):
        self.head = None
        self.tail = None
        for number in int_seq:
            node = Node(number)
            if self.head is None:
                self.head = node
            else:
                self.tail.next = node
            self.tail = node

    def size(self):
        if self.head is None:
            return 0
        curr = self.head
        count = 0
        while curr:
            curr = curr.next
            count += 1
        return count

    def insert(self, elem, posn=1):
        if posn == 1:    # Insert before head
            node = Node(elem)
            node.next = self.head
            self.head = node
            return
        curr = self.head
        while curr.next is not None and posn > 2:
            curr = curr.next
            posn -= 1
        if posn != 2:
            raise ValueError("Invalid position")
        node = Node(elem)
        node.next = curr.next
        curr.next = node
        if curr == self.tail: # Insert after tail
            self.tail = node
        else:                 # Insert in between
            curr.next = node

    def values(self):
        curr = self.head
        while curr is not None:
            yield curr.data
            curr = curr.next

seq = input("Enter the sequence of integers: ").split()
llist = LinkedList([int(i) for i in seq])
# 1 3 5 7 9 2 4 8 6 0

llist.insert(0, 1)
print("size: {}".format(llist.size()))
print("values: {}".format(list(llist.values())))
llist.insert(10, 12)
print("size: {}".format(llist.size()))
print("values: {}".format(list(llist.values())))
llist.insert(11, 5)
print("size: {}".format(llist.size()))
print("values: {}".format(list(llist.values())))

在上面的代码中，我保留了相同的概念posn，所以在位置 1 插入意味着插入将发生在头节点之前。许多人会发现将其实际定义为位置 0 更自然，但我保持原样。

我没有看到以不同方式处理输入值 -1 的意义，因为您可以读取和插入所有值，因此我删除了该逻辑。

当给定的插入位置超出范围时，我认为引发异常更合适。

此外，计算元素的数量以确定位置是否在范围内是多余的，因为您需要以任何方式遍历列表。因此，您可以确定该迭代中位置的有效性。

推荐阅读