Как вставить новый узел перед первым узлом двусвязного списка?

Question

Я смотрю, как вставить новый узел перед первым узлом двусвязного списка. Я путаюсь с вспомогательными узлами, необходимыми для этой операции, и последовательностью шагов , для которых необходимо выполнить операцию. Я был бы признателен за подсказку о том, как решить эту проблему, т.е. что не так с моим insertBeforeFirst методом. В его нынешнем виде метод вызывает исключение nullPointerException, которое мне трудно устранить. (примечание: это продолжение предыдущей записи .)

public DLL()
{
    header = null ;
    tail = null ;
}

...
DLL myList = new DLL() ;
DLLNode A = new DLLNode("Hello", null, null) ;
DLLNode B = new DLLNode("Hi", null, null) ;
...

myList.addFirst(A) ;
myList.insertBeforeFirst(B)

...
public void addFirst(DLLNode v)
{
    v.pred = header ; 
    v.succ = tail ; 
    header = v ;
    tail = v ;
}
...

public void insertBeforeFirst(DLLNode v)
{
    DLLNode aux = v ;
    aux.succ = header.succ ;
    header = aux ;
    DLLNode aux2 = aux.succ ;
    aux2.pred = v ;
}

[EDIT]

Я последовал совету Аарона и сделал чертеж, и у меня есть небольшое улучшение в том, что я больше не получаю исключение nullPointerException, но новый режим вставляется после первого узла, а не до. Так что мои навыки рисования тоже нуждаются в полировке:)

public void insertBeforeFirst(DLLNode v)
{
    v.succ = header.succ ; // point new node succ to current first node
    header.succ = v ;  //point header to new node
    DLLNode aux = header.succ ; // auxiliary node for backward insertion
    aux.pred = v ; // point auxiliary's pred backward to new node
}

[EDIT2]

Глядя на сообщение MahlerFive, я теперь понимаю, почему некоторые из вас могут запутаться из-за моего заголовка и разговора. Вот откуда я это взял: "Для упрощения программирования удобно добавлять специальные узлы на обоих концах двусвязного списка: узел header непосредственно перед заголовком списка, и трейлер узел сразу после хвоста списка. Эти "фиктивные" узлы не хранят никаких элементов " source

Так что для начала мне нужно найти способ правильно реализовать эти фиктивные узлы, прежде чем я смогу что-либо добавить и сделать правильные ссылки. кажется, что эти DUMMY-узлы требуют другого конструктора Node? Могут ли они быть созданы конструктором DLL по умолчанию?

[EDIT3]

@ MahlerFive, конструктор DLL будет выглядеть так:

public DLL()
{
    DLLNode Header = new DLLNode(null, null, null) ;
    DLLNode Tail = new DLLNode(null, Header, null) ;
    Header.succ = Tail ;
}

и мой метод примерно такой, хотя в настоящий момент я получаю исключение nullPointerException:

// insert z before v
public void addBeforeFirst(DLLNode v, DLLNode z)
{
    DLLNode aux = v.pred ;
    z.pred = aux ;
    z.succ = v ;
    v.pred = z ;
    aux.succ = z ;
}

[EDIT4]

Я делаю успехи. (отличное чувство!) Я согласен с MahlerFive, что узлы DUMMY Header и Tail не являются отличным способом приблизиться к этому. Но, как было упомянуто в опубликованной книге по этому вопросу, его стоит хотя бы изучить. Вот мой новый код (без использования фиктивных узлов):

...

// DLL Constructor
public DLL()
{
    first = null ;
    last = null ;
}
...
// example insert call
// B is the node in front of which i want to insert
l.insert("Ciao", B) ;
...

public void insert(String elem, DLLNode pred)
{
    // make ins a link to a newly-created node with element elem,
    // predecessor null, and successor null.
    DLLNode ins = new DLLNode(elem, null, null) ;
    // Insert ins at the insertion point in the
    // forward SLL headed by first.
    ins.pred = first ;
    ins.succ = first ;
    // let first be the the new node
    first = ins ;
}

