12
\$\begingroup\$

Could someone review my linked list code? Specificially, is the design to separate Node and actions to create linked list appropriate?

template <typename T>
class Node {

  public:
    Node() : next(0) { }
    Node(T value) : val(value), next(0) { }
    T val;
    Node* next;

  private:
    Node(const Node& nd) { }
    Node& operator=(const Node& nd) { }  
};

template <typename T>
class List {

  public:
    List() {
      begin = new Node<T>();
    }

    List(T initval) { 
      begin = new Node<T>(initval);
    }
    List(const List& inp) {
      begin = new Node<T>(inp.begin->val);
      Node<T> *tempInitial = inp.begin->next;
      Node<T> *tempFinal = begin;

      while(tempInitial->next) {
        tempFinal->next = new Node<T>();
        tempFinal = tempFinal->next;
        tempFinal->val = tempInitial->val;
        tempInitial = tempInitial->next;
     } 
  }


  void addVal(const T& val) {
    if(!begin->next && begin->val == 0) {
      begin->val = val;
    }
    else {
      Node<T> *temp = begin;
      while(temp->next) { 
        temp = temp->next;
      }
    temp->next = new Node<T>(val);
    }
  }

  bool deleteVal(const T& val) {
    Node<T>* pos = isPresentN(val);
    if( pos == 0) return 0;
    if(pos == begin) { begin = pos->next; delete pos; return 1;  }

    Node<T>* temp = begin;
    while(temp->next != pos) {
      temp = temp->next;
    }
    Node<T>* delnode = temp->next;
    temp->next = temp->next->next;
    delete delnode;
    return 1;
  }



  Node<T>* isPresentN(const T& val) {
    Node<T>* temp = begin;
    while(temp) { 
      if(temp->val == val)  return temp;
    temp = temp->next;
    }

  return 0;  
  }

  bool isPresent(const T& val) {
    if(isPresentN(val)) return 1;
    return 0;
  }

  ~List() {
    Node<T>* temp= begin, *t;
    while(temp) {
      t = temp;
      temp = temp->next;
      delete t;
    } 
  }

  private:
    Node<T> *begin;
};
\$\endgroup\$
4
\$\begingroup\$

By no means an expert at C++, but a few notes:

Node Constructor

I would get rid of the first constructor and change the second constructor a bit:

Node(const T& value = T()) : val(value), next(NULL) { }

Two things are happening here: * I would make it just use a default-constructed instance if one isn't passed * You should be passing a const reference as to avoid an unnecessary copy (val(value) is already copying it)

isPresentN is badly named

Any time a method starts with is I expect a bool return. I would consider renaming this to findNode or something similar. (And, as Benjamin Kloster said, I would make it private.)

Remember that your class is a template

I suspect that most people, me included, tend to develop templated classes while pretending that T is just a plain-old-int. You have to be careful about this though.

