constructor for a linked list

Question

i am trying to implement a linked list.

List has private variables *head, *tail, count.

I understand the logic in the data structure, but admittedly I am new to C++, so i feel like i may be using the constructor incorrectly.

*head and *tail are list node pointers. list nodes then have pointers to previous and next (doubly linked list).

here is what I tried:

List::List():head(), tail(), count(0) {
    head->previous = NULL; 
    head->next = tail;
    tail->previous = head; 
    tail->next = NULL; 
}

my program compiles but crashes when it tries to make a new list with this constructor. any suggestions?

paxdiablo paxdiablo · Accepted Answer · 2013-09-13T06:26:54

Typically, head and tail will be null pointers for an empty list so dereferncing them like this:

head->previous = NULL;

will be undefined behaviour.

The constructor would simply be:

List::List() : head(0), tail(0), count(0) {}

(or use nullptr for head and tail if your C++ is advanced enough).

If your the type of person who likes dummy nodes at the start and end of your lists, you will need to allocate them before trying to use them:

List::List() : count(0) {
    head = new somethingOrOther();
    tail = new somethingOrOther();

    head->previous = NULL; 
    head->next = tail;

    tail->previous = head; 
    tail->next = NULL; 
}

This trick is often used to greatly simplify list insertions and deletions since you never have to worry about whether you're inserting at the end or deleting at the start.

The downside is that the list traversals and searches for nodes (including for deletion) must start at head->next and finish with tail->previous but that's often simpler than worrying about the earlier issues.

constructor for a linked list

1 Answers