как на самом деле изменяется связанный список

Question

Мне было интересно, может ли кто-нибудь помочь мне с этим вопросом. я верю, что понимаю код и логику по большей части. я могу отследить код, и это имеет смысл, но я не могу понять одну вещь: как предыдущий LinkedListNode фактически меняет переданный LinkedListNode n?

мне кажется, что функция проходит через n и, если элемент еще не найден, помещает его в хеш-таблицу. но когда он найден снова, он использует этот недавно созданный LinkedListNode, чтобы пропустить дубликат и ссылку на следующий элемент, который является n.next. Как это на самом деле отключить LinkedListNode n? Кажется, что предыдущий будет LinkedListNode, который не имеет дубликатов, но, поскольку ничего не возвращается в этой функции, n должен быть тот, который изменяется. Я думаю, я не вижу, как на самом деле меняется n.

Ясная и тщательная помощь будет высоко ценится. Спасибо =)

public static void deleteDups(LinkedListNode n){

    Hashtable table = new Hashtable();
    LinkedListNode previous = null;
    while(n != null){
        if(table.containsKey(n.data))
            previous.next = n.next
        else{
            table.put(n.data, true);
            previous = n;
        }
        n = n.next;
    }
}

не линия ...

LinkedListNode previous = null;

создать новый LinkedListNode?

так что это моя логика того, как я это делаю ... скажем, аргумент n передается как

5 -> 6 -> 5 -> 7

при первом запуске кода предыдущий равен нулю. это входит в оператор else, а предыдущий теперь 5? и тогда строка n = n.next составляет n 6? теперь у хеш-таблицы 5, и она снова зацикливается и переходит в остальное. prev теперь 6, а hastable имеет 6. тогда n становится 5. он снова зацикливается, но на этот раз он переходит в if, а prev теперь 7. и n становится 7. я вижу, что prev пропустил более 5, но .. . как превосходит связь? кажется, что предыдущий - это LinkedListNode, который не содержит дубликатов

Answer 1

как предыдущий LinkedListNode фактически меняет переданный LinkedListNode n?

Посмотрите на строку

n = n.next;

Эта строка вызывает изменение переданного узла n - эффективно перемещая его на один узел вперед с каждой итерацией.

он использует этот недавно созданный LinkedListNode, предшествующий, чтобы пропустить дубликати ссылка на следующий элемент

Нет, новый узел здесь не создается.Узел previous всегда указывает на узел в существующем LinkedList, для которого переданный узел n является одним из узлов.(может быть начальным узлом).Что заставляет вас думать, что он недавно создан?

Похоже, вы запутались в своем понимании того, как узлы и ссылки (и, таким образом, LinkedList в целом) работают в Java.Поскольку все изменения происходят с данными узла, а не с самой ссылкой (тьфу ... это не совсем правильно), исходный LinkedList, переданный методу, действительно модифицируется после его возврата.Вам нужно будет детально проанализировать структуру и работу LinkedList, чтобы понять, как это работает.Прежде всего, я хочу получить ясность относительно того, что передается по значению и передается по ссылкам в Java.

edit:

Ваш анализ прогона верен, однако ваша путаница все еще остается, потому что вы не концептуальнопрояснить некоторые вещи.

В конце вашего анализа вы спрашиваете: "как это prev не связывает n? кажется, что prev - это LinkedListNode, который не содержит дубликатов"

Это беспорядок - сначала нужно различить LinkedListNode и LinkedList.prev и n - это два экземпляра LinkedListNode, а не LinkedList.В вашем примере LinkedList безымянный (у нас нет имени, чтобы ссылаться на него).Это оригинальный список - другого списка нет.

Во-вторых, на вашей иллюстрации числа, которые вы показываете, представляют собой только одну часть узла, называемую данными узла.Другая часть, которую вы пропустили, это ссылка next LinkedListNode, которая неявно присутствует в каждом узле.Ссылка, которую вы рисуете ->, фактически является следующей ссылкой в ​​каждом узле. Когда вы говорите, что предыдущая пропускает 5, на самом деле происходит следующее: следующий узел с данными 6 создается для указания на узел с данными 7.

В начале: 5 | следующий -> 6 | следующий -> 5 | следующий -> 7 | следующий -> NULL

После пропуска 5: 5 | следующий -> 6 | следующий -> 7 | следующий-> NULL

Как видите, связанный список изменен!Не имеет значения, было ли оно изменено с помощью prev или n, изменение остается в списке.

Answer 2

if(table.containsKey(n.data))
            previous.next = n.next

Раздел, который выполняет удаление. Он присваивает ссылку поля next предыдущего узла узлу после текущего узла, фактически отменяя связь с текущим узлом.