C++ implementation of a linked list

Question

Can someone please review this code and provide comments?

• Please comment on error handling

• Is it right to do like this in method LinkedList::InsertFront()?

  Node *node = node->CreateNode(key);
  

#include<stdio.h>
#include<stdlib.h>
#include<iostream>

class LinkedList{
public:
   LinkedList(){
      head = NULL;
      tail = NULL;
   };
   ~LinkedList(){
      Node *temp;
      while( head!=NULL ) {
         temp = head;
         head = head->next;
         delete temp;
      }
   }
   void InsertFront(int key);       /*Insert a node in head of the list*/
   void InsertBack(int key);        /*Insert a node in end of the list*/
   int TopBack();                   /*Get tail node - complexity-O(1) */
   int TopFront();                  /*Get head node - complexity-O(1) */
   void PopBack();                  /*Remove the first element in list.complexity-O(n)*/
   void PopFront();                 /*Remove the first element in list.complexity-O(1) */
   void FindNode(int key);          /*Find node O(n)*/
   void DeleteNode(int key);        /*Delete first matching  node of a given key.complexity-O(n)*/
   void PrintList();
private:
   struct Node {
      int item;
      Node *next;
      Node *CreateNode(int key){
         Node *node = new Node();
         if(!node)
            return NULL;
         node->next = NULL;
         node->item = key;
      }
   };
   Node *head;
   Node *tail;
};

/*Insert a node in head of the list*/
void
LinkedList::InsertFront(int key) {
   Node *node = node->CreateNode(key);
   if(!node)
   {
      std::cout << "ERR: Failed to allocate new node \n";
      return;
   }
   if(head != NULL){
      node->next = head;
   } else {
      tail = node;
   }
   head = node;
}

/*Insert a node in end of the list*/
void
LinkedList::InsertBack(int key) {
   Node *node = node->CreateNode(key);
   if(!node)
   {
      std::cout << "ERR: Failed to allocate new node \n";
      return;
   }
   if(!head) {
      head = node;
   } else {
      tail->next = node;
   }
   tail = node;
}

/*Get tail node - complexity-O(1) */
int
LinkedList::TopBack(){
   if(!tail) {
      std::cout << "ERR: List is empty\n";
      return -1;
   }
   return tail->item;
}

/*Get head node - complexity-O(1) */
int
LinkedList::TopFront(){
   if(!head) {
      std::cout << "ERR: List is empty\n";
      return -1;
   }
   return head->item;
}

/* Remove the first element in list.  complexity-O(n) */
void
LinkedList::PopBack(){
   if(!tail){
      std::cout << "ERR: List is empty to PopBack \n";
      return;
   }
   if(head == tail)
   {
      std::cout << "popback item is - " << head->item << "\n";
      delete head;
      head = tail = NULL;
      return;
   }
   Node *temp = head;
   while(temp->next!=tail) {
      temp = temp->next;
   }
   std::cout << "popback item is - " << tail->item << "\n";
   delete tail;
   tail = temp;
   tail->next = NULL;
   return;
}

/* Remove the first element in list.  complexity-O(1) */
void
LinkedList::PopFront(){
   if(!head){
      std::cout << "ERR: List is empty to Popfront \n";
      return;
   }
   if(head == tail)
      tail = NULL;
   std::cout << "popfront  item is - " << head->item << "\n";
   Node *temp = head;
   head = head->next;
   delete temp;
   return;
}

/* Find node */
void
LinkedList::FindNode(int key) {
   Node *temp = head;
    while( temp != NULL ) {
      if(temp->item == key) {
         std::cout << "Item found in list \n";
         return;
      }
      temp = temp->next;
   }
   std::cout << "Item not found in list \n";
}

/*Delete first matching  node of a given key*/
void
LinkedList::DeleteNode(int key) {
   Node *node,*prev;
   node = head;
   while(node != NULL){
      if(node->item == key)
         break;
      prev = node;
      node = node->next;
   }
   if(node == NULL)
   {
      std::cout << "Item not found in list \n";
      return;
   }
   if(node == head){
      if(node == tail){
         std::cout << " Deleting Node with item " << node->item  << " - only node available in list \n";
         delete node;
         head = tail = NULL;
         return;
      }
      prev = head;
      head = head->next;
      std::cout << " Deleting Node with item " << prev->item  << " - head node of list\n";
      delete prev;
      return;
   }
   if(node == tail){
      prev->next = NULL;
      std::cout << " Deleting Node with item " << tail->item  << " - tail node of list\n";
      delete tail;
      tail = prev;
      return;
   }
   prev->next = node->next;
   std::cout << " Deleting Node with item " << node->item  << " -  middle  node of list\n";
   delete node;
   return;
}

