
Linked List Class
Submitted by 
This is the same Linked List class that was submitted by Chris Thompson a few
weeks ago, only optimised. As Chris had said at the time, it was a simple class
that was not optimised and written quickly. It was an excellent learning
experience for me, and that was only as such because of its simplicity. I had
since spoken with Chris and he had no problems with me resubmitting the code.
Some changes made are big, but overall, only one effect is made to how the class
is used:
List made 2 way
List Inserts now insert at the end of the list, and will not insert
into the specified position.
index parameter was left for 3 reasons:
removing the parameter would effect code that used the
parameter
if someone wanted to readd positional inserts, then
they would not have to make any drastic changes.
im lazy.
The [] operator now works in milestones, jumping in m_msJump and
m_msJump2 distances respectively. Basically, the list is now linked on three
different levels, the bottom level being each element to the next, the next
level being linked every m_msJump elements, and the third being linked every
m_msJump2 distances (for the very large lists).
Any advice is encouraged (although flaming is not  I am relatively new to c++,
so gimme a break). If anyone knows of a possible better way of doing a list (not
including using STL  i'm optimising this list for a learning experience),
please feel free to post a message. The optimisations has taken my code from
0.1fps to ~3540fps, so I'm happy with my optmisations.
Hope to hear from you all,
Richard Szalay

Download Associated File: newlist.h (7,026 bytes)
/*
Name: List.h
Purpose: Linked List template class (declarations and definitions)
Original Author: Chris Thompson
Author: Richard Szalay
Created: 27th September, 2000
History: 08/10/00 : Added primary/secondary milestone system
*/
#ifndef __LIST_H__
#define __LIST_H__
#include <stdio.h>
template <class ListItem>
class List
{
public:
List()
:m_numelements(0),
m_lastIndex(0),
m_msJump(64),
m_msJump2(256)
{
m_head = new Link;
m_tail = new Link;
m_head>next = m_tail;
m_head>prev = m_head;
m_tail>next = m_tail;
m_tail>prev = m_head;
};
~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)
{
/* Positioning removed from insert
 data in inserted before the tail */
Link* newnode = new Link(data); // Create the new node
/* inform the surrounding nodes */
newnode>prev = m_tail>prev;
newnode>prev>next = newnode;
m_tail>prev = newnode;
newnode>next = m_tail;
/* 0 is an exception to the Milestone counter */
if (m_numelements == 0)
{
m_lastMilestone = newnode;
m_tail>prevMS = newnode;
m_lastMilestone2 = newnode;
m_tail>prevMS2 = newnode;
m_lastNode = newnode;
m_lastIndex = 0;
}
newnode>prevMS = m_lastMilestone; // remember the previous milestone
newnode>prevMS2 = m_lastMilestone2;
/* Primary Level Milestone */
if (((m_numelements) % m_msJump) == 0)
{
m_lastMilestone = newnode;
newnode>prevMS>nextMS = newnode;
newnode>nextMS = newnode;
m_tail>prevMS = newnode;
}
/* Secondary Level Milestone */
if (((m_numelements) % m_msJump2) == 0)
{
m_lastMilestone2 = newnode;
newnode>prevMS2>nextMS2 = newnode;
newnode>nextMS2 = newnode;
m_tail>prevMS2 = newnode;
}
m_numelements++;
}
void Remove(int index)
{
Link* before = m_head;
Link* after;
/*
Could/Should impliment a faster
Remove function  but i've never
actually used it
*/
for (int i=0;i<index;i++)
before = before>next;
after = before>next>next;
delete before>next;
before>next = after;
after>prev = before;
m_numelements;
}
ListItem operator[](int index)
{
Link* element;
int start, end, lastIndex;
start = 0;
end = m_numelements;
lastIndex = m_lastIndex;
element = m_head>next;
/*
Before we do anything else, check
if we are within 16 of the beginning
or the end
*/
// Near beginning
if (index < m_msJump)
{
for (int i=0; i<index; i++)
{
element = element>next;
}
m_lastIndex = index;
m_lastNode = element;
return element>data;
}
// Near end
if (index > (m_numelements  (m_numelements % m_msJump)))
{
element = m_tail;
for (int i=m_numelements; i>index; i)
{
element = element>prev;
}
m_lastIndex = index;
m_lastNode = element;
return element>data;
}
/*
Also, check if we are within 16 of the
last requested index
*/
// < to the left
if ((index < m_lastIndex)&&((m_lastIndex  index) < (m_msJump >> 1)))
{
element = m_lastNode;
for (int i=m_lastIndex;i>index;i)
{
element = element>prev;
}
m_lastIndex = index;
m_lastNode = element;
return element>data;
}
// > to the right
if ((index >= m_lastIndex)&&((index  m_lastIndex) < (m_msJump >> 1)))
{
element = m_lastNode;
for (int i=m_lastIndex;i<index;i++)
{
element = element>next;
}
m_lastIndex = index;
m_lastNode = element;
return element>data;
}
/*
If we are here we arent close
to anything 'nice'. So we find
our closest 'milestone'
*/
int diffModulo = (index % m_msJump);
int closePrevMS = (index  diffModulo);
int diffModulo2 = (closePrevMS % m_msJump2);
int closePrevMS2 = (closePrevMS  diffModulo2);
int i;
/* Find secondary level milestone */
// Which end should we start at?
// (which half of the list is it?)
if (closePrevMS2 > (m_numelements >> 1)) // end?
{
element = m_tail>prevMS2;
int supl = (m_numelements(m_numelements%m_msJump2));
for (i=supl; i>closePrevMS2; i=m_msJump2)
{
element = element>prevMS2;
}
}
else // beginning ?
{
for (i=0; i<closePrevMS2; i+=m_msJump2)
{
element = element>nextMS2;
}
}
/* Find primary level milestone */
// Which end should we start at?
// (which half of the list is it?)
if ((diffModulo2 > (m_msJump2 >> 1)) && (element>nextMS2 != element))
{
element = element>nextMS2; // jumpin'
i += m_msJump2; // we start one jump forward (for counting)
if ((element>prevMS>nextMS != element) &&
(element>prevMS != element))
{
element = element>prevMS;
i=m_msJump;
}
for (i=i; i>closePrevMS; i=m_msJump)
{
element = element>prevMS;
}
}
else // no  stay here and go forwards
{
if ((element>prevMS>nextMS != element) &&
(element>prevMS != element))
{
element = element>prevMS;
i=m_msJump;
}
for (i=i; i<closePrevMS; i+=m_msJump)
{
element = element>nextMS;
}
}
/*
 Final Stage 
The closest lowestlevel milestone has been located
From here go (forwards or backwards) to find the node
*/
// Should we jump to the next milestone and go backwards?
if ((diffModulo > (m_msJump >> 1)) && (element>nextMS != element))
{
// yes  jump and go backwards
element = element>nextMS; // jumpin'
i += m_msJump; // we start one jump forward (for counting)
for (i=i; i>index; i)
{
element = element>prev;
}
}
else // no  stay here and go forwards
{
for (i=i; i<index; i++)
{
element = element>next;
}
}
m_lastIndex = index;
m_lastNode = element;
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
Link* prev; // previous node
ListItem data; // data stored in this node
Link* nextMS;
Link* prevMS;
Link* nextMS2;
Link* prevMS2;
};
// head and tail
Link* m_head;
Link* m_tail;
Link* m_lastNode;
int m_numelements;
int m_lastIndex;
Link* m_lastMilestone; // link of primary level jumps (milestones)
Link* m_lastMilestone2; // link of secondary level jumps (milestones)
int m_msJump; // Size of jump for primary level
int m_msJump2; // Size of jump for secondary level
};
#endif 

The zip file viewer built into the Developer Toolbox made use
of the zlib library, as well as the zlibdll source additions.
