2
\$\begingroup\$

I made this C++ doubly circular linked list implementation and it seems to work right, handle everything well, and not have any errors. However, I've been working with it for a while and would like some fresh eyes to take a look and see if I am missing anything large or if my code contains any 'gotchas'.

Side note: I ran valgrind on several tests of this implementation and never got any memory leaks so I suspect it is handling that end of this correctly.

CLL.h

#ifndef CLL
#define CLL

class CircularLinkedNode {
public:
    int info;
    CircularLinkedNode *next, *prev;

    CircularLinkedNode() {
        next = prev = this;
    }

    CircularLinkedNode(int num) {
        info = num;
        next = prev = this;
    }

    CircularLinkedNode(int nu, CircularLinkedNode *ne, CircularLinkedNode *pre) {
        info = nu;
        //auto put new node in the middle of next and previous
        next = ne;
        prev = pre;
        prev->next = this;
        next->prev = this;
    }

    ~CircularLinkedNode() {
        //when deleted, seal the gap
        //prev->next = next;
        //next->prev = prev;
    }
};

class CircularLinkedList {
private:
    CircularLinkedNode *head, *tail;
public:
    CircularLinkedList() {
        head = tail = 0;
    }

    ~CircularLinkedList();

    bool isEmpty() const {
        return head == 0;
    }

    void addToHead(int);
    void addToTail(int);
    int removeFromHead();
    int removeFromTail();
    void remove(int);
    bool isInList(int) const;


};

#endif

CLL.cpp

#include <iostream>
#include "CLL.h"


CircularLinkedList::~CircularLinkedList() {
if (isEmpty()) {
    return;
}
if(head == tail) {
    delete head;
    head = tail = 0;
    return;
}

    CircularLinkedNode *tmp = head->next;
    delete head;
    while(tmp != tail) {
        head = tmp;
        tmp = tmp->next;
        delete head;
    }
    delete tail;

}

void CircularLinkedList::addToHead(int n) {
    isEmpty() ? head = tail = new CircularLinkedNode(n) : head = new     CircularLinkedNode(n, head, tail);
}

void CircularLinkedList::addToTail(int n) {
    isEmpty() ? tail = head = new CircularLinkedNode(n) : tail = new CircularLinkedNode(n, head, tail);
}

int CircularLinkedList::removeFromHead() {
    if(isEmpty()) {
        return 0;
    }

    int el = head->info;
    if(head == tail) {
        delete head;
        head = 0;
        return el;
    }

    CircularLinkedNode *tmp = head;
    head->prev->next = head->next;
    head->next->prev = head->prev;
    head = head->next;
    std::cout << "delete" << std::endl;
    delete tmp;
    return el;
}

int CircularLinkedList::removeFromTail() {
    if(isEmpty()) {
        return 0;
    }

    int el = tail->info;
    if(head == tail) {
        delete tail;
        tail = 0;
        return el;
    }
    CircularLinkedNode *tmp = tail;
    tail->prev->next = tail->next;
    tail->next->prev = tail->prev;
    tail = tail->prev;
    std::cout << "delete" << std::endl;
    delete tmp;
    return el;
}

void CircularLinkedList::remove(int n) {
    if (!isEmpty()) {
        if (head->info == n) {
            removeFromHead();
            return;
        } else if (tail->info == n) {
            removeFromTail();
            return;
        } else {
            CircularLinkedNode *tmp;
            for (tmp = head; tmp != tail && !(tmp->info == n); tmp = tmp->next);
            if(tmp != tail) {
                tmp->prev->next = tmp->next;
                tmp->next->prev = tmp->prev;
                delete tmp;
            }
        }

    }
}

bool CircularLinkedList::isInList(int el) const {
    CircularLinkedNode *tmp;
    for (tmp = head; tmp != tail && !(tmp->info == el); tmp = tmp->next);
    return (tmp->info == el);
}
\$\endgroup\$
  • \$\begingroup\$ Be aware that because you've posted two similar implementations at the same time, you may receive the same advice for both. If you don't want to hear anything twice, then you can just have one reviewed at a time. \$\endgroup\$ – Jamal Sep 12 '15 at 5:18
2
\$\begingroup\$

Heads and tails

I got confused reading this code because in my mind, a circular list doesn't have a tail. Or at least, the tail is the same as the head.

The code appears to be correct, but you could have only kept a head pointer. Anywhere where you use tail, you could essentially replace that with head->prev and get the same functionality.

\$\endgroup\$
  • \$\begingroup\$ Yes I was wondering how exactly I should handle this it doesn't make too much sense to carry a tail around and what not \$\endgroup\$ – Dominic Farolino Sep 14 '15 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.