Разница между узлом.prev.next = ... и узлом = - PullRequest
Новая
       30

Разница между узлом.prev.next = ... и узлом =

0 голосов
/ 23 января 2019

Для показанного кода, какая именно разница будет. Насколько я понимаю, он должен вернуть значение current.data и изменить указатель для current на current.next для обоих. Кроме того, кто-нибудь может объяснить тонкости current.prev.next = ... и current = ... в целом? DoubleLinkedLists, все еще меня немного смущает. Спасибо! 

public T next() {
    if (!hasNext()){
        throw new NoSuchElementException();
    }
    T data = current.data;
    current = current.next;
    return data;
}

против 

public T next() {
    if(!hasNext()) {
        throw new NoSuchElementException();
    }
    current = current.next;
    return current.prev.data;
}

1 Ответ

0 голосов
/ 23 января 2019

TL; DR ~

Если у вас был двусвязный список, AND узел имеет как предыдущий node, так и next узел. Сказав node->previous->next, вы действительно вернетесь к начальной точке. Но если вы находитесь в начале или в конце списка, код потерпит крах (потому что он пытается NULL->next). Так что не делай этого.

Хорошо, давайте на минуту забудем о структурах данных.

Представьте, что «узел» - это человек в футболке. На всей этой футболке написано их имя (данные).

В первом случае люди выстроились в линию, все лицом к лицу в одном направлении, а человек сзади вытянул руку, указывая на человека перед собой. Если вы ищете «Джо», вы можете увидеть, является ли текущий человек «Джо», и есть ли другой человек, чтобы проверить (на кого указывает «Джо», или он последний).

Это односвязный список. Каждый человек знает только о себе и о следующем человеке. Каждый человек может «видеть» только человека перед собой, а не человека позади. Чтобы узнать имя человека, вы должны спросить самого человека или человека, указывающего на них. То есть спросите node.data или node->next.data. Вы можете спросить человека о том, кто следующий, а не кто предыдущий. Они не знают, кто предыдущий.

Теперь представьте, что люди стоят на одной линии, указывая на двух людей по обе стороны. Это двусвязный список. Каждый человек указывает на предыдущего человека и следующего человека. Любой данный человек может сказать вам свое имя и имя людей, на которых он указывает. Также возможно перемещаться в обоих направлениях вдоль списка людей, поскольку они могут сказать вам, на кого они указывают в обоих направлениях.

Это дает нам некоторый код: 

structure NodeSingle
{
    String       name;
    NodeSingle   next;
}

и 

structure NodeDouble
{
    String       name;
    NodeDouble   previous;
    NodeDouble   next;
}

Итак, мы начнем с пустого (односвязного) списка.

Приходит "Боб". Бобу не на кого указывать (ни на следующий, ни на предыдущий), поэтому в терминах данных мы получаем ["Bob", <>].

Затем приходит "Салли". По какой-то причине мы хотим, чтобы список сортировался в алфавитном порядке. Поэтому мы смотрим на Боба и решаем, что Салли должна идти дальше. Таким образом, мы заставляем Боба указать на Салли. ["Bob", <Sally>] и ["Sally", <>].

Затем приходит "Эрнст", он должен идти между Бобом и Салли: ["Bob", <Ernst>] ["Ernst",<Sally>] ["Sally", <>]

В программировании здесь используется node->next. Когда мы добавили «Салли», мы могли бы сказать ["Bob"]->next = new NodeSingle("Sally").

Если [Sally] должен был находиться между [Bob] и [Tina], то, очевидно, ["Bob"]->next = new NodeSingle("Sally", <Tina>)

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

Таким образом, при программировании можно ссылаться на узлы: node->next->next ... и т. Д. Если определены next и prev (и это большое значение, если), это используется для перемещения по цепочке.

Представьте себе простую функцию поиска: 

// Return the node with name = <for_this_name> or NULL
NodeSingle *find(NodeSingle *list, String for_this_name)
{
    while (list != NULL && list->name != for_this_name)
        list = list->next;  // skip to next node
    return list; 
}
...