Как работает связанный список?

Question

У меня нет информатики. Я пытаюсь изучить кодирование самостоятельно, и я делаю это, частично, путем решения проблем на LeetCode.
В любом случае, есть проблемы с использованием связанных списков. И я уже нашел информацию о том, что связанный список должен быть смоделирован в Phython. Моя проблема в том, что я действительно не могу получить то, что стоит за связанным списком. Например, какие проблемы могут быть нацелены на эти проблемы?
И вообще, как функция связанного списка. Любая ссылка для такой информации была бы очень полезной.
Недавняя проблема, которую я смотрел на LeetCode, просит поменять местами каждые два соседних узла и вернуть свою голову. И LeetCode предлагает следующее решение, что я не могу понять, как это работает.

# Definition for singly-linked list. 
# class ListNode(object): 
#  def __init__(self, x): 
#   self.val = x 
#   self.next = None 

class Solution(object): 
    def swapPairs(self, head): 
     """ 
     :type head: ListNode 
     :rtype: ListNode 
     """ 
     pre = self 
     pre.next = head 
     while pre.next and pre.next.next: 
      a = pre.next 
      b = a.next 
      pre.next =b 
      b.next =a 
      a.next =b.next 
      pre = a 
     return self.next 

Как я уже сказал, я не понимаю этого решения. Я попытался использовать список примеров 1-> 2-> 3-> 4, который должен вернуть список 2-> 1-> 4-> 3 Все, что мне удалось, это сделать только один проход через цикл, а затем компьютер должен выйти из но тогда что происходит? Как переключаются последние два номера? Как этот код работает вообще, если в списке есть только 2 элемента, для меня это кажется невозможным.

Если бы вы могли просто направить меня в онлайн-литературу, которая объяснит что-то подобное, я был бы очень благодарен.

Спасибо.

Answer 1

Связанный список действует почти так же, как массив. Однако есть несколько основных отличий. В связанном списке в используемой памяти нет (и почти никогда) непрерывной памяти. Поэтому в массиве, если у вас есть 5 элементов, и вы смотрите на память, все 5 предметов будут рядом друг с другом (по большей части). Однако каждый «элемент» в связанном списке имеет указатель, который указывает непосредственно на следующий элемент, устраняя необходимость иметь непрерывную память. Таким образом, массив представляет собой «список» элементов, которые существуют смежно в памяти, а связанный список - это «список» объектов, каждый из которых содержит элемент и указатель на следующий элемент. Это считается единственным связанным списком, поскольку обход возможен только с одного направления. Существует также двойной связанный список, где каждый узел теперь имеет указатель на следующий узел и другой указатель на предыдущий узел, позволяющий обходить оба направления.

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

ссылка поможет вам ознакомиться с визуализируя, как работают эти связанные-листы. Я бы, вероятно, сосредоточился на вставке до и после, поскольку они должны помочь вам понять, что делает ваша петля.

Answer 2

Связанные списки не «существуют» в Python, так как язык в основном имеет итерируемый встроенный объект списка. Под капотом я уверен, что это реализовано как связанный список в C-коде (наиболее распространенная реализация Python).

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

Вы должны делать это на C, чтобы получить реальное представление о распределении памяти и указателях.

При этом, учитывая ваш пример, каждый ListNode содержит значение (например, массив), но вместо этого он имеет переменную «next», где вы храните другой объект ListNode. Этот объект, как и первый, имеет значение и переменную, в которой хранится другой объект ListNode. Это может продолжаться как можно больше объектов.

Способ, которым работает код, заключается в том, что, когда мы говорим pre.next, это относится к объекту ListNode, который хранится там, а следующий объект после этого - pre.next.next. Это работает, потому что pre.next - объект ListNode, который имеет следующую переменную.

Снова прочитайте связанные списки на C. Если вы планируете работать на языках более высокого уровня, я бы сказал, что вам действительно не нужно понимание связанных списков, так как эти структуры данных становятся «свободными» с самыми высокими уровня.