Linked list (1)

List is the most basic data structure. I have got the idea in the book "Absolute C++". But there are still some interesting points.

Dummy Head Nodes

• That is always present, even when the linked list is empty.
• The item at the first position of the list is actually in the second node.
• The insertion and deletion algorithms initialize prev to point to the dummy head node rather than to NULL
• Dummy head nodes are useful in doubly linked list, since it could eliminate the special case and make the operation relatively simpler.

Function Object

• An object that behave like a function, uses the method operator to define the desired behavior.
• Following code allows strings to be sorted in descending order by overriding the default std::greaterff

template<> struct std::greater
{
//override operator() to create a function object
bool operator() (string* s1, string* s2)
{
return (*s1) > (*s2)
}//end operator()
};//end std::greater