0

I wrote a Double linked list class which has insertAtStart, insertAtEnd, removeFromStart, removeFromEnd member functions. Check the code below

class Node {
    public:
        int val;
        Node *next;
        Node *prev;

        Node(int v)
            : val(v),
              next(nullptr),
              prev(nullptr) {}
};


#include<iostream>
using namespace std;

#include "../node.h"

class LinkedList {
    private:
        Node* start;
        Node* end;

    public:
        LinkedList(): start(nullptr), end(nullptr) { }

        void insertAtStart(int val) {
            Node* n = new Node(val);
            if(start == nullptr) {
                start = n;
                end = n;
            } else {
                n->next = start;
                start = n;
            }
        }

        void insertAtEnd(int val) {
            Node* n = new Node(val);
            if(end == nullptr) {
                end = n;
                start = n;
            } else {
                end->next = n;
                n->prev = end;
                end = n;
            }
        }

        void removeFromStart() {
            if(start == nullptr) return;
            if(start == end) {
                start = end = nullptr;
                return;
            }
            start = start->next;
            start->prev = nullptr;
        }

        void removeFromEnd() {
            if(end == nullptr) return;
            if(start == end) {
                start = end = nullptr;
                return;
            }
            end = end->prev;
            end->next = nullptr;
        }

        void printList() {
            Node *ptr = start;
            while(ptr != nullptr) {
                cout << ptr->val << " ";
                ptr = ptr->next;
            }
            cout << endl;
        }
};

I tested the above code using the following main function and it worked perfectly

#include "double-linked-list.h"

int main() {
    LinkedList l = LinkedList();
    l.insertAtStart(1);
    l.insertAtStart(2);
    l.insertAtStart(3);
    l.insertAtStart(4);
    l.insertAtStart(5);
    l.insertAtEnd(6);
    l.insertAtEnd(7);
    l.insertAtEnd(8);
    l.insertAtEnd(9);
    l.insertAtEnd(10);
    l.printList();
    l.removeFromStart();
    l.printList();
    l.removeFromStart();
    l.printList();
    l.removeFromEnd();
    l.printList();
    l.removeFromEnd();
    l.printList();
    return 0;
}

output:

Inserting 1 at start
Linked list: 1
Inserting 2 at start
Linked list: 2 1
Inserting 3 at start
Linked list: 3 2 1
Inserting 4 at start
Linked list: 4 3 2 1
Inserting 5 at start
Linked list: 5 4 3 2 1
Inserting 6 at end
Linked list: 5 4 3 2 1 6
Inserting 7 at end
Linked list: 5 4 3 2 1 6 7
Inserting 8 at end
Linked list: 5 4 3 2 1 6 7 8
Inserting 9 at end
Linked list: 5 4 3 2 1 6 7 8 9
Inserting 10 at end
Linked list: 5 4 3 2 1 6 7 8 9 10
Removing from start
Linked list: 4 3 2 1 6 7 8 9 10
Removing from start
Linked list: 3 2 1 6 7 8 9 10
Removing from end
Linked list: 3 2 1 6 7 8 9
Removing from end
Linked list: 3 2 1 6 7 8

I now, wrote a Queue class that is derived from the above linked list class

#include "../double-linked-list/double-linked-list.h"

class Queue {
    private:
        LinkedList q;
    public:
        Queue() {}

        void enqueue(int val) {
            q.insertAtStart(val);
        }

        void dequeue() {
            q.removeFromEnd();
        }

        void printQueue() {
            q.printList();
        }
};

and the following main function to test it

#include "queue.h"

int main() {
    Queue q = Queue();
    q.enqueue(1);
    q.printQueue();
    q.enqueue(2);
    q.printQueue();
    q.enqueue(3);
    q.printQueue();
    q.enqueue(4);
    q.printQueue();
    q.enqueue(5);
    q.printQueue();
    q.dequeue();
    q.printQueue();
    q.dequeue();
    q.printQueue();
}

enqueue seems to work perfectly but dequeue doesn't. It's not even printing anything after dequeue.

Output:

Enqueuing 1
1
Enqueuing 2
2 1
Enqueuing 3
3 2 1
Enqueuing 4
4 3 2 1
Enqueuing 5
5 4 3 2 1
Denqueuing

In an attempt to debug, I put a cout statement in removeFromEnd function in LinkedList.

void LinkedList::removeFromEnd(){
    if(end == nullptr) return;
    if(start == end) {
        start = end = nullptr;
        return;
    }
    end = end->prev;
    cout << "print statement 1";
    end->next = nullptr;
    cout << "print statement 2";
}

Now, when I ran queue's main function again, print statement 1 is printing in console but the 2nd one isn't. I'm not able to understand why. Can someone pls help me figure out what I'm doing wrong?

EDIT:

After reading the comments I made changes to the following functions

void insertAtStart(int val) {
    Node* n = new Node(val);

    // If start and end are null
    if(start == nullptr && end == nullptr) {
        start = end = n;
    }
    // There is at least 1 node in the list
    else {
        n->next = start;
        start->prev = n;
        // There is only one node in the list
        if(start->next == nullptr) {
            end->prev = n;
        }
        start = n;
    }
}

void insertAtEnd(int val) {
    Node* n = new Node(val);

    // If start and end are null
    if(start == nullptr && end == nullptr) {
        start = end = n;
    }
    // There is at least 1 node in the list
    else {
        n->prev = end;
        end->next = n;
        // There is only one node in the list
        if(end->prev == nullptr) {
            start->next = n;
        }
        end = n;
    }
}

