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.