Doubly Linked List Implementation [C++]

Question

C++ noob reporting. I'm working on implementing a doubly linked list using two separate classes: one class, called node, containing your standard doubly linked list parameters, and another class, called dList, that contains functions to alter my doubly linked list. Here is my node class:

class node {
  public:
    node *prev;
    node *next;
    int key;
    char type;
};

and here is my dList class:

class dList {
  private:
    node *head; // dummy head
    node *tail; // dummy tail

  public:
    dList() { // default constructor, creates empty list
      cout << "in default constructor" << endl; // to debug
      head = nullptr;
      tail = nullptr;
    }
    // destructor
    ~dList() {
      cout << "in destructor" << endl; // to debug
      node *ptr = head;
      while (ptr != nullptr) {
        delete ptr;
        ptr = ptr->next;
      }
      tail = nullptr;
    }

    // searches list for occurence of int parameter and returns pointer to node containing key
    node *search(int k);

    // outputs all keys that have type equal to character parameter, front to back
    void find(char t);

    // parametrized constructor, initialize list w/ contents of arrays
    dList(int arrayNums[], char arrayChars[], int size);

    // creates new node at front of list
    void addFront(int k, char t);

    // creates new node at back of list
    void addBack(int k, char t);

    // moves node pointed to by parameter to front of list
    void moveFront(node* ptr);

    // moves node pointed to by parameter to back of list
    void moveBack(node* ptr);

    // outputs first int elements of list, starting at front or back depending on char parameter
    void out(int num, char = 'f');

    // splits list in two
    node *split(node* headRef);

    // merges two linked lists
    node *mergeLists(node* first, node* second);

    // performs mergeSort on linked list
    node *mergeSort(node* headRef);

    // peforms an O(NlogN) sort on list; list should be in increasing order based on integer key
    void sort();
};

I have all of my functions figured out, besides the sort() function and all of the functions related to it (split, mergeLists, mergeSort). I'm mainly looking for critiques and improvements. If y'all could look over my code and help me optimize it (condensing and deleting unnecessary lines), as well as help me make sure I'm using pointers correctly, it'd be much appreciated!

Below are my declared functions (excluding any sort related ones):

// parametrized constructor, initialize list w/ contents of arrays
dList::dList(int arrayNums[], char arrayChars[], int size) {
  node *newNode = nullptr;
  //cout << "parametrized constructor called" << endl;
  for (int i = 0; i < size; i++) {
    //cout << "in for loop" << endl;
    if (head == nullptr) {
      //cout << "in first if statement" << endl;
      newNode = new node;
      newNode->key = arrayNums[i];
      newNode->type = arrayChars[i];
      newNode->prev = nullptr;
      newNode->next = nullptr;
      head = newNode;
      tail = head;
    }

    else {
      //cout << "in else statement" << endl;
      newNode = new node;
      newNode->key = arrayNums[i];
      newNode->type = arrayChars[i];
      newNode->prev = tail;
      tail->next = newNode;
      tail = newNode;
    }
  }
}

void dList::addFront(int k, char t) { // creates new node at front of list
  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

  if (head != nullptr) {
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
  }
  else {
    newNode->prev = nullptr;
    newNode->next = nullptr;
    head = newNode;
    tail = nullptr;
  }
}

void dList::addBack(int k, char t) { // creates new node at back of list
  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

  node *ptr = head;

  if (ptr != nullptr) {
    while (ptr->next != nullptr) {
      ptr = ptr->next;
    }
    ptr->next = newNode;
    newNode->next = nullptr;
    newNode->prev = ptr;
  }
  else {
    newNode->next = nullptr;
    newNode->prev = nullptr;
    ptr = newNode;
    tail = ptr;
  }
}

void dList::moveFront(node *ptr) { // moves node pointed to by parameter to front of list
  //node *tempHead = head;
  //node *tempTail = tail;

  if (ptr == head) {
    return;
  }
  else if (ptr == tail) {
    ptr->prev->next = nullptr;
    tail = ptr->prev;
  }
  else {
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
  }

  head->prev = ptr;
  ptr->next = head;
  ptr->prev = nullptr;
  head = ptr;
}

