нужен для заголовка узла

Question

мы говорим, что связанный заголовок список - это тот, который состоит из специального узла, называемого узлом заголовка, который отмечает начало списка но я не понимаю, какова важность этого узла заголовка. пожалуйста, помогите мне?

Answer 1

Наличие сторожевых узлов избавляет вас от необходимости обрабатывать определенные крайние случаи.

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

Рассмотрим два случая:

С головой и хвостовым узлом:

addNewDataAtHead( data ):
    newNode = new Node(data);
    newNode.next = head.next;
    newNode.prev = head;
    head.next.prev = newNode;
    head.next = newNode;

Без:

addNewDataAtHead( data ):
    newNode = new Node(data);
    if (head == null):
        head = newNode;
    newNode.next = head;
    head.prev = newNode;
    head =  newNode;

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

Answer 2

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

Это потому, что пустой список выглядит так:

        +-------+    +-------+
head -> | dummy | -> | dummy | -> null
null <- | head  | <- | tail  | <- tail
        +-------+    +-------+

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

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

def init ():                            def init ():
    head = null                             head = new node
    tail = null                             tail = new node
                                            head->next = tail
                                            head->prev = null
                                            tail->prev = head
                                            tail->next = null

Сравните классическое добавление (вставка еще более сложна, поскольку вам может потребоваться вставить до head, в середине или после tail) с упрощенным:

def append (node):                      def append (node):
    node->next = null                       node->next = tail
    if head == null:                        node->prev = tail->prev
        head = node                         tail->prev = node
        tail = node
        node->prev = null
    else:
        tail->next = node
        node->prev = tail
        tail = node

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

def delete (node):                      def delete (node):
    if node == head and node == tail:       if node != head and node != tail:
        head = null                             node->prev->next = node->next
        tail = null                             node->next->prev = node->prev
    elsif node == head:                         free node
        head = head->next
        head->prev = null
    elsif node == tail:
        tail = tail->prev
        tail->next = null
    else:
        node->prev->next = node->next
        node->next->prev = node->prev
    free node

Код для обхода списка, конечно, должен исключать фиктивные узлы, но это тривиальное изменение:

def traverse (head):                    def traverse (head):
    node = head                             node = head->next
    while node != null:                     while node != tail:
        do something with node                  do something with node
        node = node->next                       node = node->next

---

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