if(!begin->next && begin->val == 0) {

If T were string, or basically anything that doesn't implement operator==(int), this line would keep your class from compiling.

As Benjamin said, just use a NULL begin when the list is empty.

addVal and deleteVal

I would consider renaming these add (or append) and remove since the consumer already knows that he's adding a value.

Edit

I previously suggested to use NULL. After the note in the comments and a bit of googling, I've decided that my suggestion to use NULL was in error. For anyone interested though, the following links outline a few interesting reasons for and against NULL: here, here, here, and here.

\$\endgroup\$
  • \$\begingroup\$ Brilliant. I had totally missed the begin->val == 0 part. Thanks for the suggestions. \$\endgroup\$ – ersran9 Jun 26 '12 at 9:07
  • \$\begingroup\$ @ersran9 Once I have a templated class finished, I typically test it with int, string and a user defined type that does lots of dynamic memory allocation and deallocation. Then I run the program through valgrind. That usually takes care of forgotten lines like that one or any kind of memory issues the class may have. (Can be a bit overkill for simple classes though.) \$\endgroup\$ – Corbin Jun 26 '12 at 9:17
  • \$\begingroup\$ I disagree strongly with using NULL. There is no difference for the compiler, so using NULL can be highly misleading. int x = NULL; compiles just fine, so NULL doesn’t actually offer any information about usage to the reader. This changes with C++11 and nullptr, but for now, sticking to 0 is fine and encouraged by most professional C++ programmers who write about this. \$\endgroup\$ – Konrad Rudolph Jun 26 '12 at 9:32
  • 1
    \$\begingroup\$ @KonradRudolph: max0x7ba.blogspot.com/2010/03/0-vs-null-in-c.html \$\endgroup\$ – Martin York Aug 3 '12 at 22:47
  • 1
    \$\begingroup\$ @Loki You are aware that this breaks the standard though? Is it enabled with -pedantic? \$\endgroup\$ – Konrad Rudolph Aug 4 '12 at 9:12
10
\$\begingroup\$

Major problem:

You are breaking the rule of three(five).

Your class contains a RAW pointer. This means you need to override Copy Constructor/Assignment operator/Destructor. You missed the assignment operator.

{
    List<int>  x;
    List<int>  y;

    x = y; // This is going to cause problems.
}
// At this point when it is destroyed.
// As both x and y point at the same begin object.

Since you have a valid copy constructor you can just use the copy and swap idium to build the assignment operator.

List& operator=(List rhs)        // pass by value to get copy
{
    std::swap(begin, rhs.begin); // Now swap all data members.
                                 // You could write your own swap member
    return *this;
}

Sentinels

You create your list with an initial 'Sentinel' value. This is a common technique to remove the need to check for NULL pointers in your code and can make the other functions easier to write (as you don't need to check for NULL). BUT to use it usefully the list needs to be circular (last element points at first) and you must always have this unused 'Sentinael' node.

When you use this technique you should never use the sentinel as a value holding node. You should always skip over it. Your loop then is always from begin->next (as the first node) until begin (when you reach begin again you have gone one past the last node (hence the need for a circle).

Unfortunately your code is a mix of using sentinel and using NULL terminated list. You need to pick one and stick with it. Using a sentinel makes the code much easier to write (as you don't need to check for NULL and special case the empty list).

Need a tail pointer

You currently only have a head pointer.
This means when you insert into the list you always chain all the way to the end before inserting. This makes an operation that could be O(1) be O(n). Most list implementations use head/tail pointer or use a doubly linked list (one chain for each direction). This makes finding the tail trivial and maintaining the extra pointer has practically no cost.

Other comments:

The rest of the code assumes you were trying to use a sentential value to make the use of the list more efficient. If you want to use NULL to indicate the end of a list rather than a sentinel the comments will change slightly (but using sentinels is the better solution so I will move ahead from there).

Not all types have a default value (or are default constructable). So you need two versions of your node class. One to use as the sentinel and one to use that holds the data payload. Let us assume that Node is the version that holds the payload and inherits from the base class that just contains pointer information:

When construing Nodes:

// Remove the default constructor.
// When creating a payload node it should be initialized with a value.
Node() : next(0) { }

// The constructor should take a value by const reference
// This will make sure that expensive to copy objects are not over copied.
// You should also pass a pointers to link it into the list.
// At the point it is constructed you should have that information by putting
// this code in the constructor you will make creation and use easier.
Node(T value) : val(value), next(0) { }

// Since Node is a publicly available class and not designed to be copied
// You should (and have) disable the copy constructor and assignment operator.
//
// Alternatively if you make Node a private Type inside the List class then
// this is not needed.   
private:
Node(const Node& nd) { }
Node& operator=(const Node& nd) { }  

Construct list and insert sentinel as expected.

List() {
  begin = new BaseNode();  // Note I changed the type BaseNode
                           // Note: BaseNode constructor will make next point
                           //       back at itself.
}

When you use this constructor. You should also insert a sentinel. So the list always has a sentinel value no matter how it is created. Then you can just add the value as normal.

List(T initval) { 
  begin = new BaseNode();
  addVal(initval);
}

Adding a node is a common task with its own specific method addVal() of doing this. Use this common method to do the actual work of adding a node. This prevents duplicating of code and makes sure that adding a node is consistently done (Note your current addVal() is not very efficient but I will address that separately.

    List(const List& inp) {
      begin = new Node<T>(inp.begin->val);
      Node<T> *tempInitial = inp.begin->next;
      Node<T> *tempFinal = begin;

      while(tempInitial->next) {
        tempFinal->next = new Node<T>();
        tempFinal = tempFinal->next;
        tempFinal->val = tempInitial->val;
        tempInitial = tempInitial->next;
     } 
  }

// Could look like this:
List(List const& rhs)
{
      begin = new BaseNode<T>();  // sentinel.

      Node<T>* begin = inp.begin;
      for(Node<T>* loop = begin->next; loop != begin; loop  = loop->next);
      {
           addVal(loop->val);
      }
}

In your version here you seem to overwrite the sentinel.
This is wrong as if you add 0 multiple times it will only be added once. Leave the sentinel alone and just concentrate on adding a new node each time.

void addVal(const T& val) {
if(!begin->next && begin->val == 0) {
  begin->val = val;
}

Here you assume that last node is NULL terminate.
But in the copy constructor you assume that the list is circular.

else {
  Node<T> *temp = begin;
  while(temp->next) { 
    temp = temp->next;

I would go with the circular list (using sentinels). Also each time you add a value you must traverse the whole list to find the end. It would be easier to keep track of the last value using two pointers in List object; begin (points at the sentinel) and end (points at the last inserted node (or at the sentinel if empty list)).

Using a sentinel the insert becomes.

void addVal(const T& val)
{
    Node<T>* last = findlast(begin); // not needed if you have a last member.

    Node<T>* newNode = new Node(val, last, begin);
                                //   ^^^^         node before the new node
                                //         ^^^^^  node after the new node.
}

Deleting items from a singly linked list is a pain (as you need the proceeding item). doubly linked list are a lot easier (in my opinion) to use because of this. But again you are potentially deleting the sentinel here.

You also search the list twice. The first time you search to find the value. Then you search the list to find the value before the node you want to delete.

bool deleteVal(const T& val) { Node* pos = isPresentN(val); if( pos == 0) return 0; if(pos == begin) { begin = pos->next; delete pos; return 1; }

Node<T>* temp = begin;
while(temp->next != pos) {
  temp = temp->next;
}

You can simplify this and just look for the value by checking the value of the next node. Note: The same code works for NULL terminate list (just change begin into NULL).

Node<T>* loop = begin;
while(loop->next != begin && loop->next.val != val)
{
    loop = loop->next;
}
// Now loop->next is either begin or points at the node we are looking for.
if (loop->next != begin)
{
    Node<T> old = loop->next;
    loop->next = old->next;
    delete old;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for the suggestions.I have some doubts though 1. the std::swap uses the copy constructor [ which performs the deep copies anyway- hence suited in this scenario. ] - Is my understanding correct here? 2 . When you say circular linked list - you mean => [sentinal] -> [some elements here] -> [last element] -> [the initial sentinal]. Is this right? \$\endgroup\$ – ersran9 Jun 27 '12 at 14:05
  • \$\begingroup\$ Also, you remarked that "But in the copy constructor you assume that the list is circular.". I didn't get that part - the loop while(tempInitial->next) will go on till the last element. I wrote that code for a singly linked list. Did I make a mistake here, or am I not understanding this right? \$\endgroup\$ – ersran9 Jun 27 '12 at 14:10
  • \$\begingroup\$ Opps. Your copy constructor does assume NULL termination. You confused me with your naming convention tempFinal. mea culpa. \$\endgroup\$ – Martin York Jun 27 '12 at 15:39
  • \$\begingroup\$ If your first comment is about the assignment operator then: 1: std::swap() on pointers just swaps the pointers (there is no deep copy). But the assignment operator must do a deep copy and thus is achieved by using the copy constructor which is used implicitly when we pass by value (please read up on the copy swap idiom). \$\endgroup\$ – Martin York Jun 27 '12 at 15:43
  • \$\begingroup\$ The circular list: you mean => [sentinal] -> [some elements here] -> [last element] -> [the initial sentinel]. Yes. \$\endgroup\$ – Martin York Jun 27 '12 at 15:44
3
\$\begingroup\$

The overall structure looks ok, but two things:

  1. If T is int and you repeatedly call addVal(0), the list stays unchanged. Consider just setting begin to NULL, it's a more reliable way to tell if the list is empty.

  2. isPresentN should either be private (or at least protected), or you should return a const pointer to the node. Otherwise, someone could accidentally change the node's next field.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot. Since I'm using isPresentN as a helper function within the class, isn't it better if I make it a private function? [ compared to returning a const pointer ] \$\endgroup\$ – ersran9 Jun 26 '12 at 8:46
  • \$\begingroup\$ Yep. It's always a good idea to only expose the absolutely necessary functions. And I can't imagine a scenario where you'd need to override it in a subclass, so private should be the right choice. \$\endgroup\$ – Benjamin Kloster Jun 26 '12 at 9:00

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.