2
\$\begingroup\$

I have created a linked list in C++, I suspect there is a good chance I have made some larger errors in this code as I am working with a few concepts new to me. Please be very hard on me as I want to eventually be good at this.

#include <iostream>

// basic linked list implimentation in C++ using templates


template <class T>
class linkedList
{
  public:
    linkedList(); //constructor
    ~linkedList(); //destructor
    void push_back(const T &value);
    void deleteNodes(const T &value);
    void printList();
    void reverseList();
    void deleteList();
  private:
    struct _node
    {
      T val;
      linkedList *next;
    };
    struct _node node ;
    linkedList *root = NULL;


};
template<class T>
linkedList<T>::linkedList(){};

template<class T>
linkedList<T>::~linkedList(){};

template<class T>
void linkedList<T>::deleteList()
{
  linkedList *t = root;
  while (t)
  {
    t = root->node.next;
    delete root;
    root = t;
  }
}

template<class T>
void linkedList<T>::printList()
{
  if(!root) std::cout<<"List is empty"<<std::endl;
  else
  {
    linkedList *t = root;
    while (t)
    {
      std::cout<<t->node.val<<std::endl;
      t = t->node.next;
    }
  }

}
template <class T>
void linkedList<T>::reverseList()
{

  linkedList *temp = NULL, *prev = NULL, *current = root;
  while (current != NULL)
  {
    temp = current->node.next;
    current->node.next = prev;
    prev = current;
    current = temp;
  }
  root = prev;
}
template <class T>
void linkedList<T>::deleteNodes(const T &value)
{
  linkedList *prev = NULL, *active = NULL;

  if(!root) std::cout<<"List is empty"<<std::endl;
  else
  {
    if (root&& root->node.val == value)
    {
      linkedList *t = root;
      root = t->node.next;
      delete t;
    }
  } 
  prev = root;
  active = root->node.next;
  while (active)
  {
    if (active->node.val == value)
    {
      prev->node.next = active->node.next;
      delete active;
      active = prev->node.next;
    }
    else
    {
      prev = active;
      active = active->node.next;
    }
  }
}
template<class T>
void linkedList<T>::push_back(const T &value)
{
  if (!root)
  {
    root = new linkedList<T>();
    root->node.val = value;
  }
  else
  {
    linkedList *ptr = root;
    while (ptr->node.next)
    {
      ptr = ptr->node.next;
    }

    ptr->node.next = new linkedList<T>(); 
    ptr = ptr->node.next;
    ptr->node.val = value;
  }
}

int main()
{
  linkedList <int> example;

  for (int i = 1; i<=20; i++)
    example.push_back(i);

  example.deleteNodes(20);
  example.deleteNodes(1);
  example.deleteNodes(10);
  example.reverseList();

  example.printList();
  example.deleteList();
  return 0;
}

Compiled with GCC v 4.7.3 on ubuntu 13.04 with the command:

g++ linkedlist.cpp -Wall -std=c++0x -o linkedlist.o

Here is the latest version I have made with the suggested changes. I still need to implement iterators.

#include <iostream>

// basic linked list implementation in C++ using templates


template <class T>
class linkedList
{
  public:
    ~linkedList(); //destructor
    void push_back(const T &value);
    void delete_nodes(const T &value);
    void print_list() const;
    void reverse_list();
    void clear();
    void erase(size_t pos);
  private:
    struct _node
    {
      T val;
      _node *next;
    };
    _node *root = NULL;
};

template <class T>
linkedList<T>::~linkedList<T>()
{
  clear();
}


template <class T>
void linkedList<T>::clear()
{
  struct _node *t =NULL;
  while (t)
  {
    t = root->next;
    delete root;
    root = t; 
  }
}

template <class T>
void linkedList<T>::erase(size_t pos)
{
  struct _node *current = root;
  struct _node *prev = NULL;

  size_t i = 0;
  while (current != NULL)
  {
    if (pos == i)
    {
      struct _node *t = current->next;
      prev->next = t;
      delete current;
    }
   ++i;
   prev = current;
   current=current->next;
  }
}

template <class T>
void linkedList<T>::reverse_list()
{
  struct _node *t = NULL, *prev = NULL, *current = root;
  while (current != NULL)
  {
    t = current->next;
    current->next = prev;
    prev = current;
    current = t;
  }
  root = prev;
}

template <class T>
void linkedList<T>::delete_nodes(const T &value)
{
  struct _node *prev = NULL;
  struct _node *active = NULL;

  if (root == NULL) return; //list is empty
  else 
  {
    if (root != NULL && root->val == value)
    {
      struct _node *t = root;
      root = t->next;
      delete t;
    }
  }

  prev = root;
  active = root->next;

  while (active)
  {
    if(active->val == value)
    {
      prev->next = active->next;
      delete active;
      active = prev->next;
    }
    else
    {
      prev = active;
      active = active->next;
    }
  }
}

