pop 方法 LinkedList Class

Question

我已经实现了 LinkedList class：我需要实现不带参数的 pop()。该方法删除并 returns 链表末尾的项目。如果列表为空，它 returns None 什么都不做。

class LinkedList:
        def __init__(self):
            self.head = None
            self.count = 0
    
        def is_empty(self):
            return self.count == 0
    
        def size(self):
            return self.count
    
        def add(self, item):
            new_node = Node(item)
            new_node.set_next(self.head)
            self.head = new_node
            self.count += 1
    
        def search(self, item):
            current = self.head 
            while current != None:
                if current.get_data() == item:
                    return True
                else:
                    current = current.get_next()
            return False
    
        def remove(self, item):
            found = False
            current = self.head
            previous = None
            while current != None and not found:
                if current.get_data() == item:
                    found = True
                else:
                    previous = current
                    current = current.get_next()
            if found:
                if previous == None:
                    self.head = current.get_next()
                else:
                    previous.set_next(current.get_next())
                self.count -= 1
            else:
                raise ValueError("remove(" + str(item) + "). " + str(item) + " is not in list")
                
        def clear(self):
            self.head = None
            self.count = 0
                
        def __str__(self):
            temp = self.head
            if(temp != None):
                output ="Head"
                while (temp != None):
                    output = output+" --> "+str(temp.data)
                    temp = temp.next
                return output
            else:
                return "Head --> None"
                
        def append(self, item):
            new_node = Node(item)
    
            if self.head is None:
                self.head = new_node
                return
            last = self.head
            while(last.next):
                last = last.next
    
            last.next = new_node
            
        def pop(self):   #Problem here
            if self.head is None:
                return None
            else:
                popnode = self.head
                self.head = self.head.next
                popnode.next = None
                return popnode.data

测试：

a_list = LinkedList()
a_list.add(1)
a_list.add(2)
a_list.add(3)
print(a_list)
print("Removed item:",a_list.pop())
print("Removed item:",a_list.pop())
print(a_list)

预期输出：

Head --> 3 --> 2 --> 1
Removed item: 1
Removed item: 2
Head --> 3

记录输出：

Head --> 3 --> 2 --> 1
Removed item: 3
Removed item: 2
Head --> 1

测试：

a_list = LinkedList()
a_list.append(1)
a_list.append(2)
a_list.append(3)
print(a_list)
print("Removed item:",a_list.pop())
print("Removed item:",a_list.pop())
print(a_list)

预期输出：

Head --> 1 --> 2 --> 3
Removed item: 3
Removed item: 2
Head --> 1

记录输出：

Head --> 1 --> 2 --> 3
Removed item: 1
Removed item: 2
Head --> 3

Answer 1

这是一个简化的 pop() 方法，可以满足您的要求 -

def pop(self):   #Problem here
    # Empty LinkedList
    if self.head is None:
        return None

    # There is a single node in the LinkedList = head, read data and delete it
    if self.head.next is None:
        data = self.head.data
        self.head = None
        return data
    
    # there are 2 or more nodes in the LinkedList
    secondlast = self.head
    while (secondlast.next.next):
        secondlast = secondlast.next
    # found the second last node
    # read the data of the last node and then delete it, by setting secondlast.next = None
    data = secondlast.next.data
    secondlast.next = None
    return data

另一种方法使用临时虚拟节点来简化 LinkedList-

中只有一个节点的情况

def pop(self):   #Problem here
    # Empty linkedlist
    if self.head is None:
        return None
    # create a dummy secondlast node
    secondlast = Node(-1)
    secondlast.next = self.head
    while (secondlast.next.next):
        secondlast = secondlast.next
    data = secondlast.next.data
    secondlast.next = None
    return data

在您的 LinkedList 中，append() 和 pop() 方法都是 O(n)，因为您需要遍历整个 LinkedList 来执行这些操作。考虑向 LinkedList 添加一个新的属性 self.tail（或 self.secondlast），它跟踪 LinkedList 中的最后一个节点。这将有助于简化代码并使 append() 和 pop() 操作 O(1)

Answer 2

当变成None时就跟踪popnode.next，同时存储上一条，当popnode.next变成None时，就把上一条的下一条None，以及 popnode.next 的 return 数据：

def pop(self):  # Problem here
    if self.head is None:
        return None
    elif self.head.next == None:
        d = self.head.data
        self.head = None
        return d
    else:
        popnode = self.head
        prev = popnode
        while popnode.next:
            prev = popnode
            popnode = popnode.next
        prev.next = None
        return popnode.data

输出：

a_list = LinkedList()
a_list.add(1)
a_list.add(2)
a_list.add(3)
print(a_list)
print("Removed item:", a_list.pop())
print("Removed item:", a_list.pop())
print("Removed item:", a_list.pop())
print(a_list)

将是：

Head --> 3--> 2--> 1
Removed item: 1
Removed item: 2
Removed item: 3
Head  None

pop 方法 LinkedList Class

pop method LinkedList Class

python

linked-list

nodes