Всем привет. Товарищи, второй день сижу над этой задачей. Но кроме строчки Node node = new Node(); ничего не написал. Вообще нет понимания как к этой задаче подступиться. При этом сама тема связанных списков понятна. И в грокаем алгоритмы читал про них, и здесь... Но погоды это не делает. Как быть? С чего начать? Смотрел и правильное решение, вот хоть убей не понятно оно мне.
Евгений
32 уровень
Не понимаю с чего начать...
Решен
Комментарии (12)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Евгений
14 марта, 12:32
Всем спасибо за ответы. НО проблема не в том, что я не знаю как строится цепочка связанного списка. По мне так это элементарно. Проблема в том, что не понятно как этот процесс описать кодом. Не понятны сами операции присвоения этих ссылок. Не понятна эта логика. Уже и брал занятия с ментором, разбирали создание связанного списка с нуля. И вроде какое то понимание пришло. Но когда добрался до этой задачи вновь, реализовать ничего не получилось. Пересмотрел еще кучу видео. Но на написание моего кода для решения этой задачи все это никак не повлияло.
Вот что делает этот конструктор в правильном решении?
public StringLinkedList(){
first.next = first;
last.prev = last;
}
Если читать его перевод, то первому следующему присваивается первый.
Последнему предыдущему присваивается последний. Как это понимать, ума не приложу. Я таким тупым себя давно не чувствовал.
+2
Anonymous #3303140
14 марта, 14:38
Ниже будут слайды, которые я выкладывал кому-то в ответ на схожий вопрос, но они могут помочь и тебе. Тот вопрос не смог найти, поиск в разделе помощи так себе работает. На каждом изображении будут нарисованы стрелки между нодами и строки кода, которые являют собой эти самые связи. Если тебе действительно понятна логика построения двусвязного списка, то ты должен разобраться. Если ты не сможешь понять самостоятельно, задавай вопросы. Только, пожалуйста, предметно. Вопросы в духе "вообще ничего непонятно" вообще не способствуют тому, чтобы тебе помогли. Так не бывает, да и это говорит скорее о том, что тебе лень сформулировать свои мысли и сформулировать вопрос, А если ты спросишь про конкретную строку, объяснишь как ты сам её понимаешь и спросишь, верны ли твои рассуждения, а если нет, то в чём именно -- вот тогда можно разговаривать.
Информацию на картинках дополню своими комментариями. Картинки склеены парами.
Итак, поехали.
Ты знаешь, что такое ноды в списке, что они ссылаются на своих соседей слева и справа. Ссылка next смотрит вперёд, ссылка prev - назад. Тебе нужно реализовать механизм добавления новых нод в список.
1. В методе main создаётся новый список. При создании выполняется код конструктора, который создаёт крайние ноды first и last, которые ссылаются друг на друга. Они не содержат значений, только ссылки на первую и последнюю ноду со значениями.
2. Добавляем новую ноду со значением. Это будет первая нода, содержащая значение. Изначально она никуда не ссылается., поэтому рисуем её без стрелочек. Для удобства изобразим её посередине между first и last. При этом ссылки first.next и last.prev остались без изменений.
+9
Anonymous #3303140
14 марта, 15:02
Досюда ты дошёл самостоятельно. Дальше тебе нужно соединить новую ноду со своими соседями.
3. Тебе нужно знать, от какой ноды нарисовать входящую слева стрелку к новой ноде. Для этого нужно посмотреть, какая нода идёт перед last: last всегда будет последней, а last.prev ссылается на ту, которая была перед ней. Поэтому мы возьмём ту ноду, на которую ссылается last.prev и для удобства сохраним её в новую переменную lastNode. Это будет последняя ссылка на последнюю добавленную перед этим ноду, а в случае пустого списка она совпадёт с нодой first.
4. Соединим ноду lastNode с новой нодой node.
Чтобы полностью встроить ноду, тебе предстоит воссоздать все 4 связи: каждый из соседей должен ссылаться на новую ноду, и нода должна ссылаться на каждого из соседей. Пока мы реализовали одну стрелку: сосед слева ссылаются на новую ноду. Продолжим строить эти связи.
5. Нода ссылается на соседа слева, т.к. сосед слева - это всегда lastNode, т.е. последняя нода, которую добавили перед этим
6. Сосед справа - это всегда “якорь” last, потому что мы добавляем ноды в конец списка. Добавим ссылку от соседа справа к новой ноде
+10
Anonymous #3303140
14 марта, 15:02решение
7. И от новой ноды к соседу обратно к соседу справа. Информация на стикере относится не к тебе, а к тому, для кого изначально я делал эти схемы.
8. При добавлении следующей ноды, теперь уже эта следующая нода будет называться node, а та, что мы добавили перед этим будет храниться в переменной lastNode, потому что на неё указывает ссылка last.prev на верхней картинке.
9. Остаётся сделать вместо двух имеющихся связей между lastNode и last четыре новых связи - две между lastNode и node, две между node и last
Так ты и добавляешь ноды в список.
Получается, ты знаешь, что такое двусвязный список, что каждый элемент должен ссылатсья на своих соседей. Знаешь, что в переменной хранится ссылка. Понимаешь, что `=` - это операция присваивания, которая означает "взять значение, полученное справа от знака равно и поместить (присвоить) в переменную слева от знака равно. По сути - это весь багаж знаний, необходимый для того, чтобы решить эту задачу. Тебе не хватает - я не знаю, воображения, что ли.
Я буду признателен, если ты оставишь обратную связь, скажешь, удалось ли разобраться с помощью этой схемы, и что именно было тебе непонятно, что мешало решить самому.
+19
Евгений
14 марта, 15:59
Товарищ!!! Это сильно! Просто не знаю как и благодарить тебя! Самое интересное что эти картинки встречал. Но с твоими объяснениями я наконец то понял все. Спасибо огромное за твой труд! Я 3 дня ломал мозг)))).
0
Anonymous #3303140
14 марта, 16:27
А что было непонятно в эти три дня, что не складывалось?
0
Евгений
14 марта, 18:16
Было не понятно вообще с чего начать. Если честно я и сейчас не понимаю как бы я смог до этого решения сам додуматься. у меня получалось только вывести в консоль значение первого элемента. Далее пытался запустить цикл, на вывод остальных элементов и присваивания им ссылок. Но считаю, что для человека с "нуля" базы которая дана на этом этапе курса вообще не хватает для реализации подобных методов. Более того и гугление ничего не дало. Конечно по себе людей других не судят...
+1
Alexey
20 марта, 19:21
Твое объяснение помогло и мне. Лично я думал, что Ноды first и last начальные объекты, в которые записываются значения, а следующие добавляются - это и сбивало меня с толку. А теперь, как понял, они не учитываются в списке, а нужны как бы для "ориентации". Читал дословно из условия задачи : "нужно изменить ссылку последней ноды на новосозданную, а новосозданная станет последней."
0
Екатерина
4 июня, 13:09
Спасибо большое анонимус! Долго не могла понять зачем создаем lastNode, но при этом понимала, что нужно от чего-то "отталкиваться" чтобы не создавать новые Ноды на одном и том же месте и не был понятен порядок присваивания ссылок, сейчас все стало на свои места
0
Антон Карпов
14 марта, 05:33полезный
Если уже смотрел правильное решение, тогда я думаю ты не будешь против если я скину свой вариант. Он длиннее и там есть лишние строки, которые можно не писать, но лично мне было легче разобраться с таким кодом:
Моменты, которые помогут это осмыслить:
1. Когда мы передаем объект переменной, она хранит ссылку на этот объект.
2. Во время добавления ноды у нас возможно два случая: либо старых нод еще не было совсем и эта первая, либо у нас уже есть какая-то нода и мы добавляем новую в конец списка.
3. Добавляя новую ноду к уже имеющимся надо не забывать менять в старой ноде ссылку на новую. Это можно сделать такой конструкцией: "last.prev.next" - где last.prev - это ссылка на прошлую ноду, которая хранится в объекте last.
Теперь попробуй в тетрадке нарисовать весь процесс. Сначала по краям нарисуй объекты first и last. И затем добавь первую ноду с тремя ячейками: next,value, prev. Заполни в ней значения. Потом у объектов first и last поменяй ссылки на эту ноду.
Затем добавь вторую ноду, добавь в нее ссылки, поменяй в предыдущей ноде ссылку на текущую. И поменяй в объекте Last ссылку на последнюю ноду.
Когда все это сделаешь, станет понятно где, что как меняется.
Ну и в самом конце, перепеши этот код. Убери лишние вещи (например нам не надо задавать значение null у нод, т.к. они и так null.
Затем попробуй разобрать код из задачи, где задействован конструктор.
+3
ZloyLis
13 марта, 23:56
Попробуй в тетради просто нарисовать схему работы списка так, как ты его понимаешь. Потом попробуй пошагово реализовать в коде. Буквально по строкам.
0
Anonymous #3303140
13 марта, 19:17
Попробуй почитать объяснение здесь https://javarush.com/help/88991
0