template <class T>
void linkedList<T>::push_back(const T &value)
{

  if (root == NULL)
  {
    root = new _node;
    root->val = value;
  }
  else
  {
    struct _node *ptr = root;
    while (ptr->next != NULL)
    {
      ptr = ptr->next;
    }
    //now ptr is at the last spot in the list
    ptr->next = new _node; 
    ptr = ptr->next;
    ptr->val = value; 
    ptr->next = NULL; 
  }
}

template <class T>
void linkedList<T>::print_list() const
{
  struct _node *t = root;
  while (t)
  {
    std::cout<<t->val<<std::endl;
    t = t->next;
  }
}

int main()
{
  linkedList <int> example;

  for (int i = 1; i<=20; i++)
    example.push_back(i);

  example.delete_nodes(1);
  example.delete_nodes(10);
  example.delete_nodes(20);
  example.erase(2);

  example.reverse_list();

  example.print_list();

  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Your code still doesn’t follow the Rule of Three Anton mentioned. In particular, you should either provide copy-assignment and and copy-constructor or explicitly disable them (C++98: declare private and do not implement). Otherwise, it’s all too easy to get memory freed too early, and multiple times. \$\endgroup\$ – Christopher Creutzig Dec 25 '13 at 12:00
5
\$\begingroup\$

I'll cover the C++-specific issues first, and then move on to the design decisions you make.

First of all, note that C++ has the Rule of Three. It states that if you have a custom destructor, copy-constructor or copy-assignment operator, you almost certainly need custom implementations for all three. In your code, the destructor does nothing, and you have no reason to define a custom one at all; the same goes for the constructor. If your destructors and constructors aren't doing any custom work, and there's no technical reason they have to be defined past the class definition, leave them implicit.

However, you should be doing some work in the destructor: destroying the list! Your user should not have to call deleteList just for it to be cleaned up correctly; make it be called by default in the destructor. If it was already deleted, it won't do any harm, and if it wasn't it'll save you from a memory leak. (Alternatively: assert that it has been deleted in the destructor. I don't think it'll make you many friends, though.)

Moving on; the way you define _node and node means that val and next are effectively just members of linkedList. Why not get rid of the extra struct and make them members directly? It won't impact performance, the things probably compile to the same code, but it will make accessing them easier.

Your printList function hopefully doesn't modify the list, so you should make it const. Otherwise, people will be unable to work with references to const to your list, which will upset anyone who's used to using the standard library.

I understand this is the first version, but only allowing people to print the list is a little limiting. Ideally, you should be providing (forward) iterators for your list; they aren't hard to implement, being just pointers with custom increment and dereference semantics. Failing that, at least allow one to apply a function over the list, or to fold it; that would cover most uses.

At the moment, you seem to be treating the val in the first list as not being a real value. This is rather strange; why are you creating a value that nobody can ever access?

This last point brings us to the design questions. All in all, it looks like you end up half-way between representing the linked list and the nodes as a single type, and representing them separately. Here's a suggested rewrite:

template <class T>
class linkedList
{
  public:
    // delete to satisfy rule of 3.
    linkedList(linkedList const&) = delete;
    linkedList& operator=(linkedList const&) = delete;
    ~linkedList();

    // I've renamed your members to be snake_case.  It doesn't really
    // matter which one you use, but mixing them inside one class just
    // doesn't look right to me.
    void push_back(const T& value);
    void delete_nodes(const T& value);
    void print_list() const;
    void reverse_list();
    void delete_list();

  private:
    // Now we have the choice of whether to represent the list with each
    // node being another linked list, or a single linked list with separate
    // nodes:

#ifdef NODES_SEPARATE
    // In this version, the linkedList is responsible for all nodes:
    struct _node {
        T val;
        _node* next;
    };

    _node* root = NULL;

#else
    // In this case, every linked list thinks it is the first in the
    // chain.  A little weird, but still usable.
    struct _node {
        T val;
        linkedList list;
    };

    _node* next = NULL;
#endif
};

I could be missing something, but I think you meant to have one of these. (They are likely the same in memory, by the way, it's just a matter of different types.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the review I am working on the changes now. Would you recommend that I simply call my deleteList() function from the destructor? Or would it make more sense to not have a deleteList() function, and have that code directly in the destructor? \$\endgroup\$ – r-s Sep 4 '13 at 22:39
  • 3
    \$\begingroup\$ @r-s: I would try to mimic standard library containers as much as possible, so I'd have a clear function which I'd call from the destructor. \$\endgroup\$ – Anton Golov Sep 4 '13 at 22:51
2
\$\begingroup\$

Just a quick note:

In the void linkedList::clear() function you probably mean

  struct _node *t =root;

and not

  struct _node *t =NULL;

In the latter, you will never enter the while loop if t == NULL

| improve this answer | |
\$\endgroup\$

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.