Какова «голова» связанного списка?

Question

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

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

head.next будет 12 (также как узел1).Тем не менее, что такое голова?

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

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

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's next-node reference to this node's next-node reference
        temp.setNext(current.getNext());
        // now set this node's 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

Answer 1

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

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

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

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

---

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

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

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

---

Относительно вашего второго редактирования:

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

head = new Node(null);

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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