#python #linked-list
#питон #связанный список
Вопрос:
Я начинающий программист-самоучка и прохожу курс по структурам данных. Я столкнулся с проблемой при попытке вызвать метод get_position после запуска методов добавления и вставки, и я не понимаю, почему это происходит. Ссылаясь на приведенный ниже код, print(ll.get_position(5).value)
выводит «5» до вызова метода вставки, и после вставки я ожидал print(ll.get_position(6).value)
бы, что будет выведено «5», но он выводит «3». Кроме того, я могу передать любое число в качестве аргумента в методе get_position, и он все равно будет печатать «3» или «4», даже если число находится за пределами связанного списка. Я предполагаю, что цикл while метода вставки застрял? Как я могу повторно e5
подключиться к связанному списку? Почему он теряется?
Спасибо!
class Element(object): def __init__(self, value): self.value = value self.next = None class LinkedList(object): def __init__(self, head=None): self.head = head def append(self, new_element): current = self.head if self.head: while current.next: current = current.next current.next = new_element else: self.head = new_element def get_position(self, position): counter = 1 current = self.head while current and counter lt;= position: if counter == position: return current current = current.next counter = 1 def insert(self, new_element, position): counter = 1 current = self.head if position lt; 1: return None elif position == 1: new_element.next = self.head self.head = new_element while current and counter lt; position: if counter == position - 1: new_element.next = current.next current.next = new_element return current = current.next counter = 1 # Elements in list e1 = Element(1) e2 = Element(2) e3 = Element(3) e4 = Element(4) e5 = Element(5) # Linked List Setup ll = LinkedList(e1) ll.append(e2) ll.append(e3) ll.append(e4) ll.append(e5) # Should print 5 print(ll.get_position(5).value) ll.insert(e4, 3) # Expected Ouput: 1,2,4,3,4 print(ll.get_position(1).value) print(ll.get_position(2).value) print(ll.get_position(3).value) print(ll.get_position(4).value) print(ll.get_position(5).value) # Expected output: 5 (Actual Output 3) print(ll.get_position(6).value) # Expected output: Error. (Actual Output 4) print(ll.get_position(7).value)
Комментарии:
1. Вы пытаетесь вставить элемент, который уже есть в списке, поэтому его «следующий» перезаписывается.
2. @MichaelButscher Спасибо тебе! Таким образом, ссылка на существующий узел создает круговую связь между этим узлом и следующим?
3. Да, именно так.
Ответ №1:
Вы используете существующий узел e4, который указывает на узел e5. создайте новый элемент со значением 4, а затем передайте его методу insert.
new_e4 = Element(4) l1.insert(new_e4, 3)
После вставки e4 вы ожидаете, что связанный список будет выглядеть следующим образом
1 -gt; 2 -gt; 4 -gt; 3 -gt; 4 -gt; 5
Но на самом деле связанный список стал:
1 -gt; 2 -gt; 4 lt;=gt; 3 5 ( 5 is lost and 3 is pointing back to 4 and hence infinite loop)
Комментарии:
1. Ааааааа!! Большое вам спасибо за наглядное представление!! Это делает все гораздо более ясным! Огромное спасибо!
2. @CheyJax Без Проблем. Голос приветствуется 😉