/*Print whole list*/
void
LinkedList::PrintList() {
   Node *temp = head;
    while( temp != NULL ) {
      std::cout << temp->item << "\t";
      temp = temp->next;
   }
   std::cout << "\n";
}


/* Test code */
void
testlist( LinkedList &new_list ){
   new_list.InsertFront(10);
   new_list.PrintList();
   new_list.InsertFront(50);
   new_list.PrintList();
   new_list.InsertFront(20);
   new_list.PrintList();
   new_list.InsertBack(60);
   new_list.PrintList();
   std::cout << "last node - " << new_list.TopBack() << "\n";
   std::cout << "First  node - " << new_list.TopFront() << "\n";
   new_list.PrintList();
   new_list.PopBack();
   new_list.PrintList();
   new_list.PopFront();
   new_list.PrintList();
   new_list.PopFront();
   new_list.PrintList();
   new_list.PopFront();
   new_list.PrintList();
   new_list.FindNode(70);
   new_list.PrintList();
   new_list.InsertBack(60);
   new_list.PrintList();
   new_list.InsertFront(10);
   new_list.PrintList();
   new_list.DeleteNode(60);
   new_list.PrintList();
   new_list.InsertBack(60);
   new_list.PrintList();
   new_list.InsertFront(70);
   new_list.PrintList();
   new_list.DeleteNode(10);
   new_list.PrintList();
}

void
insert_random_nos(LinkedList &new_list){
   int i;
   for(i=133;i>11;i=i-7) {
      new_list.InsertFront(i%23);
   }
   new_list.PrintList();
}


int main() {
   LinkedList new_list;
   new_list.InsertFront(70);
   testlist(new_list);
   insert_random_nos(new_list);
   new_list.PrintList();
   std::cout << "last node - " << new_list.TopBack() << "\n";
   std::cout << "First  node - " << new_list.TopFront() << "\n";
}

Follow-up code review Revision-2 C++ implementation of a linked list

Answer 1

Use C++ Headers

These are C headers.

#include<stdio.h>       // Also some white space to make it readable
#include<stdlib.h>      // would be nice.

The C++ equivalent are:

#include <cstdio>
#include <cstdlib>

The difference is that the C++ versions put the function into the stanadrd namespace std so that we avoid name collisions.

You have not implemented the rule of three.

LinkedList   x;
x. InsertFront(1);
LinkedList   y(x); // This is allowed because the compiler
                   // automatically generates a copy constructor
                   // and a copy assignment operator.

You will notice the above compiles (as the compiler generated the copy constructor). But because the compiler generated version does a shallow copy both x and y point at the same list.

x.head -> 1
x.tail ---^
y.head ---^
y.tail ---^

The trouble is that at the end of scope. Both objects get destroyed. 'y' will get destroyed first calling its destructor and calling delete on the node. Then 'x' will be destroyed and it will also call delete on its one node (but this node has already been deleted so this is illegal).

Now the compiler generated methods are usually exactly what you want. But when your class contains an "owned" pointer then you need to do some extra work as the default implementation simply does a shallow copy.

Rule of 5 (Optional)

In C++11 they introduced move semantics to the language. So it has become pretty standard to implement move semantics for container class (as it makes a lot of things very effecient).

Use Initializer List

class LinkedList{
public:
   LinkedList(){
      head = NULL;
      tail = NULL;
   };  // This ';' is not required.

Use the initializer list to initialize member variables in the constructor.

   LinkedList()
      : head(nullptr) // In C++11 we introduced nullptr to replace NULL
      , tail(nullptr) // This is because of the type information.
   {}

Return by reference (maybe)

   int TopBack();
   int TopFront();

This code works fine. But if you return by reference you can alter the value while it is in the list. This can help if you don't want to pop the value and then replace it.

I would have done:

   int& TopBack();
   int& TopFront();

Then in my code I can do:

   LinkedList x;
   // Add stuff to x

   x.TopFront() = 5; // Change the top front value to 5.

What does find do?

   void FindNode(int key);          /*Find node O(n)*/

It does not return anything?

Printing

   void PrintList();

Sure you can print the list. But print it to where? Why not pass the stream you want to print on as a parameter. You can default the stream to std::cout.

   void PrintList(std::ostream& out = std::cout);

Create should just be a constructor.

Sure you can have a createNode() function. But to use this it should be a static method otherwise you need a member to call it.

      Node *CreateNode(int key){

But it's easy to call the constructor directly.

      Node* newNode = Node::CreateNode(5);
      // or
      Node* newNode = new Node(5);

new will not fail

The new function will never return nullptr. If it fails it will throw an exception. As a result there is no need (or point) in checking the return value of new.

         Node *node = new Node();
         if(!node)                 // This will never fire.
            return NULL;

Here there is no point in checking for nullptr here.

   Node *node = node->CreateNode(key);
   if(!node)