Как происходит смена головы списка при вставке?

Question

[Джина Ли]

Глупый вопрос от новичка:
Есть кусок код на С++, который описывает вставкунового элемента в голову списка :

void LinkedList::headInsert(int val)
{
    /* The list is empty? */
    if (_pHead == NULL) {
        /* the same to create a new list with a given value */
        _pTail = _pHead = new Node(val);
    }
    else
    {
        /* Create a new node and insert it before the head node */
        Node *node = new Node(val);
        node->_pNext = _pHead;
     
 /* Update the head node */
        _pHead = node;
    }
}

Неясно что происходит в конце

/* Update the head node */
        _pHead = node;

до этой строчки node указывает на голову, и головой списка считается изначальная голова списка. А потом как? Мы обращаемся к исходной голове списка и присваиваем ей node. Выходит, что за node следует node (два одинаковых элемента). Что я неправильно понимаю?

Answer 1

[Павел Шафоростов]

Попробую как-нибудь рассказать :) Первый момент - надеюсь понятно, что если нет головы, то она создается, а если есть - то добавляется элемент. В коде указан некий класс Node. При создании объекта от этого класса принимаем значение val как значение этого объекта. Также в данном объекте есть ссылка на следующий объект, что необходимо для реализации списка.
Допустим есть 1 элемент в списке. Каждый элемент - это объект класса Node. В нем есть некое значение, и ссылка на слд. объект. Но так как объекта нету, то ссылка указывает на NULL.
Вставляем новый элемент. Для этого создаем новый объект класса Node с необходимым значением. Ссылку, которая введет на слд. объект мы указываем на голову данного списка. Теперь у нас есть 2 разных объекта (при *node = new Node(val) создаются разные объекты класса). И для финиша указываем что голова это наш новый элемент/объект

Comments

[Джина Ли]

Спасибо. Это все ясно, кроме последнего предложения. Вот я вижу все это как
cs628224.vk.me/v628224737/1b6f1/H0Krk5Onozg.jpg
(слева от черты я ввожу обозначения)
после первой картинки ("Вставляем новый элемент. Для этого создаем новый объект класса Node с необходимым значением. Ссылку, которая введет на слд. объект мы указываем на голову данного списка. Теперь у нас есть 2 разных объекта (при *node = new Node(val) создаются разные объекты класса)") мы обращаемся к _pHead, то есть кружочку. ему мы присваиваем node ( _pHead = node;). В итоге я вижу картинку 2. вот и вопрос,как происходит, куда обращаемся при "И для финиша указываем что голова это наш новый элемент/объект"

[Павел Шафоростов]

Попробовал на листке все изложить: cs628126.vk.me/v628126718/23f0e/YG-ffrfw544.jpg

[Джина Ли]

Павел Шафоростов: спасибо :)

Answer 2

[Artem Vereschaka]

Тут Вам следует понимать что вы оперируете с объектами. То есть в конце ссылка на новую голову перемещается на новый, только что созданный, элемент.

Answer 3

[abcd0x00]

до этой строчки node указывает на голову

Он указывает не на голову, а на только что выделенный через new фрагмент памяти.
А вот уже внутри этого фрагмента памяти есть указатель, который указывает на голову.
Дальше они (новый узел и голова) становятся связанными и мы можем сделать новый узел головой.
Доступ к прежней голове осуществляется через новую голову.