Как получить корневой узел при удалении из односвязного списка - PullRequest
Новая
       2

Как получить корневой узел при удалении из односвязного списка

0 голосов
/ 09 мая 2011

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

class LinkedList { 
    LinkedListNode root; 

    // Remove the nodes which contain data equal to obj 
    void deleteNode(Object obj) { 
        // special case for root 
        if( root.data.equals(obj) ) { 
            root = root.next; 
        }  
        LinkedListNode current = root; 
        // iterate through list looking for obj 
        while( current.next != null ) { 
            // match found 
            if( current.next.data.equals(obj) ) { 
                // cut out the node 
                current.next = current.next.next; 
            } 
            current = current.next; 
        }
    }
} 

private class LinkedListNode { 
    Object data; 
    LinkedListNode next; 
}

Я не уверен, почему, просто создавая корень LinkedListNode, он ссылается на корневой узел. Ясная и легкая для понимания помощь будет высоко ценится.

Ff теоретически я не создал корень LinkedListNode, могу ли я просто передать дополнительный параметр в функцию удаления и указать, какой из них является заголовком на основе его данных? 

LinkedListNode deleteNode(LinkedListNode head, int d) {
    LinkedListNode n = head;
    if (n.data == d) {
        return head.next; /* moved head */
    }
    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
            return head; /* head didn’t change */
        }
        n = n.next;
    }
}

Ответы [ 2 ]

0 голосов
/ 09 мая 2011

Это не автоматически.«Корень» - это переменная класса для класса LinkedList, то есть каждый экземпляр класса LinkedList имеет атрибут с именем root, который является некоторым LinkedListNode.Вы можете использовать и / или ссылаться на это где угодно в определении класса.

Корневой узел будет указан при создании экземпляра класса LinkedList в его конструкторе (который, я предполагаю, где-то существует).Если это не так, то не будет никакой ссылки на созданный вами LinkedList, и он будет практически бесполезен.

Чтобы ответить на вторую часть вашего вопроса, вы могли бы написать такую ​​функцию, но естьне нужно.Это было бы излишним;Вы можете просто использовать ссылку на корневой узел.

0 голосов
/ 09 мая 2011

Я не уверен, что понимаю вопрос ...

LinkedListNode root является закрытым членом класса LinkedList, предположительно инициализированным в конструкторе и / или в другом месте в функции AddNode или чем-то еще. После инициализации члена root (и обращения к корневому узлу списка) такие функции, как DeleteNode, могут использовать его, например: if( root.data.equals(obj) ) { root = root.next; }

Надеюсь, это поможет ...

...