это требует тонкой настройки, поскольку я еще не установил никаких обратных ссылок, но это отличная отправная точка. Чтобы убедиться, что это работает правильно (по крайней мере, в прямом направлении), я добавил операторы печати, чтобы распечатать первый и последний элемент при добавлении узлов. Действительно, они были обновлены правильно:

Hi
first: hi
last: hi

Ciao Hi
first: Ciao
last: hi

Moin Ciao Hi
first: Moin
last: hi

Answer 1

Вместо того чтобы делать все это в своем мозгу, сядьте на пять минут и нарисуйте структуру данных (DLL и 2-3 пары узлов) на бумаге.

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

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

Теперь сядьте и внесите каждое изменение.

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

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

Answer 2

Похоже, большая часть вашего замешательства связана с тем, как работает header.Это просто ссылка на первый узел в списке.Кроме того, нет необходимости во «вспомогательном» узле.

Давайте рассмотрим шаги, которые необходимо предпринять, чтобы:

Шаг 1: Установить pred узла, который вы вставляете.

Поскольку узел станет первым узлом, за ним не будет никаких узлов, так что вы можете сказать v.pred = null;

Шаг 2: Установите succ вставляемого узла.

Наш новый узел должен указывать вперед на старый первый узел.Вот где приходит путаница.Вы делаете следующее:

v.succ = header.succ ; // point new node succ to current first node

Но что такое header?Это ссылка на первый узел.Говоря header.succ, вы говорите, что хотите получить преемника первого узла, который является вторым узлом.Когда вы видите header, просто подумайте «первый узел», и вы получите:

v.succ = header;

Шаг 3: Укажите старый первый узел обратно нановый узел

Вы уже делаете этот шаг правильно (помните, что заголовок «первый узел»):

header.succ = v ; //point header to new node

Шаг 4: Теперь сделайте новый узел заголовком

header = v;

РЕДАКТИРОВАТЬ (в ответ на ваши изменения # 3): В этом подходе есть некоторые проблемы, которыеЯ приведу в конце, но пока что в стороне, и при условии, что вы должны настроить свой список таким образом ...

Предполагая, что вы переходите в первый узел списка (Заголовок.succ) как v, давайте сделаем те же шаги:

Шаг 1: Установите pred узла, который вы вставляете.

Вы хотите, чтобы ваш новый узелукажите назад на заголовок.v.pred = Header;

Шаг 2: Установите succ вставляемого узла.

Вы хотите, чтобы ваш новый узел указывал на старый первый узел, которыйбыло Header.succ

v.succ = Header.succ;

Шаг 3: Укажите старый первый узел обратно на новый узел

Убедитесь, что выпервый узел существует первым (забыл об этом в моем первом посте)!

if (Header.succ != null) {
    Header.succ.pred = v; // Header.succ is the first node, and you want to set its pred reference
}

Шаг 4: Теперь сделайте новый узел первым узлом

Header.succ = v;

Обратите внимание, каквам даже не нужно z, поскольку вы можете добраться до первого узла, используя Header.succ.Это означает, что вам не нужно использовать его в качестве параметра.

Теперь, кроме всего этого, есть некоторые проблемы, о которых вы должны подумать:

Какой смысл в заголовке, имеющем ссылку pred иполе данных?Какой смысл в хвосте, имеющем succ-ссылку и поле данных?

Если вы хотите использовать этот связанный список и вставлять элементы, не лучше ли было бы просто вызвать add () длякаждый элемент вместо addFirst () и addBeforeFirst ()?Что если бы вы могли использовать метод remove (), то вам нужно было бы отслеживать, является ли список пустым или нет, чтобы выяснить, какой метод вызывать, addFirst () или addBeforeFirst (), что довольно уродливо.Лучше написать более обобщенный метод add (), который позаботится об этом для пользователя, который будет использовать этот список.