Unable to make "head or tail" of a doubly linked list

Question

I can't seem to wrap my head around understanding how to assign the head and tail of a doubly linked list. Trying to get the remove function to work to no avail.

I'm fairly certain the problem lies in the LinkedList::insert() and LinkedList::remove() functions, specifically something to do with the head and tail properties of the LinkedList class.

One of the things I don't quite understand how to get it to work is what to assign to the current variable in the LinkedList::remove() function. If I use head, then it assigns the previous node's value. If I use head.next, I get an exception thrown. The other thing is how (if at all) to get previous to work. Also throws an exception.

I've looked at the other examples in StackOverflow, but was unable to find the answers I need.

Node header file

#pragma once

class Node
{
public:
    int data;
    Node* next;
    Node* previous;
};

Class header file

class LinkedList
{
private:
    int length;
    Node* head;
    Node* tail;

public:
    LinkedList();
    void remove(int deleted);
    void insert(int data);
    void display();
    int getLength();
};

LinkedList C++ file

#include <iostream>
#include "LinkedList.h"
#include "Node.h"

using namespace std;

//Define variables used in the class
LinkedList::LinkedList()
{
    length = 0;
    head = NULL;
    tail = NULL;
}

//Define the remove function
void LinkedList::remove(int deletedNode)
{ 
    struct Node* current = head;
    while (current)
    {
        if (current->data == deletedNode)
        {
            if (current->next == NULL)
            {
                current->previous->next = NULL;
                current = NULL;
            }
            else if (head == NULL)
            {
                current->next->previous = NULL;
                current = NULL;
            }
            else
            {
                current->previous->next = current->next;
                current->next->previous = current->previous;
                current = NULL;
            }
        }
        current = current->next;
    }
}

//Define insert function
void LinkedList::insert(int num1)
{
    Node* node = new Node(); //Create new node
    node->data = num1; //Assign new number to node's data variable
    node->next = head; //Assign the current contents of the head variable to the new node's next pointer
    node->previous = tail; //Assign the current contents of the tail variable to the new node's previous pointer
    head = node; //Assign the new node to the head variable
    tail = node->previous;

    length++; //Increase the list's length by one
}

//Define display function
void LinkedList::display()
{
    Node* curr = this->head;
    int i = 1;
    while (curr)
    {
        cout << "Value of node #" << i << " is " << curr->data << endl;
        curr = curr->next;
        i++;
    }
}

//Define getLength function
int LinkedList::getLength()
{
    return length;
}

Main C++ file

#include <iostream>
#include "LinkedList.h"
#include "Node.h"
#include <time.h>

using namespace std;

int main()
{
    int userRemove = 1;

    LinkedList list;

    // Define & start clock
    clock_t start, end;
    start = clock();

    for (int i = 1; i < 101; i++)
    {
        list.insert(rand() % 101);
    }

    // Display list
    list.display();

    // End clock
    end = clock();

    //Display duration it took to display list
    cout << endl << "It took " << (end - start) << " milliseconds to list & display all nodes." << endl;

    //Display total number of nodes
    int len = list.getLength();
    cout << endl << "# of nodes = " << len << endl;

    //Ask user for node number to remove
    while (userRemove != 0)
    {
        cout << endl << "Please enter the number of the node you wish to delete or press '0' to exit: " << endl;
        cin >> userRemove;
        list.remove(userRemove);
        cout << endl << "The first node containing " << userRemove << " has been removed." << endl;
        //Display list and list length after removal
        list.display();
        cout << endl << "# of nodes = " << len << endl;
    }
}

Answer 1

--Edit 04/04/2023 -- Seems like it wasn't only my C++ that was rusty. My data structures knowledge has also faded :) See comment by user "@Caleth" down below. What I'm describing here is a "loop". Main difference is that in a double linked list, both Head->Prev and Tail->Next points to NULL (There is nothing before the head or after the tail node).

I'd like to begin by saying I'm a C# and .Net peasant, my c++ knowledge is beyond rusty, so I'll try to make my answer as generic as possible.

Looking at your void LinkedList::insert(int num1) I have a few questions:

What happens with the existing head node (let's call it prevHead) next pointer? prevHead->previous should be set you the node you're inserting

Also, is it necessary to set the tail at all? If you are inserting at the beginning you should only need to set tail->next to the new node you are inserting.

in fact this: node->previous = tail; followed by this: tail = node->previous; doesn't seem to be doing anything at all, you're just swapping variable values back and forth.

Your void LinkedList::remove(int deletedNode) function is interesting. Usually, when removing you'd be specifying an "index" or "position". But seems like you're removing any node with a value that matches the passed deletedNode arg. Is that what you really want?

Remember, one of the biggest advantages of doubly linked lists is that for operations like inserting and deleting you only have to adjust the 'prev' and 'next' pointers of the affected nodes.

Answer 2

Since you're doing a doubly-linked list, you forgot to link the former head node back to the newly added node when inserting a new node. As a final step:

if (node->next) {
    node->next->previous = node;
}

Answer 3

When you try to delete the node, you don't actually delete anything. You left that node in memory and you lost address of it. Use:

delete current;

Instead of:

current = NULL;

current is in the function scope and it will released automatically. Lastly, don't forget to decrease the length.

To make head or tail you have to check head or tail initialized or not. If the list is empty, head==NULL/tail==NULL/length==0 statements returns true. Before the insert anything check if list empty or not, then decide to initialize head and tail or if they are already initialized just use them.

Here is a good resource to understand data structures.

Answer 4

In C++ you should use std::vector for list-like data. If you are absolutely sure that a doubly-linked list is the best fit for your data, then you should use std::list. You should never implement these basic data structures yourself for production code! For learning, of course, it is fine.

Answer 5

insert and remove should only be modifying the two nodes that are adjacent to the target.

To avoid having edge cases, you can have head and tail always exist, as sentinels (with no data).

class LinkedList
{
    Node head;
    Node tail;
    // other members
};

LinkedList::LinkedList() : length(0)
{
    head.next = &tail;
    tail.prev = &head;
}

void LinkedList::insert(int num1)
{
    Node* node = new Node{ num1, head.next, &head };
    head.next = node;
    node->next->prev = node;
    ++length;
}

void LinkedList::remove(int deletedNode)
{
    for (Node * current = head.next; current != &tail; current = current->next)
    {
        if (current->data == deletedNode)
        {
            current->next->prev = current->prev;
            current->prev->next = current->next;
            delete current;
            --length;
            return;
        }
    } 
}