|
Linked List
Submitted by |
Here's a small linked list class I use in just about everything I do. It's just
really handy, and really easy to use. I wrote it after reading "Algorithms in
C++" by Robert Sedgewick. He's got a few chapters that look in depth into
lists/stacks/queues. There's some good ideas in there like using head and tail
nodes to eliminate special case handling of beginning/end of list. I definitely
recommend it to immediate/advanced C++ users.
Sometime in the future, when I have some spare time and a need for speedups, I
may add more to this class. One idea I had was to flag each link as used/empty,
so that links can be reused to avoid memory allocation overhead. Another idea,
taken from Sedgewick, is to use an array for the links and an array for indices.
Basically you are restricted by the array size, but you can insert/remove in the
style of linked lists without needing to shuffle things around. Plus you have
the advantage of all links being contiguous in memory, which reduces cache
misses. Again these are just ideas that may or may not be feasible depending on
the application.
Chris Thompson aka "Lightman"
|
Download Associated File: list.h (1,786 bytes)
template <class ListItem>
class List
{
public:
List()
:m_numelements(0)
{
m_head = new Link;
m_tail = new Link;
m_head->next = m_tail;
m_tail->next = m_tail;
};
~List()
{
Link* before = m_head;
Link* after;
while (before->next != m_tail)
{
after = before->next->next;
delete before->next;
before->next = after;
}
delete m_head;
delete m_tail;
};
void Insert(int index, const ListItem& data)
{
Link* before = m_head;
Link* newnode;
for (int i=0;i<index;i++)
before = before->next;
newnode = new Link(data);
newnode->next = before->next;
before->next = newnode;
m_numelements++;
}
void Remove(int index)
{
Link* before = m_head;
Link* after;
for (int i=0;i<index;i++)
before = before->next;
after = before->next->next;
delete before->next;
before->next = after;
m_numelements--;
}
ListItem operator[](int index)
{
Link* element = m_head->next;
for (int i=0;i<index;i++)
element = element->next;
return element->data;
}
int Size() // number of elements in the list
{
return m_numelements;
}
private:
// node in our list
struct Link
{
Link()
:next(NULL) {};
Link(const ListItem& datain)
:data(datain),
next(NULL) {};
Link* next; // next node in list
ListItem data; // data stored in this node
};
// head and tail
Link* m_head;
Link* m_tail;
int m_numelements;
}; |
|
The zip file viewer built into the Developer Toolbox made use
of the zlib library, as well as the zlibdll source additions.
|