Since we have no clean implementations:
The thing to notice is that the push_back() and erase() become trivial if you use a sentinal. This is because you do not need to test for NULL in any part of the code.
Node(Node* after)
{
prev = after;
next = after->next;
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
iterator push_back(T const& value)
{
tail = new ValueNode(value, tail);
// If new succeeded then increment count
++count;
return iterator(tail);
}
void erase(iterator const& i)
{
// Get the value we will set as tail if the delete works
Node* newTail = (tail == i.node)
? i.node->prev
: tail;
delete i.node;
// Delete worked now we can update the state.
tail = newTail;
--count;
}
Here is the whole code
#ifndef THORS_ANVIL_UTILITY_LINKED_LIST
#define THORS_ANVIL_UTILITY_LINKED_LIST
#include <algorithm>
#include <functional>
template<typename T>
class LinkedList
{
struct Node
{
Node* prev;
Node* next;
Node(Node* after)
{
prev = after;
next = after->next;
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
void swap(Node& rhs) throw() { std::swap(prev, rhs.prev); std::swap(next, rhs.next);}
};
struct ValueNode: Node
{
ValueNode(T const& value, Node* after)
: Node(after)
, data(value)
{}
T data;
};
Node head;
Node* tail;
int count;
public:
struct Iterator: std::iterator<std::input_iterator_tag, T, ptrdiff_t, const T*, const T&>
{
Iterator(Node* node): node(node){}
T& operator*() {return static_cast<ValueNode*>(node)->data;}
T* operator->() {return &static_cast<ValueNode*>(node)->data;}
T const& operator*() const {return static_cast<ValueNode*>(node)->data;}
T const* operator->() const {return &static_cast<ValueNode*>(node)->data;}
Iterator& operator++() /*prefix*/ { node = node->next; return *this;}
Iterator& operator--() /*prefix*/ { node = node->prev; return *this;}
Iterator operator++(int) /*postfix*/ { Iterator result(*this);this->operator++(); return result;}
Iterator operator--(int) /*postfix*/ { Iterator result(*this);this->operator--(); return result;}
bool operator !=(Iterator const& rhs) const { return node != rhs.node;}
bool operator ==(Iterator const& rhs) const { return !(*this != node);}
mutable Node* node;
};
LinkedList()
: tail(&head)
, count(0)
{}
~LinkedList()
{
clear();
}
void clear()
{
while(head.next != &head)
{
Node* old = head.next;
head.next = head.next->next;
--count;
delete old;
}
}
LinkedList(LinkedList const& copy)
: tail(&head)
, count(0)
{
std::for_each(copy.head->next, copy.head, std::bind1st(std::mem_fun(&LinkedList::push_back), this));
}
LinkedList& operator=(LinkedList rhs)
{
rhs.swap(*this);
return *this;
}
void swap(LinkedList& rhs) throw()
{
std::swap(head, rhs.head);
std::swap(tail, rhs.tail);
std::swap(count, rhs.count);
}
bool isEmpty() const { return &head == tail; }
size_t size() const { return count; }
typedef Iterator iterator;
typedef Iterator const const_iterator;
iterator push_back(T const& value)
{
tail = new ValueNode(value, tail);
++count;
return iterator(tail);
}
void erase(iterator const& i)
{
Node* newTail = (tail == i.node)
? i.node->prev
: tail;
tail = newTail;
--count;
delete i.node;
}
iterator begin() {return iterator(head.next);}
const_iterator begin() const {return iterator(head.next);}
iterator end() {return iterator(&head);}
const_iterator end() const {return iterator(&head);}
};
#endif
Then Main
#include <LinkedList.h>
#include <iostream>
int main()
{
LinkedList<int> list;
list.push_back(5);
LinkedList<int>::iterator item = list.push_back(7);
for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::cout << *loop << "\n";
}
list.erase(item);
for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::cout << *loop << "\n";
}
}
Diagram of Node Insertion:
Node Before Insertion Starts
after
######### #########
--># Next #------------------------># Next #----
# # # #
---#Prev #<------------------------#Prev #<---
######### #########
NewNode(this)
#########
# Next#
#Prev #
#########
prev = after;
after
######### #########
--># Next #------------------------># Next #----
# # # #
---#Prev #<------------------------#Prev #<---
######### | #########
|
| (this)
| #########
| # Next#
-----#Prev #
#########
next = after->next;
after
######### #########
--># Next #------------------------># Next #----
# # | # #
---#Prev #<-----------------|------#Prev #<---
######### | | #########
| |
| (this) |
| ######### |
| # Next#--
-----#Prev #
#########
prev->next = this;
after
######### #########
--># Next #------ ------># Next #----
# # | | # #
---#Prev #<----|------------|------#Prev #<---
######### | | | #########
| | |
| | (this) |
| | ######### |
| --># Next#--
-----#Prev #
#########
next->prev = this;
after
######### #########
--># Next #------ ------># Next #----
# # | | # #
---#Prev #<--- | | ---#Prev #<---
######### | | | | #########
| | | |
| | (this) | |
| | ######### | |
| --># Next#-- |
-----#Prev #<-----
#########