Нужна помощь в визуализации связанного списка

Question

Я пытался понять односвязный список.

Какая разница между настройкой переменных, таких как

cur=head
prev=head

, для переменных cur и prev?и

как prev.next =cur.next

влияет на связанный список?Как я могу это визуализировать?

    cur=head
    prev=head
    c=0
    while(end!=None):
        end=end.next
        c+=1
    print(c)
    mark=c-n
    if mark==0:
        head=head.next    

    while(mark>0):
        prev=cur
        cur=cur.next
        mark-=1
    prev.next=cur.next
    return head

Answer 1

Давайте рассмотрим пример списка 1->2->3->4->5 по всему этому объяснению.

Этот алгоритм удаляет n -й узел из конца связанного списка. Первая часть кода просто находит и печатает длину списка (я предполагаю, что c - это сокращение от «count»):

c=0
while(end!=None):
    end=end.next
    c+=1
print(c)

Обратите внимание, что отсутствует пропущенная переменная end, которая является узлом бегуна, используемым для обхода списка, и должна быть инициализирована как end = head. После того, как end пройдет по списку, c = 5.

---

Давайте пройдемся по логике удаления основного узла в списке образцов. Первая часть,

if mark==0:
    head=head.next    

обрабатывает крайний случай, когда нам нужно удалить заголовок списка. n должно быть равно длине списка, или в этом примере 5, что означает, что мы хотим удалить 5-ый-последний узел. Здесь просто были установлены head на следующий элемент, который удаляет все ссылки на узел 1. В какой-то момент после этой операции будет собран мусор.

before:
+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
    ^    
    |    
   head

after:
+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                ^    
                |    
               head

the resulting list:
+--------+  +--------+  +--------+  +--------+
| val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+
    ^    
    |    
   head

---

Что касается типичного случая, описанного в

while(mark>0):
    prev=cur
    cur=cur.next
    mark-=1
prev.next=cur.next

, где удаляемый элемент - не голова, давайте рассмотрим пример с n = 2. В этом случае мы хотим удалить второй или последний узел из 1->2->3->4->5 или 4.

Перед началом цикла while вот что prev, cur и head указывают на:

   head
     |
     v
+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
  ^    ^
  |    |
prev  cur

На первой итерации prev устанавливается на cur:

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
  ^    ^
  |    |
 prev cur

mark = 3

Затем cur устанавливается на следующий узел:

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
    ^            ^
    |            |
   prev         cur

mark = 3

То же самое делается еще два раза:

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
              ^    ^
              |    |
            prev  cur

mark = 2

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                 ^            ^
                 |            |
                prev         cur

mark = 2

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                          ^    ^
                          |    |
                         prev cur

mark = 1

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                            ^            ^
                            |            |
                           prev         cur

mark = 1

В этот момент цикл прерывается, поскольку mark уменьшается до 0. Вы можете видеть, что наши узлы находятся в идеальном положении, чтобы отсоединить 4 от списка с помощью prev.next=cur.next. Давайте сделаем это:

                                   +------------------+
                                   |                  |
                                   |                  v
+--------+  +--------+  +--------+ |  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 | |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: ---+  | next: --->| next: ---> [None]
+--------+  +--------+  +--------+    +--------+  +--------+
                            ^              ^ 
                            |              |
                           prev           cur

Узел, на который указывает cur со значением 4, недоступен и на него ничего не ссылается. Это будет сборщик мусора в будущем. Теперь, когда он больше не является частью списка, мы получим следующий результат после завершения кода:

+--------+  +--------+  +--------+  +--------+ 
| val: 1 |  | val: 2 |  | val: 3 |  | val: 5 |  
| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  
     ^
     |
   head

Answer 2

Думайте об элементах (узлах) как о блоках.Каждое поле имеет два свойства data и next (мост к следующему элементу).

Каждый связанныйList имеет один специальный блок, называемый заголовком, который является единственным известным вам элементом (шлюз к списку), и если вам нужны другиеэлементы списка вы следуете по цепочке мостов.

Теперь, когда вы говорите что-то linke cur = head или prev = head, вы просто копируете этот шлюз в список, чтобы вы могли перебирать список поговоря cur = cur.next и по-прежнему сохраняя исходный шлюз (head) нетронутым.

что делает cur = cur.next, это просто просматривает следующий узел cur через мост и обновляет cur, чтобы указывать непосредственно на этот следующий узелточно так же, как вы пересекаете невесту.