Linked List review

Question

In my time off I thought I'd implement some idiomatic data structures, starting with a linked list.

Here's my current version:

#include <iostream>
using namespace std;

struct node{
int data;
node *next;
};

void traverseList(node *head){
    for(node *iterator = head ; iterator ; iterator = iterator->next)
    {
        cout << iterator->data << endl;
    } 
}

int length(node *head){
    int count = 0;
    for(node *iterator = head ; iterator ; iterator = iterator->next, count++) {}
    return count;
}

int main(){

    //create the head of the list, assign it data
    node *head = new node;
    head->data = 0;

    //create a {1,2,3} list
    node *first = new node;
    node *second = new node;
    node *third = new node;

    //assign appropriate data
    first->data = 1;
    second->data = 2;
    third->data = 3;

    //assign pointees
    first->next = second;
    second->next = third;
    third->next = 0;

    //give the head the pointee
    head->next = first;

    traverseList(head);
    int listLength = length(head);
    printf("List Length: %d\n", listLength);
    return 0;
}

I've already changed the while loops I originally used (e.g.):

void traverseList(node *head){
  if(head != 0){
    while(head->next !=0){
    cout << head->data << endl;
    head = head->next;
    }

  //one extra for the node at the end
  cout << head->data << endl;
  }
}

to the for loops above. Is there anything else I should keep in mind? I'm following the Stanford CS linked list basics and problem set.

Answer 1

This is C++, not C. Therefore, your linked list class should contain the methods for operating on the list, and it shouldn't expose implementation details like nodes. For traversing the list, provide iterators. You should also make it a template so that it can be used with any type

That's the general picture. More specifically:

• If you insist on traversing with a dedicated function for it, make it take a function (or functor!) so that anything can be done with the nodes.
• You've not created any mechanism for deleting the nodes. Your class should do that in its destructor.
• You're not doing a lot of error checking that you should be. That's not as relevant when you turn it into a class, but making sure head isn't null is very important. You're doing that in traverse now, but length also needs it.

To summarise, if the user of your class sees a single pointer, you can be sure you're doing it wrong.