This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  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.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.