I just tried to find a decent article on linked lists, but I couldn't, so bear with me and I'll try and write one:
Objects in the list should not need to know anything about lists. This way we can change the list for any other data structure and everything will still work.
I gave an outline for a linked list class before. Here's a slightly modified version:
// this is the class of objects we will put in our linked list.class Content{};// this is out linked list classclass LinkedListForContent{ public: LinkedListForContent(); ~LinkedListForContent(); void append(Content* object); Content* get(int index); private: Content* head; LinkedListForContent* tail;};
Now for the constructor. The initial list has no content and no tail:
LinkedListForContent::LinkedListForContent(){ head = null; tail = null;}
We'll leave the destructor for a bit. Next we'll write the append method.
Our fist LinkedList node has no content, so we can just put the content into the node. After that things get tricky. To simplify things we'll do the following. Everytime we insert an object we check if the current node already has data. If not we put the data in this node and create a new node after this one. If this node already has data then we move on to the next node and try there.
This means that there will always be a free node at the end of the list with no data.
void LinkedListForContent::append(Content* object){ if (head == null) { head = object; tail = new LinkedListForContent(); } else { tail->append(object); }}
Now for the get function. This one is easy. If the index is zero then we wan't the item from the current node. If not we want the item from (index - 1) nodes further down, so we can just get the (index - 1)'th item from the tail of the list.
Content* LinkedListForContent::get(int index){ if (index < 0) { // somebody's just being silly return null; } else if (index == 0) { return head; } else if (tail != null) { return tail->get(index - 1); } else { // there's no more list left return null; }}
Finally the destructor. All we need to do is delete the data object and ask the rest of the list to delete itself.
LinkedListForContent::~LinkedListForContent(){ delete head; delete tail;}
Hopefully that makes sense. If you have any questions then just ask. Note that a real list wouldn't delete the whole list in the destrutor. It would only delete the node. Instead it would provide a function to delete the whole list. This arrangement allows you to do things like remove an item from the middle of the list, or remove the first element.
Enigma
EDIT: typos
EDIT2: more typos
EDIT3: and yet more typos
EDIT4: ditto
EDIT5: clarification
[edited by - Enigma on February 6, 2004 8:23:39 PM]