I implement a doubly linked list in C ++ without using STL.

struct DLNode { //узел списка int d; DLNode * next, * prev; }; DLNode * AddHeadDL (int data, DLNode * head) { DLNode * temp = new DLNode; temp->d = data; temp->next = head; if (head) head->prev = temp; head = temp; temp->prev = NULL; return head; } //функция, добавляющая элемент в начало списка и возвращающая указатель на начало списка DLNode * RemoveHeadDL (DLNode * head) { if (head) { DLNode * cur = head; head = head->next; cur->next = NULL; delete cur; cur=NULL; } if (!head) cout << "head is null" << endl; return head; } //функция, удаляющая первый элемент из списка и возвращающая указатель на список void ListAll (DLNode * head) { if (head) { DLNode * cur = head; while (cur) { cout << cur->d << endl; cur=cur->next; } } } //функция вывода списка в консоль /*Текст основной программы*/ int main() { DLNode * head = 0; head = AddHeadDL (21, head); ListAll (head); if (!head->next) cout << "end is null" << endl; if (!head->prev) cout << "prev is null" << endl; if (head) cout << "list isn't empty" << endl; RemoveHeadDL (head); if (!head) cout << "success" << endl; else cout << head->d << endl; _getch (); return 0; }

After removing a single item from the list, it continues to remain non-empty. However, if you make a simple check inside the RemoveHeadDL function after the line head = head->next; output to the console: if (!head) cout << "head is null" << endl; , you can easily make sure that head does not indicate anywhere, as it should be. However, immediately after using the RemoveHeadDL function in main , it turns out that the head still points to a certain node containing some value. What could be the problem?

    1 answer 1

    You must call the delete item function as follows.

     head = RemoveHeadDL (head);

    Otherwise, the head in main will not change.

    In addition, in the function itself, the value of head->prev not set to NULL .

    The function can be written as follows.

     DLNode * RemoveHeadDL( DLNode * head ) { if ( head ) { DLNode * cur = head; head = head->next; if ( head ) head->prev = NULL; delete cur; } if (!head) cout << "head is null" << endl; return head; } //функция, удаляющая первый элемент из списка и возвращающая указатель на список
    • I would also add that the correct (or more general) approach to the construction of a doubly linked list is to represent it as a pair of pointers, one on the head (at first), and the second at the tail (on the last) of the list. - avp
    • @Vlad Thank you for the very fast response, the solution of the problem and a sensible comment! - neonb