Explore our sites

Stack Exchange
tour help
Take the tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite
1

I have implemented a Doubly Linked List in C++. I have tested it and everything works as expected, but I am not sure if my copy constructor and assignment operator perform a Deep Copy. Can someone tell whether I am doing a shallow or deep copy. Also, just by looking at my code, does my destructor seem to work properly? Also, I think I am leaking memory. Can anybody confirm. I will run valgrind as soon as I get a chance.

#include <iostream>

template <typename T>
class list {

 public:

    list();                                   // constructor
    list(const list &l);                      // copy constructor
    list &operator=(const list &l);           // assignment operator
    ~list();                                  // destructor

    // Returns number of elements in the list
    unsigned size();

    // Returns true if the list is empty, false otherwise.
    bool isEmpty() const;

    // Inserts element to front of list
    void insertFront(const T &val);

    // Inserts element to the end of list
    void insertBack(const T &val);

    // Returns the values of the front element in the list
    T front();

    // Returns the value of the back element of the list.
    T back();

    // Deletes the front element of the list and returns its value
    void removeFront();

    // Deletes the back element of the list and returns its value
    void removeBack();

    // Prints each element of the list in order
    void printForward();

    // Prints each element of the list in reverse order
    void printReverse();

 private:
    struct node {
      node   *next;
      node   *prev;
      T      value;
    };

    node   *first; // The pointer to the first node
    node   *last;  // The pointer to the last node
    unsigned length; // holds number of elements in the list

    // Initializes empty list
    void createEmpty();

    // Removes all of the elements in the list
    void removeAll();

    // Makes copy of all of the elements in the list
    void copyAll(const list &l);

};

template <typename T>
void list<T>::createEmpty() {
  first = nullptr;
  last = nullptr;
  length = 0;
}

template <typename T>
void  list<T>::removeAll() {
  while (!isEmpty()) {
    removeFront();
  }
}

template <typename T>
void list<T>::copyAll(const list &l) {
  node *iterator = l.first;
  while (iterator) {
    T obj = iterator->value;
    insertBack(obj);
    iterator = iterator->next;
  }
}

template <typename T>
unsigned list<T>::size() {
  return length;
}

template <typename T>
bool list<T>::isEmpty() const{
  return (first == nullptr && last == nullptr);
}

template <typename T>
void list<T>::insertFront(const T &val) {
  length++;
  node *newNode = new node;
  new (&(newNode->value)) T(val);
  newNode->next = first;
  newNode->prev = nullptr;
  if (isEmpty()) first = last = newNode;
  else {
    first->prev = newNode;
    first = newNode;
  }
}

template <typename T>
void list<T>::insertBack(const T &val) {
  length++;
  node *newNode = new node;
  new (&(newNode->value)) T(val);
  newNode->next = nullptr;
  newNode->prev = last;
  if (isEmpty()) first = last = newNode;
  else {
    last->next = newNode;
    last = newNode;
  }
}

template <typename T>
T list<T>::front() {
  return first->value;
}

template <typename T>
T list<T>::back() {
  return last->value;
}

template <typename T>
void list<T>::removeFront() {
  if (isEmpty()) return;
  length--;
  node *removedNode = first;
  first = first->next;
  if (first) first->prev = nullptr;
  else first = last = nullptr;
  delete removedNode;
  return;
}

template <typename T>
void list<T>::removeBack() {
  if (isEmpty()) return;
  length--;
  node *removedNode = last;
  last = last->prev;
  if (last) last->next = nullptr;
  else first = last = nullptr;
  delete removedNode;
  return;
}

template <typename T>
list<T>::list() {
  createEmpty();
}

template <typename T>
list<T>::list(const list &l) {
  createEmpty();
  copyAll(l);
  return;
}

template <typename T>
list<T>& list<T>::operator= (const list &l)
{
    if (this != &l) {
        removeAll();
        copyAll(l);
    }
    return *this;
}

template <typename T>
list<T>::~list() {
  removeAll();
}

template <typename T>
void list<T>::printForward() {
  if (isEmpty()) {
    std::cout << "List is empty\n"; 
    return;
  }
  node *head = first;
  while (head) {
    std::cout << head->value << " ";
    head = head->next;
  }
  std::cout << "\n";
}

template <typename T>
void list<T>::printReverse() {
  if (isEmpty()) {
    std::cout << "List is empty\n"; 
    return;
  }
  node *tail = last;
  while (tail) {
    std::cout << tail->value << " ";
    tail = tail->prev;
  }
  std::cout << "\n";
}
share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

There's a few stylistic or design things that I noticed, but please pay special attention to the first two (especially the first item). The first two are not style or design related but rather actual bugs that are very likely to happen (well, the second one not so much).