void dList::moveBack(node *ptr) { // moves node pointed to by parameter to back of list
  //node *tempHead = head;
  //node *tempTail = tail;

  if (ptr == tail) {
    return;
  }
  else if (ptr == head) {
    head = ptr->next;
    tail->next = ptr;
    ptr->prev = tail;
    ptr->next = nullptr;
    tail = ptr;
  }
  else {
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
    tail->next = ptr;
    ptr->prev = tail;
    tail = ptr;
  }
}
// searches list for occurence of int parameter and returns pointer to node containing key
node *dList::search(int k) {
  node *ptr = head;
  while (ptr->next != nullptr) {
    if (ptr->key == k) {
      return ptr;
    }
    else {
      ptr = ptr->next;
    }
  }

  return nullptr;
}
// outputs all keys that have type equal to character parameter, front to back
void dList::find(char t) {
  node *ptr = head;
  while (ptr->next != nullptr) {
    if (ptr->type == t) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->next;
    }
    else {
      ptr = ptr->next;
    }
  }
}
// outputs first num elements of list, starting at front or back depending on char parameter
void dList::out(int num, char side) {
  cout << "out() called" << endl;
  if (side == 'b') {
    node *ptr = tail;
    for (int i = 0; i < num; i++) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->prev;
    }
  }
  else {
    node *ptr = head;
    for (int i = 0; i < num; i++) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->next;
    }
  }
}

And here is my main.cpp file I've been using to test:

#include <iostream>
using namespace std;
#include "dList.cpp"
#define SMALL 200
#define MAX 100000
#define ROUNDS 100
int main(){
    int i, x[MAX];
    char ch[MAX];

    for(i=0;i<SMALL;i++) {
      x[i] = (2*SMALL)-i;
      ch[i] = 'a' + (i % 26);
    }
    dList A(x,ch,SMALL), B;
    A.out(10);
    node *tmp = A.search(2*SMALL-8);
    A.moveFront(tmp);
    A.out(10);
    A.moveBack(tmp);
    A.out(10);
    A.find('b');
    A.sort();
    A.out(10);
    A.out(10,'b');
    A.addBack(500,'d');
    A.addFront(501,'z');
    A.out(10);
    A.out(10,'b');
    B.addFront(1,'a');
    B.addBack(2,'b');
    B.out(2);

    for(int j=0; j<ROUNDS; j++){
      cout << endl << "round " << j << endl;
      for(i=0;i<MAX;i++) {x[i] = 2*MAX-i; ch[i] = 'a'+ (i%26);}
      dList A(x,ch,MAX);
      node *tmp = A.search(2*MAX-8);
      A.moveFront(tmp);
      A.moveBack(tmp);
      A.sort();
      A.out(10);
      A.out(10,'b');
    }
}

