how to insert a new node if a doubly linked list is empty or has existing node

Dman 0
Viewed 39

What am I doing wrong here? I'm new to linked lists and would appreciate some insight.

I am trying to add a new node in an empty list, or add a new node at the beginning if a node exists:

void insert(node* previous, int value){
    if(previous == nullptr){
        node* newNode = new node;
        newNode->next = nullptr;
        newNode->prev = nullptr;
        (*head) = newNode;
        (*tail) = newNode;
    }else{
        node* newNode = new node;
        newNode->next = (*head);
        newNode->prev = nullptr;
        (*head)->prev = newNode;
        (*head) = newNode;
    }
}

class dlist {
public:
    dlist() { }

    struct node {
        int value;
        node* next;
        node* prev;
    };

    node* head() const { return _head; }
    node* tail() const { return _tail; }

private:
    node* _head = nullptr;
    node* _tail = nullptr;
}
linked-list c++
1 Answers

There are these issues:

  • The code refers to head and tail, but these are not defined. There are _head and _tail members which should be used. They are not pointer-pointers, but just pointers.
  • The code uses previous only to test against nullptr, nothing more. This can never accomplish that the new node should be inserted after that previous node.
  • The code assumes that if previous is nullptr that the list is currently empty, but that is not the meaning of previous. previous is a reference to the node after which a new node must be inserted. This tells us nothing about the list being empty or not.
  • The code assumes that the new node will always become the first in the list (as newNode->prev is always set to nullptr), but the goal is to make newNode the successor of previous, so that when previous is an existing node, newNode->prev should point to that previous node.
  • The value argument is never used. This value should be assigned to the new node's value member.

Here is a possible correction to your code, although we have no way to test it on whichever platform you are to submit it:

    void insert(node* previous, int value) {
        node* newNode = new node; // Always create a new node (no matter what the case is)
        newNode->value = value; // Assign the argument as value
        newNode->prev = previous; // previous is always going to be the predecessor
        if (previous == nullptr) {  // newNode becomes the first node of the list
            newNode->next = _head;
            _head = newNode; // Set it is the new head
        } else { // newNode must come after previous
            newNode->next = previous->next;
            previous->next = newNode; // Set the reverse link
        }
        // If there is a node after the new node, it should have a backreference to it
        if (newNode->next != nullptr) {
            newNode->next->prev = newNode;
        }
        if (_tail == previous) { // Update tail 
            _tail = newNode;
        }
    }
trincot0
Related