NOTE: This item is a major bug. It's a "this code could never actually be used" level bug.

Why are you placement-new'ing on top of the default-constructed element of node? This is unnecessary unless you're trying to get around some rather odd aversion to a copy constructor or assignment operator.

If you're going to do it this way (and I highly suggest that you don't), you need to manually destruct the element ((newNode->value).~T()) before you placement new over it.

To illustrate the problem, imagine that your're containing a type that sets up some kind of resources in its constructor. As the destructor never gets called for the initial member of node (the one that gets created when node is created), those resources will leak.

I would just pass the object to node through a constructor and let the compiler work its magic before trying to unnecessarily placement-new things:

struct node {
    T value;
    node* next;
    node* prev;
node(const T& val, node* const next = nullptr, node* const prev = nullptr)
    : value(val), next(next), prev(prev)
{ }
};

When you're dealing with memory details, you must be very conscious of exceptions.

In particular, if your new statements throw exceptions after your length++ statements, the length is then incorrect. Luckily the solution is simple: just allocate the memory before incrementing length.

Your indenting is inconsistent (4 spaces sometimes, and 2 spaces others)

The void returns in removeFront and removeBack that do not affect control flow are a bit odd.

front and back could (and probably should) return a reference instead of a copy (as all of the standard library containers do). Note that you would then want two versions: a const one that returns a const reference, and a non-const one that returns a mutable reference.

You've implemented more of a deque than a list. How do you iterate over the list?

I suggest going the style of the standard library and making iterators.

As this is just an academic exercise (if not, use std::list), there's no need to put in all of the effort, but if you wanted, you could even do standard style iterators: this and this should prove helpful if you go this route.

This will allow you to iterate over the list, and, provided you write a iterator insert(iterator, const T&) method, your insertFront and insertBack methods become trivial (insert(end(), value) for example).

Your printing methods don't particularly belong in the class.

What if instead of printing a message when the list is empty, I want to do nothing? What if instead of a space separator, I want a newline? There's so many decisions that you've hard coded that it makes the method useless to a consumer of the class. Let consumers of the class handle output formatting.

(Fun bonus with iterators: just std::copy into a std::ostream_iterator and you have your print methods already written.)

createEmpty() shouldn't exist. That should be part of initialization lists.

share|improve this answer
 
I would totally emphasis the point on the placement new problem. This is not just a design flaw but an actual bug. Without the call to ~T() we have potential leak issues and undefined behavior. –  Loki Astari May 22 at 14:45
 
@LokiAstari Good point; I have edited to make it more clear that it's not only a bug but a rather serious one. –  Corbin May 22 at 20:35
 
Thanks for this. The printing statements were there so I could see what the list looks like. Kind of for debugging purposes. I use createEmpty() in the copy constructor. Should I just set those values myself? –  OGH May 23 at 0:07
 
@OGH I should have explained that item a bit better. I'm just pushing (biased) style habits on you. With primitive types, it makes no difference, but with objects as members, assignment via initialization list constructs into the object rather than using the assignment operator. That means initialization list usage saves a wasted default construction and doesn't require a operator=. Also, with a reference as a member, you must use an initialization list. In this situation, neither of these reasons apply, but I like to always use initialization lists as a habit to make sure to avoid them. –  Corbin May 23 at 1:38
add comment
up vote 3 down vote

Use the copy and swap idium for assignment operator:

template <typename T>
list<T>& list<T>::operator= (const list &l)
{
    if (this != &l) {
        removeAll();
        copyAll(l);
    }
    return *this;
}

// Easier to write as 
template <typename T>
list<T>& list<T>::operator= (list l) // Pass by value to generate copy.
{
    l.swap(*this);                   // Swap with parameter
    return *this;
}                                    // Parameter destroyed
                                     // Taking the old list with it.

The trouble with your versions is you are modifying the local object before you know that the copy has worked. This mean you are not in compliance with "Strong Exception guarantee" (you are only providing the basic guarantee).

If you add a sentinel value then you can make your code much less complicated as you don't need to worry about NULL values.

ie.

// No tail needed.
// With a sentinel the list is circular.
// head->prev       == sentinal
// head->prev->prev == tail
// list is empty then =>   head->prev == head

list::list()
{
    size = 0;
    head = new Node;
    head->next = head;
    head->prev = head;
}

void list::addHead(T val)
{
     Node* n = new Node(val);
     n->next          = head;
     n->prev          = head->prev;

     n->prev->next    = n;
     head->prev       = n;

     head             = n;
     ++size;
}

void list::removeHead()
{
    if (size == 0)
    {   return;  // Empty list just contains the sentinal
    }
    Node* old        = head;

    head             = head->next;
    old->prev->next  = head;
    head->prev       = old->prev;
    --size;

    delete old;
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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