(As a bonus, if y'all could give me tips on how to implement mergesort for a doubly linked list, I would LOVE it!)

Thanks y'all!

Answer 1

Just a short start on reviewing:

1. You are violating the rule-of-three / rule-of-five:

   dList()
   ~dList()
   

   You are missing at least:

   dlist(const dlist&)
   dlist& operator=(const dlist&)
   

   The defaults provided by the standard are fatally wrong.

   Though assuming at least C++11 you would also want:

   dlist(dlist&&)
   dlist& operator=(dlist&&)
   

2. Kudos for deleting the nodes in the dtor iteratively instead of recusively. But then you commit a use-after-free offence. Fix that by reading the pointer to the next node before freeing the node. Also, there's no use painting the walls just before demolishing the house.

I'm not reviewing the rest of your interface and implementation, aside from saying it seems to be a very leaky abstraction. Maybe work on that?

Answer 2

Design

I would put the Node inside dList as a private class. Its an implementation detail that nobody needs to know about apart from your class.

I would look up how to use a sentinel object. A sentinel is a fake object in your list that truly simplifies the code as you never have to deal with head/tail being null. Have a look at this: https://codereview.stackexchange.com/a/126007/507

The interface is not very standard for a list. You may want to look at the design of the standard containers to see what the standard methods are.

Naming conventions. It is more traditional to use an uppercase first letter for user defined types. Then lower case letter for functions and objects.

  Node(12, 'k');       // Uppercase letter therefore type.
                       // This is creating an object.

  node(12, 'k');       // lowercase letter therefore function
                       // This is calling a function

Code Review

Rule of three

You failed to implement the rule of 3 (or five).

{
    dList  x;
    x.addBack(12, 'g');

    dList  y(x);     // Woops shallow copy of x made
                     // Even though you did not define the copy constructor
}
// BOOM. Code blows up because of double delete on the same pointer.

If you define the copy constructor/assignment operator or destructor then you should probably define all three.

Accessing via deleted pointer

  while (ptr != nullptr) {
    delete ptr;
    ptr = ptr->next;    // You just deleted ptr
                        // This is no longer yours to access and doing
                        // so is UB (the whole page may have been released
                        // back to the OS resulting in a page fault.


                        // Looking from a real world perspective the delete
                        // adds this block back to the memory management
                        // library and could easily overwrite parts of the 
                        // block in the processes. So what you read here
                        // is potentially garbage.
  }

Dry your code

A lot of this code is repeated across both sides of the if statement. Why not remove duplicate code out so it happens first?

if (head == nullptr) {
  //cout << "in first if statement" << endl;
  newNode = new node;
  newNode->key = arrayNums[i];
  newNode->type = arrayChars[i];
  newNode->prev = nullptr;
  newNode->next = nullptr;
  head = newNode;
  tail = head;
}

else {
  //cout << "in else statement" << endl;
  newNode = new node;
  newNode->key = arrayNums[i];
  newNode->type = arrayChars[i];
  newNode->prev = tail;
  tail->next = newNode;
  tail = newNode;
}

Simplify code.

  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

Easier to write as:

    node* newNode = new node {nullptr, nullptr, k, t};

Printing

The normal way to print in C++ is to use operator<<.

std::cout << 5 << "\n";

You can implement this for your class by defining this operator.

std::ostream& operator<<(std::ostream& s, dlist const& object)
{
    object.print(s);  // simplest way to ask object to print itself
                      // to the stream (pass the stream).
    return s;
}

Answer 3

I agree with what the others said, but here are some additional remarks.

1. Use default initialization when possible

   class node {
   public:
       node *prev = nullptr;
       node *next = nullptr;
       int key;
       char type;
   };
   

2. Provide a constructor for your node class that passes key and type

   class node {
   public:
       node(int Key, char Type)
           : key(Key)
           , type(Type)
       {}
   
       node *prev = nullptr;
       node *next = nullptr;
       int key;
       char type;
   };
   

   Lets have a look at how that affects you helper functions addFront first

   void dList::addFront(int k, char t) { // creates new node at front of list
       node *newNode = new node(k, t);
       newNode->next = head;          
       if (head != nullptr) {
           head->prev = newNode;
       }
       head = newNode;
   
       // If your list was constructed with empty arrays you need to set tail too
       if (tail == nullptr) {
           tail = newNode;
       }
   }
   

   Is there any reason you traverse the list in addBack when you have a pointer to tail?

   void dList::addBack(int k, char t) { // creates new node at front of list
       // If there is no head create a shortcut to addFront
       if (head == nullptr) {
           addFront(k,t);
       }
   
       node *newNode = new node(k, t);
       tail->next = newNode
       newNode->prev = tail;
       tail = newNode;
   }
   

3. More a personal preference, but i would rather use a struct that is private to the list than a fully opaque class but whatever.

4. You question is tagged C++ however you use plain C-arrays in the constructor dList(int arrayNums[], char arrayChars[], int size);. Here std::vector would be better. Also think about what happens when one of the arrays is shorter than size?

   dList::dList(const std::vector<int>& arrayNums, const std::vector<char>& arrayChars) {
       if (arrayNums.size() != arrayChars.size()) {
           //Do something here, e.g. throw an exception or whatever you want
       }
   
       for (std::size_t i = 0; i < arrayNums.size(); ++i) {
           addBack(arrayNums[i], arrayChars[i]);
       }
    }