Welcome, Guest! Login | Register

Simple Data Structures [Print this Article]
Posted by: Persuter
Date posted: Aug 20 2003
User Rating: 5 out of 5.0
Number of views: 5922
Number of comments: 0
Description: Linked lists, queue, tree
Simple Data Structures

Oftentimes new programmers find concepts like linked lists, trees, and other common data structures to be somewhat intimidating. However, simple data structures serve as the building blocks for high-level programs. Hopefully, once you see a few of these data structures in action, you'll see places to use them in your own code.

Now, the only real programming experience you'll need here is that you'll have to be fairly conversant with pointers.

We'll start with the simplest data structure, the singly linked list. The singly linked list consists of a chain of elements, each with some data and a pointer to the next element in the chain. We have a head element that no other element points to, and the last element in the chain points to NULL. So, if H is the head element, and x's represent all the elements in the middle, the chain looks like this:

H -> x -> x -> x -> x -> x -> x -> NULL

We can implement a linked list that stores integers via the following:

 CODE (C++) 
class LinkedListElement {

public:

    LinkedListElement( int num )
    {
        m_pNextElement = NULL;
        m_iNumber = num;
    }

    int GetNumber( void ) { return m_iNumber; }
    void SetNextElement( LinkedListElement* elem ) { m_pNextElement = elem; }
    LinkedListElement* GetNextElement( void ) { return m_pNextElement; }

private:

    LinkedListElement* m_pNextElement;
    int m_iNumber;

};

class LinkedList {

public:

    LinkedList( void )
    {
        m_pHeadElement = NULL;
    }

    void InsertNumber( int num )
    {
        InsertElement( new LinkedListElement( num ) );
    }

private:

    void InsertElement( LinkedListElement* elem )
    {
        elem->SetNextElement( m_pHeadElement );
        m_pHeadElement = elem;
    }

    LinkedListElement* m_pHeadElement;
};


It's just that simple. Note the simplicity of InsertElement in particular. We know that m_pHeadElement will be NULL if and only if there are no entities in the chain. Thus, we can simply set elem's next element to m_pHeadElement, confident that that will always be correct, since if there are no elements, then its next element will be set to NULL.

OK, so you may have noticed that there's no way to delete numbers. We'll set that to rights now:

 CODE (C++) 
class LinkedList {

public:

    LinkedList( void )
    {
        m_pHeadElement = NULL;
    }

    void InsertNumber( int num )
    {
        InsertElement( new LinkedListElement( num ) );
    }

    void DeleteNumber( int num )
    {
        LinkedListElement* elem = m_pHeadElement;
        LinkedListElement* lastelem = NULL;

        while( elem )
        {
            if( elem->GetNumber() == num )
            {
                if( lastelem ) // it exists so we're in the middle of the list
                {
                    lastelem->SetNextElement( elem->GetNextElement() );
                }
                else // it doesn't exist, elem = m_pHeadElement
                {
                    m_pHeadElement = elem->GetNextElement();        
                }

                delete elem;
                return;
            }

            lastelem = elem;
            elem = elem->GetNextElement();
        }
    }

private:

    void InsertElement( LinkedListElement* elem )
    {
        elem->SetNextElement( m_pHeadElement );
        m_pHeadElement = elem;
    }

    LinkedListElement* m_pHeadElement;
};


Ew. Not as nice code, eh? Nonetheless, if you look at it a bit, you'll see that it's not too bad. All it does is search through the list until it gets to an element with the correct number. Once it does that, if lastelem exists, it sets lastelem's next element to elem's next element, thus "splicing" elem out. It looks something like:

H -> x -> lastelem -> elem -> NextElement -> NULL becomes H -> x -> lastelem -> NextElement -> NULL.

Now, if lastelem does not exist, that means that elem is the head particle, and thus we need to do:

H -> NextElement -> x -> x -> x -> NULL becomes NextElement -> x -> x -> x -> NULL.

All of this just takes a bit of clear thinking about what possibilities there are. Now, you might ask, "What if there is no element with the correct number?" Well, once again, the convenience of having NULL as the last pointer gets home. When elem is set to elem->GetNextElement() for the last element, elem becomes NULL, since that's the next element. And then, of course, while( elem ) becomes false.

Now we're going to do a slight change to the linked list, by changing it to a doubly linked list. This is the same as a singly linked list, except that now each element has a pointer to both the element after it and before it. The first element has a pointer to NULL before it, just like the last element had a pointer to NULL after it. This will make more complicated data structures easier to implement, but it makes it a bit more complicated in deletion.

 CODE (C++) 
class LinkedListElement {

public:

    LinkedListElement( int num )
    {
        m_pNextElement = m_pPrevElement = NULL;
        m_iNumber = num;
    }

    int GetNumber( void ) { return m_iNumber; }
    void SetNextElement( LinkedListElement* elem ) { m_pNextElement = elem; }
    LinkedListElement* GetNextElement( void ) { return m_pNextElement; }
    void SetPrevElement( LinkedListElement* elem ) { m_pPrevElement = elem; }
    LinkedListElement* GetPrevElement( void ) { return m_pPrevElement; }

private:

