C # Распределение памяти и реализация связанного списка

Question

У меня есть несколько вопросов о том, как именно C # реализует первый класс класса связанного списка:

public class Node {  
    int data;  
    Node next;   
} 

похоже, что это не связанный список, это большой объект с рекурсивным тем же классом внутри

мой второй вопрос более конкретен, для простого алгоритма обратного связанного списка, как показано ниже:

 public void ReverseList(ref ListNode head){
    if(head ==null || head.next == null) return head;
    ListNode cur = head;
    ListNode prev = null;
    ListNode next = head.next;
    while (cur != null){
        ListNode nextNode = head.next;
        cur.next= prev;
        prev=cur;
        cur=nextNode;
    }
    head = prev ;
} 

не cur = head означает "cur" копировать ВСЕ элементы связанного списка?И гораздо сложнее подумать, что происходит в алгоритме.

Answer 1

Связанный список использует ссылки для создания структуры списка.

Ключевым моментом является понимание различия между value и reference типами в C #.Типы значений, такие как int, bool или struct, действительно являются значениями, которые хранятся в стеке, и когда вы присваиваете их, вы фактически копируете данные из одного местоположения в другое.Типы ссылок classes в C #, и различие в том, что они просто указатели на данные в куче памяти.По умолчанию это null, и сначала вы должны выделить для них память в куче, чтобы они фактически указывали куда-то, используя new.

В этом случае у вас есть поле типа Node в качествеСвойство класса Node, что хорошо, потому что это либо просто null, либо оно указывает на другое место в куче памяти, где хранится следующий узел.Если вы изменили class на struct, это не скомпилирует, так как это вызовет "рекурсивную" проблему, о которой вы упоминаете.Но с классами это просто ссылка, и значением по умолчанию является null, поэтому ему не нужно указывать на экземпляр , а создание экземпляра Node создает только один экземпляр Node в памяти,с next == null.

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

Я считаю полезным использовать изображения при построении алгоритмов связанного списка.Вы можете представить каждое поле next как стрелку, указывающую куда-то.И когда значение null, оно просто указывает "никуда".Наконец, когда вы назначаете что-то для next, вы просто меняете место, куда указывает стрелка.

Answer 2

похоже, а не связанный список, это большой объект с рекурсивным тем же классом внутри

Node является class, что означает, что поле Node next; - это ссылка (в широком смысле взаимозаменяемая с указателем в терминах терминологии).Так что нет: это определенно связанный список.Node не содержит a Node.Он содержит поле, которое является ссылкой (think: pointer) на другое Node.

не cur = head означает "cur" копировать ВСЕ элементы связанного списка?

Не копирует любые элементы.Это изменяет поле ссылки (думаю: указатель) на некоторых существующих объектах, и вот оно .Нет копирования.Однако это посещение всех элементов и изменение указателей на них всех - так что если вы рассчитываете "копирование ссылок (думаю: указателей) на все элементы": конечно, это так.Никаких ассигнований и т. Д.