Cant insert item в начале связанного списка - python

Question

В настоящее время я изучаю связанные списки для класса и столкнулся с проблемами. я должен быть в состоянии вставить элемент перед указанным элементом так (Apple, банан, груша), прежде чем груша будет (Apple, банан, newItem, груша) и мне удалось это с этим кодом:

def insert_before(head,data,location): 
    current = head 
    found = False 

    while not found: 
     if current.next.data == location: 
      new_node = Node(data) 
      new_node.next = current.next 
      current.next = new_node 
      found = True 
     else: 
      current = current.next 

Но моя проблема возникла при попытке вставить элемент перед первым элементом в списке, чтобы попробовать это, я думал, что сделать это так:

if head.data == location: 
    new_node = Node(data) 
    head.next = head.next 
    new_node.next = head` 

Но это не похоже на работу. Любые руководства, которые я нашел здесь, должны были добавить элемент ПОСЛЕ первого элемента, любые советы были бы оценены.

Answer 1

В прилагаемом исходном коде использование head.next = head.next ничего не делает и не изменяет значение узла head.

Чтобы изменить значение первого узла в связанном списке, вставив новый узел раньше, необходимо обновить переменную head.

Решение 1 - назначить head в качестве возвращаемого значения функции insert_before().

переменной previous используется для изменения узла перед и когда = None, первый узел должен быть изменен.

def insert_before(head,data,location): 
    current = head 
    previous = None 
    found = False 

    while not found: 
     if (current != None): 
      if (current.data == location): 
       new_node = Node(data) 
       if (previous != None): 
        new_node.next = previous.next 
        previous.next = new_node 
       else: 
        new_node.next = head 
        head = new_node 
       found = True 
      else: 
       previous = current 
       current = current.next 
     else: 
      print('location ',location,' not found.') 
      break 
    return head 

Использование функции становится:

myhead = Node(5) 
print(myhead.data) # >> 5 
myhead = insert_before(myhead,3,5) 
print(myhead.data) # >> 3 
print(myhead.next.data) # >> 5 

Решение 2 - использовать ООП в Python, добавив атрибут head в Node классе.

ООП подход очень похож, но вместо того, чтобы хранить узел head вне функции, функция insert_before() добавляется в класс Node.

Шаг 1 - добавить в класс Node устанавливается атрибут head.

class Node(object): 
    def __init__(self, data=None, next_node=None): 
     self.data = data 
     self.next = next_node 
     self.head = self # store the first node 

Шаг 2 - использовать внутренний self.head вместо head в качестве параметра

В этом случае, когда новый узел должен быть вставлен перед первым узла, присвоение очень просто self.head = new_node.

def Insert_Before(self,data,location): 
    current = self.head 
    previous = None 
    found = False 
    print('insert ',data,' before ',location) 

    while not found: 
     if (current != None): 
      if (current.data == location): 
       new_node = Node(data) 
       if (previous != None): 
        new_node.next = previous.next 
        previous.next = new_node 
       else: 
        new_node.next = self.head 
        self.head = new_node # update the first node 
       found = True 
      else: 
       previous = current 
       current = current.next 
     else: 
      print('location ',location,' not found.') 
      break 
    return 

Использование функции становится:

myhead = Node(5) 
print(myhead.data) 
myhead.insert_before(3,5) 
print(myhead.head.data) 
print(myhead.head.next.data) 

Внимание: вместо того, чтобы использовать myhead в качестве первого узла, используйте myhead.head атрибут.