Inserting into a Doubly Linked List

Question

I am trying to create a doubly linked list container for a project. I cannot use any std containers. The doubly linked list has to be sorted. Here is my code so far:

#include <iostream>
using namespace std;

template <typename T>
class dll {
private:
    struct Node {
        Node* prev;
        Node* next;
        T data;
    };

    Node* head;
    Node* tail;

public:
    dll();
    ~dll();

    void insert(T value);

    bool empty() const { return head == tail; };
};

template <typename T> dll<T>::dll() {
    head = nullptr;
    tail = head;
}

template <typename T> dll<T>::~dll() {
    delete[] head;
}

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    node->data = value;
    // Case 1: There are no nodes yet
    if (head == nullptr) {
        node->prev = nullptr;
        node->next = nullptr;
        head = node;
        tail = head;
    }
    else {
        // Case 2: There is more than one node
        Node *curr = head;
        if (curr->next != nullptr)
        {
            while (curr->next) {
                // If the value is less than the current value
                if (value < curr->data) {
                    Node *temp = new Node;
                    temp->data = curr->data;
                    temp->next = curr->next;
                    temp->prev = curr->prev;
                    node->next = temp;
                    node->prev = temp->prev;
                    curr->prev = node;
                }
                curr = curr->next;
            }
        }
        // Case 3: There is only one node
        else {
            node->prev = head;
            node->next = nullptr;
            tail = node;
        }
    }
}

int main() {
    dll<int> list;
    list.insert(10);
    list.insert(20);
    list.insert(15);
}

The problem I am having is in my insert function. I am using the debugger and stepping into the code at the line: list.insert(10);.

It correctly goes into the first case where head == nullptr and creates the Node. When I step into the next line of code (list.insert(20) ), it creates a node with this line: Node *node = new Node; But it is creating the node with the memory address that head is pointing to.

I put a watch on the head variable and the node variable and the memory addresses were the same.Basically it is creating the same Node as it did for the last insertion.

I don't know how to get the line: Node *code = new Node; to create something new. Am I using the new keyword wrong here?

"dll" is probably not the best name for a doubly-linked-list. It means something entirely different on Windows. :) — selbie
What is the point of temp? Why not use curr? And then why set node->next to be temp? You're effectively making a hole in your list. Also, you've forgotten to update the node behind node. — scohe001
While there are several things wrong with your code as mentioned already, the problem with creating objects in the same address does not happen to me: ideone.com/RX5NyR — eerorika

selbie selbie · Accepted Answer · 2014-08-08T20:48:40

To make the initialization of Node easier, let's add a reasonable constructor that initializes prev and next members to null. That makes things easier for later code.

struct Node {
    Node* prev;
    Node* next;
    T data;
    Node() : prev(nullptr), next(nullptr)
    {

    }
};

There's always four cases to be aware of in a linked list problem. Some of which you got. Inserting into an empty list. Inserting at the front of the list, inserting at the end of the list, and the middle.

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    node->data = value;

    // Case 1: There are no nodes yet
    if (head == nullptr) {
        head = node;
        tail = head;
        return;
    }


    // case 2 - inserting at the head of the list
    if (node->data < head->data)
    {
        node->next = head;
        head = node;
        return;
    }

    // case 3 - inserting at the end of the list
    if (node->data >= tail->data)
    {
        node->prev = tail;
        tail->next = node;
        tail = node;
        return;
    }

    // general case - inserting into the middle
    Node* probe = head;
    while (probe && (node->data >= probe->data))
    {
        probe = probe->next;
    }
    if (probe)
    {
        node->next = probe;
        node->prev = probe->prev;
        probe->prev->next = node;
        probe->prev = node;
        return;
    }

    // error - we shouldnt' reach this point. If we did, it meant the list was out of order to begin with.
    return;
}

Inserting into a Doubly Linked List

2 Answers