linked list iterators

[jaded7]

I am currently implementing a linked list (as an exercise) and I am close to finish it, with one of the last few things to do being implementing an iterator. The linked list is doubly linked, with pointers to both the first and last element.


I am currently about to define an iterator, and I know that a common practice with containers which are contiguous in memory is to make the end() function return the address AFTER the last value, so that you can do stuff like this:

    std::vector<int> v(5, 10);
    for(auto it = v.begin(); it != v.end(); it++)
    {
        *it = 1234;
    }

However, I'm not sure what to do in this case, as the elements are not contiguous. My first thought was to place an empty node at the last element, and have the end() method return this. Is there a better way? Any tips, with regards to this, or making the linked list, are more than welcome.

[AbstractionAnon]

It depends on your implementation. There are (at least) two ways to implement a doubly linked list.

1) You have a distinct listhead. The pointers in the listhead usually point to itself if the list is empty. In this case, begin() would return the forward pointer and end() would return the address of the listhead. If begin() and end() are equal, the list is empty. If you're implementing your list as a class or templated class, then the instance of the class usually serves as your listhead.

2) You don't have a distinct listhead. In this case begin() and end() are problemmatic. Where does the list begin or end? Any node can be the beginning or end of the list, or both if it's a singleton node.

Edit: I just noticed you used a vector in your example. I'm presuming that was to make you point about iterators and was not how you intended to store the elements in your linked list. The main advantage of linked lists is that individual nodes do not need to be contiguous (and usually are not).

[JLBorges]

> My first thought was to place an empty node at the last element, and have the end() method return this.

That is not a good idea, for more than one reason.


> Is there a better way?

The typical implementation of an iterator for a list is:

The iterator holds a pointer to a node in the list (and identifies or 'points to' the value contained in the node).

Increment and decrement move the iterator to the next/previous element by updating the pointer to the node.

begin() returns an iterator containing a pointer to the first node.

end() returns an iterator containing a nullptr

In a doubly linked list, the iterator is bidirectional, and --end is well defined. One way to support this is by storing some extra information in the iterator; for instance a reference to the list object. For decrement, check if the pointer to the node is a nullptr; if it is, update the pointer to point to the last node of the list; if it is not, update the pointer to point to the node's previous node.

[jaded7]

re: AbstractionAnon

You are right in your edit. Just used a vector to give an example of the iterative process, it will be designed such that the nodes are not contiguous.

Thank you both for the advice.

[Lowest0ne]

However, I'm not sure what to do in this case, as the elements are not contiguous

You will be overloading the operators of the iterator, something like:

class iter
{
  node* myNode;

  operator++() { myNode = myNode->next; } // Solves the contiguous issue
  operator*()  { return myNode->data;   }  // protect the actual pointer
};

[jaded7]

That isnt the problem I was having, it was addressing the relational operators and the beginning and end of the doubly linked list. Thanks anyway.