    LinkedListElement* m_pNextElement;
    LinkedListElement* m_pPrevElement;
    int m_iNumber;

};

class LinkedList {

public:

    LinkedList( void )
    {
        m_pHeadElement = NULL;
    }

    void InsertNumber( int num )
    {
        InsertElement( new LinkedListElement( num ) );
    }

    void DeleteNumber( int num )
    {
        LinkedListElement* elem = m_pHeadElement;

        while( elem )
        {
            if( elem->GetNumber() == num )
            {
                if( elem->GetPrevElement() )
                {
                    elem->GetPrevElement()->SetNextElement( elem->GetNextElement() );

                    if( elem->GetNextElement() )
                    {
                        elem->GetNextElement()->SetPrevElement( elem->GetPrevElement() );
                    }
                    else // elem is the last particle
                    {
                        elem->GetPrevElement()->SetNextElement( NULL );
                    }
                }
                else // elem is the head particle
                {
                    m_pHeadParticle = elem->GetNextElement();

                    if( elem->GetNextElement() ) // list is not empty
                        elem->GetNextElement()->SetPrevElement( NULL );
                }

                delete elem;
                return;
            }
            elem = elem->GetNextElement();
        }
    }

private:

    void InsertElement( LinkedListElement* elem )
    {
        elem->SetNextElement( m_pHeadElement );
        elem->SetPrevElement( NULL );
        m_pHeadElement = elem;
    }

    LinkedListElement* m_pHeadElement;
};


As you can see, this is a bit more complicated than what we had earlier. However, it isn't really difficult. The logical stuff in DeleteNumber is a little annoying, but all you need to do is do a little pen-and-paper calculations to make sure it's correct. Basically, you only need to worry about an element at the end of the list, at the beginning, and in a one-element list.

OK, now we're going to do a bit more complicated data structure, which is called a queue. You'll see, however, that the queue will look much like the doubly linked list, just with one extra pointer. The idea of the queue is that we push elements into one side, and then pop them out the other in the same order. It's basically "first-come first-served", or as computer scientists like to call it, FIFO (First-In First-Out). This is useful in many contexts. For example, a very high-speed Web server might keep a queue of HTTP requests. It would push requests into the queue as they came in, and handle the requests popping off the queue as fast as it could handle them.

Enough yapping, let's get to the code. We'll use the same LinkedListElement class as we did in the doubly linked list:

 CODE (C++) 
class Queue {

public:
    Queue( void )
    {
        m_pHeadElement = m_pTailElement = NULL;
    }

    void PushElement( int num )
    {
        LinkedListElement* pElement = new LinkedListElement( num );

        if( m_pHeadElement ) // queue is not empty
        {
            pElement->SetNextElement( m_pHeadElement );
        }
        else // queue is empty
        {
            m_pTailElement = pElement;
            pElement->SetNextElement( NULL );
        }
       
        pElement->SetPrevElement( NULL );
        m_pHeadElement = pElement;
    }

    int PopElement( void )
    {
        LinkedListElement* pElement = m_pTailElement;
        LinkedListElement* elem = m_pHeadElement;

        if( elem == pElement ) // queue has one or no objects
        {
            m_pTailElement = m_pHeadElement = NULL;
        }
        else
        {
            m_pTailElement = pElement->GetPrevElement();
            m_pTailElement->SetNextElement( NULL );
        }
       
        int ret = -1;

        if( pElement ) // m_pTailElement might be NULL
        {
            ret = pElement->GetNumber();
            delete pElement;
        }
        else
        {
            printf( "Popped an empty queue!\n" );  
        }

        return ret;    
    }

private:

    LinkedListElement* m_pHeadElement;
    LinkedListElement* m_pTailElement;
};


Hopefully it's clear how this works. Again, just take a moment to write out how it works for queues of different sizes. You'll notice that this is much simpler than the doubly linked list, since you don't have to have the ability to delete any element, just one.

OK, now we'll take a look at possibly the most useful data structure, the tree. Trees appear almost constantly in most programming applications. The basic way a tree works is that each element has "children" and a "parent". There is one element, called the "root", which has no parent, and many elements, called "leaves", who have no children.

The code I'll show you is called a binary tree, because each element has two children. This is often used for sorting and searching large sets. Each element is associated with an integer. The idea is that all the elements to the right of each element, that is, the children of the element's right child, have a larger integer, while all the elements to the left of each element have a smaller integer. This way, we can easily cut out sections of the tree that don't apply to us. So, for example, if we're looking for an element with the integer 50, and we come to an element with the integer 100, we know that the element we're looking for can't be in the right child of that element. So, if the tree is nicely balanced (meaning the left child and the right child of any particular element have about the same number of descendants), we can cut the search space by about half each time we check an element. If there are a thousand elements, and the tree is perfectly balanced, we will only have to check ten elements at maximum. Not too shabby. Moreover, if there are a million elements, and the tree is perfectly balanced, we only have to check twenty elements. Extra not too shabby.

In this particular case, we'll design the tree to store some data associated with an integer. Let's take a look at the code:

 CODE (C++) 
struct data { // lots of data here };

class TreeElement {

public:

    TreeElement( int ind, data* mydata )
    {
        m_iIndex = ind;
        m_pLeftChild = m_pRightChild = NULL;
        m_pData = mydata;
    }

    data* GetDataForIndex( int ind )
    {
        if( m_iIndex == ind )
        {
            return m_pData;
        }
   
        data* returndata = NULL;

        if( ind > m_iIndex )
        {
            if( m_pRightChild )
                returndata = m_pRightChild->GetDataForIndex( ind );
        }
        else
        {
            if( m_pLeftChild )
                returndata = m_pLeftChild->GetDataForIndex( ind );
        }

        return returndata;      
    }

    void AddElement( TreeElement* elem )
    {
        if( elem->GetIndex() > m_iIndex )
        {
            if( m_pRightChild )
                m_pRightChild->AddElement( elem );
            else
                m_pRightChild = elem;
        }
        else
        {
            if( m_pLeftChild )
                m_pLeftChild->AddElement( elem );
            else
                m_pLeftChild = elem;
        }
    }

    int GetIndex( void ) { return m_iIndex; }
private:

    data* m_pData;
    TreeElement* m_pLeftChild;
    TreeElement* m_pRightChild;
    int m_iIndex;  
};

class BinaryTree {

public:
    BinaryTree( void )
    {
        m_pRootElement = NULL;
    }

    void AddElement( TreeElement* elem )
    {
        if( m_pRootElement )
        {
            m_pRootElement->AddElement( elem );
        }
        else
        {
            m_pRootElement = elem;
        }
    }

    data* GetDataForIndex( int ind )
    {
        data* returndata = NULL;
       
        if( m_pRootElement )
        {
            m_pRootElement->GetDataForIndex( ind );
        }

        return returndata;
    }

private:

    TreeElement* m_pRootElement;
};


There we go! The main thing to notice here is that when you search for an integer, it only checks the appropriate child. Also, note how AddElement always makes sure that the element gets into the correct place in the tree. Trees are a little weird at first, mainly because they lend themselves to recursive code, but once you get the hang of them, they'll be an invaluable tool in your programming toolbox. (By the way, it's important to notice that in the above code, there isn't anything to keep the indices unique, i.e., to make sure that two datas aren't associated with the same integer. That's something you'd have to do yourself.)

I hope that this tutorial has been informative about basic data structures. Whenever you program, always be looking for opportunities to use these structures. They're helpful in several ways. One is that once you get used to writing them, you have less of a chance of making a logical error than if you wrote different code each time. Second, it allows other programmers reading your code to more easily conceptualize what you're doing if you put in a comment like "// Using a FIFO queue". Third, and this is especially true for trees, it's generally the best and fastest way to do something.

(By the way, in the STL, singly linked lists, doubly linked lists, queues, and trees are implemented as slist, list, queue, and map, respectively.)

Well, as usual, if there are any questions, you can post them on the Wavelength forums or email them directly to me at persuter@planethalflife.com.

Rate This Article
This article is currently rated: 5 out of 5.0 (2 Votes)

You have to register to rate this article.
User Comments

No User Comments

You must register to post a comment. If you have already registered, you must login.

Latest Articles
3rd person View in Multiplayer
Half-Life 2 | Coding | Client Side Tutorials
How to enable it in HL2DM

By: cct | Nov 13 2006

Making a Camera
Half-Life 2 | Level Design
This camera is good for when you join a map, it gives you a view of the map before you join a team

By: slackiller | Mar 05 2006

Making a camera , Part 2
Half-Life 2 | Level Design
these cameras are working monitors that turn on when a button is pushed.

By: slackiller | Mar 04 2006

Storing weapons on ladder
Half-Life 2 | Coding | Snippets
like Raven Sheild or BF2

By: British_Bomber | Dec 24 2005

Implementation of a string lookup table
Half-Life 2 | Coding | Snippets
A string lookup table is a set of functions that is used to convert strings to pre-defined values

By: deathz0rz | Nov 13 2005


Latest Comments
knock knock
General | News
By: omega | Dec 22 2016
 
knock knock
General | News
By: MIFUNE | Oct 10 2015
 
New HL HUD Message System
Half-Life | Coding | Shared Tutorials
By: chbrules | Dec 31 2011
 
knock knock
General | News
By: Whistler | Nov 05 2011
 
Particle Engine tutorial part 4
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 18 2010
 
Particle Engine tutorial part 2
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 11 2010
 
Particle Engine tutorial part 3
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 11 2010
 
Game Movement Series #2: Analog Jumping and Floating
Half-Life 2 | Coding | Shared Tutorials
By: mars3554 | Oct 26 2009
 
Particle Engine tutorial part 5
Half-Life | Coding | Client Side Tutorials
By: Deadpool | Aug 02 2009
 
Particle Engine tutorial part 5
Half-Life | Coding | Client Side Tutorials
By: Persuter | Aug 02 2009
 

Site Info
297 Approved Articless
8 Pending Articles
3940 Registered Members
0 People Online (18 guests)
About - Credits - Contact Us

Wavelength version: 3.0.0.9
Valid XHTML 1.0! Valid CSS!