Что такое "глава" связанного списка?

Я работаю в связанных списках на Java, поэтому я пытаюсь понять концепцию одного связанного списка.

head -> 12 -> 34 -> 56 -> null

head.next будет 12 (также то же, что и node1). Однако, что такое голова?

Обновление: В чем разница между ссылкой и указателем?

Update2: Итак, если head есть 12 и head.next is 34, то это не означает, что следующая функция пропускает первый node, чтобы увидеть, является ли он нулевым?

public void add(Object data, int index)
    // post: inserts the specified element at the specified position in this list.
    {
        Node temp = new Node(data);
        Node current = head;
        // crawl to the requested index or the last element in the list,
        // whichever comes first
        for(int i = 1; i < index && current.getNext() != null; i++)
        {
            current = current.getNext();
        }
        // set the new node next-node reference to this node next-node reference
        temp.setNext(current.getNext());
        // now set this node next-node reference to the new node
        current.setNext(temp);
        listCount++;// increment the number of elements variable
    }

Источник: http://www.mycstutorials.com/articles/data_structures/linkedlists

Ответ 1

Глава списка относится к первому node списка. Это сделало бы хорошее имя для переменной, хранящей ссылку этого node, и я ожидаю, что она будет содержать нулевую ссылку, если список был пуст

someLinkedList.head
         |
         |
         v
        ______        ______        ______            
       |    |n|      |    |n|      |    |n|           
       |    |e|      |    |e|      |    |e|           
       | 12 |x| -->  | 34 |x| -->  | 56 |x| --> null
       |    |t|      |    |t|      |    |t|           
       |____|_|      |____|_|      |____|_|

В зависимости от контекста хвост может ссылаться на разные вещи. Терминология, к которой я привык, говорит, что хвост соответствует 34 -> 56 -> null в этом примере, то есть список, следующий за головой.

В других контекстах это может быть ссылка на последний node. В такой интерпретации хвост будет ссылаться на 56 node в вашем примере.

Относительно вашего первого редактирования, который, оказывается, совершенно другой вопрос:

Указатель - это значение, соответствующее адресу памяти. Ссылка - это значение, относящееся к некоторому объекту (или null). Вы не можете выполнять арифметику указателей на ссылках Java, но в противном случае я бы сказал, что они довольно похожи.

Что может вас смутить, так это то, что переменные в Java никогда не могут содержать объекты. Объекты всегда живут в куче, а переменные содержат примитивные типы данных или ссылки на объекты в куче.

Что касается второго редактирования:

В примере, который вы указали, похоже, что метод добавления пропускает первый элемент и в некотором смысле это делает. Это связано с тем, что реализация имеет элемент "dummy" в качестве головы. Посмотрите на инициализацию head-переменной в конструкторе:

head = new Node(null);

Я не понимаю, почему они решили это сделать. Для меня это выглядит глупо.

Ответ 2

Термин "голова" имеет два совершенно несвязанных значения. Наиболее распространенный (который, как мне кажется, выходит из Lisp), является "первым элементом списка". Судя по вашей диаграмме, это не значит, что вы имеете в виду.

Второе значение относится к методу решения следующей проблемы: если вы представляете связанный список как только узлы с данными, тогда, когда список пуст, все ссылки (и/или указатели, в зависимости от языка) в список должны быть нулевые, потому что на что нечего указывать. Это создает множество проблем с бухгалтерией для кода, который использует этот список. Эта проблема решена. Это список node, который не содержит фактических данных. Ссылка или указатель на список всегда является указателем на голову node. Первый элемент списка всегда head.next. Обычно существование главы скрывается в классе, который реализует "связанный список с головой".

В зависимости от поддерживаемых операций в конце списка может возникнуть подобная проблема бухгалтерского учета, особенно для двусвязных списков. Хвост списка node упрощает ведение бухгалтерии.

Они также называются "дозорными узлами" в литературе (включая статью Википедии о связанных списках).

Ответ 3

да, это просто указатель на первый node

Ответ 4

Прежде чем что-либо еще Следует отметить, что голова не является отдельной node, а просто ссылкой на первый node. Он сохраняет весь список, сохраняя указатель на первый node.

Другая заметная разница заключается в том, что head - обычная локальная переменная указателя, которая хранится в стеке, тогда как узлы списка сохраняются в куче. Таким образом, в большинстве терминов "голова" Head - это просто локальный указатель, который ссылается на первый элемент связанного списка и в основном инициализируется с помощью NULL, чтобы отличить пустой список.