Вставка для связанного списка псевдо-кода

Question

В Введение в алгоритм Ed 3, я прочитал псевдокод algo для вставки элемента в связанный список, и я не понимаю средний шаг.

x.prev = L.head 
if L.head != NIL 
    L.head.prev = x 
L.head = x 
x.prev = NIL 

и если мой оригинальный связанный список HEAD -- 4 -- 24, я понимаю, что шаги являются следующие:

1. ГОЛОВЫ - 4 - 24

2. х - 4 - 24

3. ГОЛОВКА - х - 4 - 24

с 2. соответствующей

x.prev = L.head 

Почему мы должны вставить х, прежде чем голова

if L.head != NIL 
     L.head.prev = x 

?

Может ли smbdy уточнить?

Answer 1

Допустим, сначала Head указывает на узел [Y], это означает, что [Y] - текущая головка. Мы собираемся вставить новый узел [X], который станет головным узлом нашего списка, поэтому указатель на голову укажет на [X].

Здесь следует помнить, что в начале времени (прежде чем вставлять что-либо в список) голова укажет на NiL.

Теперь давайте шаг идти за шагом с псевдокоде, чтобы увидеть, что происходит:

Текущая ситуация нашего списка: Head -> [Y], [Y].prev -> NiL, а голова указывает на [Y], так что пока мы не изменим указатель Head , всякий раз, когда мы используем Head, вы можете думать/читать его как [Y]. Теперь нынешний глава узел [Y] будет идти после того, как [X], так позволяет установить следующий из [X] = [Y]

1. x.next = L.head 

После утверждения кулак, мы имеем [X].next->[Y], Head->[Y], [Y].prev->NiL

2. if (L.head != NIL) //At the beginning Head might be pointing to NiL, and of course NiL.prev does not exist and we do not want to access illegal location. 
    3. L.head.prev = x //if head is not pointing to Nil then it is pointing to [Y], 
         //in that case [X] will be the prev node of [Y], 
        //so after this line, have Head->[Y], [X].next->[Y], [Y].prev->[X] 

После 3 line, мы можем смело установить наш список Указатель на точку [X]

4. L.head = x  
5. x.prev = NIL //You can write L.head.prev = NIL, as [X] is now the new head 

Answer 2

Подсказка в том, что

L: головка: предварительно обозначает предварительно атрибут объекта, который Л: голова указывает на

Затем алго идет следующим образом

//HEAD -- 4 -- 24 

    x.next = l.head 
    if L.head != NIL 
     L.head.prev = x 

    //x -- 4 -- 24 

    L.head = x 
    x.prev = NIL 

    //HEAD -- x -- 4 --24