Issue with add method in doubly linked list C++

Question

I'm taking a data structures course and the current assignment is to create a simple queue class that is built from an existing doubly linked list class.

Sounds easy enough, but I'm rather rusty, especially with c++ and I'm having difficulty getting the doubly linked list code from the book working. The code makes sense (except for the add method), but the program crashes when I try to call addFront().

I have a feeling I'm making a foolish mistake, but I obviously need some assistance and explanation if I can't get example code to run correctly.

The code the professor suggested we use is on page 127 of Data Structures and Algorithms in C++ by Michael T. Goodrich. You can actually view this page using Amazon's look inside feature. http://amzn.com/0470383275

The files I'm trying to compile can be found here: https://dl.dropboxusercontent.com/u/12660663/DLinkedList.zip

This is the author's add front method, it calls the add() method where I believe the problem lies.

void DLinkedList::addFront(const Elem& e)   // add to front of list
{ add(header->next, e); }

This is the add function exactly how it is written in the book and in the professors MS Word document full of example code (completely in Comic Sans by the way):

// Insert new node before v
void DLinkedList::add(DNode* v, const Elem& e) 
{
DNode* u = new DNode;  u->elem = e;    // create a new node for e
u->next = v;                           // link u in between v
u->prev = v->prev;                     // ...and v->prev
v->prev->next = v->prev = u;

}

This code makes sense except for that last line, I find it difficult to follow.

This is all I'm doing in main to make the program crash (keep in mind that the project is actually to use this class to create another class, so I just want to get it working):

#include "DLinkedList.h"

int main()
{
    DLinkedList list;

    Elem s;
    s = "Jim";

    list.addFront(s);    // This and addBack(s) causes the program to crash,
                         //   doesn't crash if I remove this line  
    return 0;
}

Here is the header file:

#include <string>
#include <iostream>
using namespace std;

#ifndef DLINKEDLIST_H_
#define DLINKEDLIST_H_

// Code Fragment 3.22
typedef string Elem;                // list element type
class DNode {                   // doubly linked list node
private:
  Elem elem;                    // node element value
  DNode* prev;              // previous node in list
  DNode* next;              // next node in list
  friend class DLinkedList;         // allow DLinkedList access
};

// Code Fragment 3.32
class DLinkedList {             // doubly linked list
public:
  DLinkedList();                // constructor
  ~DLinkedList();               // destructor
  bool empty() const;               // is list empty?
  const Elem& front() const;            // get front element
  const Elem& back() const;         // get back element
  void addFront(const Elem& e);     // add to front of list
  void addBack(const Elem& e);      // add to back of list
  void removeFront();               // remove from front
  void removeBack();                // remove from back
private:                    // local type definitions
  DNode* header;                // list sentinels
  DNode* trailer;
protected:                  // local utilities
  void add(DNode* v, const Elem& e);        // insert new node before v
  void remove(DNode* v);            // remove node v
};

#endif /* DLINKEDLIST_H_ */

I tried tagging this with 'homework' but apparently that isn't a thing anymore.

Although this is homework, my assignment is to reuse this already written code to make a new class.

Thanks in advance, I greatly appreciate any suggestions and explanations.

Michael

Answer 1

GCC 4.7.3 generates a warning for the code you find confusing. You can simplify it (and remove the warning) as follows:

void DLinkedList::add(DNode* v, const Elem& e) {
  DNode* u = new DNode;  u->elem = e;     // create a new node for e
  u->next = v;                            // link u in between v
  u->prev = v->prev;                      // ...and v->prev
  v->prev->next = u;
  v->prev = u;
}

Finally, your code is segfaulting because you did not copy Goodrich's destructor faithfully. It should be:

DLinkedList::~DLinkedList()
{
  while (!empty()) removeFront();
  delete header;
  delete trailer;
}

Answer 2

Just answering one of your questions for now:

void DLinkedList::add(DNode* v, const Elem& e) 
{
    DNode* u = new DNode;  u->elem = e;    // create a new node for e
    u->next = v;                           // link u in between v
    u->prev = v->prev;                     // ...and v->prev
    v->prev->next = v->prev = u;
}

This code makes sense except for that last line, I find it difficult to follow.

Imagine *v is a node in the linked list:

... <--[-prev NODE next-]--> <--[-prev *v next-]--> <--[-prev NODE next-]--> ...

What the code above does is prepare a new node *u:

[-prev *u next-]          // DNode* u = new DNode;
[-prev *u elem=e next-]   // u->elem = e;

            [-prev *u elem=e next=v-]-   // u->next = v;
                                     \
                                      v
... <--[-prev NODE next-]--> <--[-prev *v next-]--> <--[-prev NODE next-]--> ...

         [-prev *u elem=e next=v-]-->   // u->prev = v->prev;
             \                       \
              v                       v
... <--[-prev NODE next-]--> <--[-prev *v next-]--> <--[-prev NODE next-]--> ...


         [-prev *u elem=e next=v-]-->   // v->prev->next = v->prev = u;
             \          ^   ^        \
              v          \   \        v
... <--[-prev NODE next-]-\   \-[-prev *v next-]--> <--[-prev NODE next-]--> ...

So, the last v->prev->next = v->prev = u; breaks the link between node *v and the node before it in the list, making:

• v->prev point to *u such that *u is found previous to *v during backward traversal, and
• v->prev->next (the once-previous-to-*v's link to the next node) point to *u

Consequently, the new ordering through the list is: node-that-used-to-be-immediately-previous-to-*v -> *u -> *v ....

Answer 3

It is confusing to me that the last line of add() :

void DLinkedList::add(DNode* v, const Elem& e) {
    // ...
    v->prev->next = v->prev = u;
}

According to rule that assignment is done right to left, it should be simplified to :

void DLinkedList::add(DNode* v, const Elem& e) {
    // ...
    v->prev = u;
    v->prev->next = u;
}

Instead of what Adam Burry said:

void DLinkedList::add(DNode* v, const Elem& e) {
  //...
  v->prev->next = u;
  v->prev = u;
}

But it seems to me that I'm going wrong. After Google for a while I found out that in C++ when doing a chained assignment:

a = b = c = d;
// simplify to:
// a = d
// b = d
// c = d

And not

// c = d
// b = c
// a = b