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 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 re-submitting 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 re-add 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 ~35-40fps, 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 lowest-level 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.

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