This worked. I posted the entire Linked List class as answer if interested.

troglodyte07
  • 3,598
  • 10
  • 42
  • 66
  • 3
    Should your `Queue` really *inherit* from `LinkedList` and not only *contain* a `LinkedList`? Remember that inheritance is an *is-a* relationship, and a queue (even if implemented as one) isn't a linked list. – Some programmer dude Nov 26 '19 at 09:41
  • As for your problem, your `remove` functions doesn't have any null-pointer checks. What happens if `removeFromEnd` or `removeFromStart` removes the last node in the list (i.e. when `start == end`)? – Some programmer dude Nov 26 '19 at 09:44
  • @Someprogrammerdude Was my first thought, too. On the other hand, the inheritance is *private*, so possibly rather a matter of taste? – Aconcagua Nov 26 '19 at 09:44
  • @Aconcagua And that's an even better indicator that composition should be used instead of inheritance. – Some programmer dude Nov 26 '19 at 09:47
  • You have two memory leaks, as you don't ever delete the node to be removed. On the other hand, if you *did*, you'd delete by accident the entire list, as you don't change the next pointer of the start element (when removing from front) or prev pointer of the end element (when removing from back). – Aconcagua Nov 26 '19 at 09:47
  • Off-topic: You should get used to use constructor's initialiser list (not to be confused with `std::initializer_list`): `LinkedList() : start(nullptr), end(nullptr) { }`. While in given case not really an issue, with complex members, you prefer direct initialisation by value in favour of default initialisation + additional assignment. Some types (references, non-default-constructible types, const members) *only* can be initialised that way. – Aconcagua Nov 26 '19 at 09:51
  • @Someprogrammerdude I changed the Queue to have a linked list member instead of inheriting from linked list. I also changed the code to handle the edge cases you mentioned. I updated it in the question. Pls have a look. I still face the same problem. Dequeue not working. The second print statement is not printing. – troglodyte07 Nov 26 '19 at 09:55
  • `delete next; delete prev;` will end up in multiple deletion as soon as you have more than one node (undefined behaviour!): When next is deleted, it will delete all its successors recursively. As soon as there isn't one any more, last node will try to delete predecessor. But of that one, destruction started already. It might even happen (if tail call optimisation does not occur; otherwise you might end up in endless loop) that you end up in stack-overflow due to endless recursion as when predecessor gets deleted again, it will at first try to delete successor *again*... – Aconcagua Nov 26 '19 at 09:56
  • Off-topic: About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... – Aconcagua Nov 26 '19 at 10:01
  • @Aconcagua I made some changes in the code, considering what Some programmer dude suggested. Also, I removed the destructor from Node class. And I still face the same problem. It's quite weird. Can you have a look pls. – troglodyte07 Nov 26 '19 at 10:08

2 Answers2

2

For starters the program has memory leaks because you are not deleting allocated nodes.

As for your problem then this function

    void insertAtStart(int val) {
        Node* n = new Node(val);
        if(start == nullptr) {
            start = n;
            end = n;
        } else {
            n->next = start;
            start = n;
        }
    }

is invalid. It does not refresh the data member end->prev (more precisely start->prev) when a new node is added to the beginning of the list. That is end->prev is always equal to nullptr.

Rewrite the function at least like

    void insertAtStart(int val) {
        Node* n = new Node(val);
        if(start == nullptr) {
            start = n;
            end = n;
        } else {
            n->next = start;
            start->prev = n; // <===
            start = n;
        }
    }
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • You have been faster than me ;) Little typo: it does not refresh `start->prev` (before start is updated) which leads to *all* nodes not having a `prev` member set. – Aconcagua Nov 26 '19 at 10:15
0

After reading the comments and answer by Vlad from Moscow, I made the following changes to my double linked list class and it worked.

#include<iostream>
#include "../node.h"

class LinkedList {
    private:
        Node* start;
        Node* end;

    public:
        LinkedList(): start(nullptr), end(nullptr) { }

        void insertAtStart(int val) {
            Node* n = new Node(val);

            // If the list is empty
            if(start == nullptr && end == nullptr) {
                start = end = n;
            }
            // There is at least 1 node in the list
            else {
                n->next = start;
                start->prev = n;
                // There is only one node in the list
                if(start->next == nullptr) {
                    end->prev = n;
                }
                start = n;
            }
        }

        void insertAtEnd(int val) {
            Node* n = new Node(val);

            // If the list is empty
            if(start == nullptr && end == nullptr) {
                start = end = n;
            }
            // There is at least 1 node in the list
            else {
                n->prev = end;
                end->next = n;
                // There is only one node in the list
                if(end->prev == nullptr) {
                    start->next = n;
                }
                end = n;
            }
        }

        void removeFromStart() {
            if(start == nullptr) return;
            if(start->next == nullptr) {
                start = end = nullptr;
                return;
            }
            start = start->next;
            start->prev = nullptr;
        }

        void removeFromEnd() {
            if(end == nullptr) return;
            if(end->prev == nullptr) {
                start = end = nullptr;
                return;
            }
            end = end->prev;
            end->next = nullptr;
        }

        void printList() {
            Node *ptr = start;
            while(ptr != nullptr) {
                std::cout << ptr->val << " ";
                ptr = ptr->next;
            }
            std::cout << std::endl;
        }
};
troglodyte07
  • 3,598
  • 10
  • 42
  • 66