1. Some Basic Datastructures

Last Update: 24. March 1998

1.0 Preface

'I want to program games, do I really need these stupid datastructures they lecture here at university?'. I once stumbled over a this question on some newsgroup and the answer is: datastructures are the basis on which games are usually build. Why? Because games usually handle a lot of information (where player is, where is he going, what does he see, where are all the hundreds of enemies, where are they going, in what 'mood' are they etc.) in real time and using the right datastructure in the right place can make a huge difference in speed. The datastructures presented here are really not optimized versions, but rather introductions to the consepts. I might write a chapter called 'Some Optimized Datastructures' one day, but we'll have to see about that later. The last structure (Finite Automata) is really not a data structure (in conventional sense), but I thought it would be good to present it here.

Code examples in this chapter were done before JDK 1.1 was finished, so they should compile ok on any current JDK version. If you wan't to 'port' these structure examples to make better use of the new features in JDK versions 1.1.x, you could start by moving all the 'node' classes as inner classes of those classes that use them and maybe renaming them as simply 'nodes' (instead of 'stackNode' you would have an inner class in the 'stack' class called 'node').

Datastructures organize information that is contained in same type of objects. This ordering can be achieved in many ways e.g..

• Collecting all the objects in to a table
• Attaching information (a reference in Java) to the objects about the other objects that are related to it.

Datastructures can be divided in:

• Linear structures: All data cells (nodes) have one defined predecessor or successor or both.
• Nonlinear structures: A data cell can have several predecessors or successors.

1.1 Stack

Stack is a so called LIFO- structure (Last In First Out). That means that the last node added to the stack is the first one to be removed.

The basic operations affect the top of the stack:

• Push: A new node is added to the top of the stack.
• Pop: A node is removed from the top of the stack.

A stack can be implemented in Java like this:

• We define two classes called stackNode and stack:
• stackNode contains a reference to the stored data (that can be any Java object) and a reference to the next node in the stack.
• stack is the main class, that uses the stackNode class and makes it possible to add and remove nodes to the stack.
• The node at the bottom of the stack has a null reference pointing the next element.
• A reference to the topmost node is stored in the stack class, that handles both the adding and removing of nodes.

Graphical representation

We mark the null reference with symbol

Stack

 

Adding an node to the stack (push)

 

Removing an node from the stack (pop)

 

 

Code example

Here is a directly compileable Java class, that uses any Java class as data. Just copy and paste it to your text editor and save it as 'stack.java'
(Note: This implementation is highly inefficient and rude as you have to typecast every object you get from the stack. This also means that you'll have to know the type of the stored data):

public class stack
    {
    private node TOP = null;

      // Add an node to the stack
    public void push (Object data)
        {
        stackNode newnode = new node (data);
        newnode.next = TOP;
        TOP = newnode;
        }

      // Remove an node reference from the
      // stack and return it to the caller
    public Object pop ()
        {
        stackNode pointer = TOP;
        if (TOP != null) TOP = TOP.next;
        return pointer.data;
        }
    } // End of class stack

class stackNode
    {
    Object data;
    stackNode next;

    public stackNode (Object data)
        {
        this.data = data;
        this.next = null;
        }
    } // End of class stackNode

1.2 Queue

Queue is a so called FIFO- structure (First In First Out). That means that the first node added to the queue is removed first.
All the basic operations affect the ends of the queue:

• Enqueue: A new node is added to the tail of the queue.
• Dequeue: An node is removed from the head of the queue.

A queue can be implemented in Java like this:

• We define two classes queue and queueNode:

• queueNode contains the reference to the stored data (can be any Java object) and a reference to the next node in the queue (when order is from the head to the tail).
• queue is the main class, that uses the queueNode class and makes it possible to add and remove nodes. It contains also references to the first and the last node in the queue.

 

Graphical representation

Queue

 

Adding an node to the queue (enqueue)

 

Removing an node from the queue (dequeue)

 

Code example

Here is a directly compileable Java class, that uses any Java class as data. Just copy and paste it to your text editor and save it as 'queue.java'
(Note: This implementation is highly inefficient and rude as you have to typecast every object you get from the queue. You also have to know the type of the stored data at all times):

public class queue
    {
    queueNode HEAD = null;
    queueNode TAIL = null;

      // Add an node to the queue
    public void enqueue (Object data)
        {
        queueNode newnode = new queueNode(data);
        newnode.next = null;

          // Is the queue empty?
        if (HEAD != null)
            {
            TAIL = newnode;
            }
            else
                {
                  // First node is added to the queue
                HEAD = newnode;
                }

        TAIL = newnode;
        }

      // Remove an node reference from the
      // queue and return it to the caller
    Object dequeue ()
        {
        queueNode pt = HEAD;
        if (HEAD != null) HEAD = HEAD.next;
        return pt.data;
        }
    } // End of class queue

class queueNode
    {
    Object data;
    queueNode next;

      // Constructor is given the stored data as a parameter
    public queueNode (Object data)
        {
        this.data = data;
        this.next = null;
        }
    } // End of class queueNode

Queues are often used to implement buffers:

• A routine in a program outputs infromation that another part of the program uses as input.
• It is often inpractical or impossible to handle the reading and writing synchronously (e.g. a terminal program that displays text: characters arrive from the outside world at unpredictable moments and they can arrive at times too fast for the display to keep up)
• This asynchronous problem can be handled easily with buffers: Incoming data is added to the end of the buffer and is read from the beginning of the buffer.
• Buffers are usually implemented as circular buffers. That means a stack whose last node is linked to the first element.

1.3 Doublelinked List

In doublelinked list structure every node has a reference to its immediate predecessor and successor.
The basic operations can affect any node in the list:

• insert: A new node is added as some other nodes immediate predecessor or successor
• delete: An node is removed from any point at the list.

A double linked list can be implemented in Java like this:

• We define two classes linkedList and linkedListNode:

• linkedListNode holds the references to the stored data (can be any Java object) and a reference to the next and previous element.
• linkedList is the main class of double linked list. It uses the linkedListNode class and makes it possible to add and remove nodes. It also contains a reference to the first node in the list

Graphical representation

Doublelinked list

 

Adding an node to the double linked list (insert)

 

Removing an node from the double linked list   (delete)

 

Code example

Here is a directly compileable Java class, that uses any Java class as data. Just copy and paste it to your text editor and save it as 'linkedList.java'
(Note: This implementation is highly inefficient and rude as you have to typecast every object you get from the queue and you'll have to know the type of the stored data):

public class linkedList
    {
    linkedListNode HEAD = null;

      // Add an node as successor of some node
      //(curr = null means that the list is empty)
    void append (linkedListNode curr, Object data)
        {
        linkedListNode newnode = new linkedListNode(data);
        if (curr != null)
            {
              // The list was not empty
            newnode.prev = curr;
            newnode.next = curr.next;
            if (curr.next != null) curr.next.prev = newnode;
            curr.next = newnode;
            }
            else
                {
                  // The list was empty
                newnode.prev = newnode.next = null;
                HEAD = newnode;
                }
    }

      // Add an node as predecessor of some node
      //(curr = null means that the list is empty)
    void prepend (linkedListNode curr, Object data)
        {
        linkedListNode newnode = new linkedListNode(data);
        if (curr != null)
            {
              // The list was not empty
            newnode.next = curr;
            newnode.prev = curr.prev;
            if (curr.prev != null)
                {
                  // The node is NOT the first node
                curr.prev.next = newnode;
                }
                else
                    {
                      // The node IS the first node
                    HEAD = newnode;
                    curr.prev = newnode;
                    }
            }
            else
                {
                  // The list was empty
                newnode.prev = newnode.next = null;
                HEAD = newnode;
                }
        }

      // Remove an node from the list(delete)
    public Object remove(linkedListNode curr)
        {
        if (curr.prev != null)
            {
              // The node is NOT the first node
            curr.prev.next = curr.next;
            }
            else
                {
                  // The node IS the first node
                HEAD = curr.next;
                }
        if (curr.next != null)
            {
            curr.next.prev = curr.prev;
            }
        return curr.data;
        }
    } // End of class linkedList

class linkedListNode
    {
    Object data;
    linkedListNode prev;
    linkedListNode next;

    public linkedListNode (Object data)
        {
        this.data = data;
        this.next = null;
        this.prev = null;
        }
    } // End of class linkedListNode

1.4 Binary tree

• Each node in a binary tree has either:

• Left or right (or both) child. In this case that node is a root of a subtree.
• No children. In this case that node is called a leaf.

• Every node in the binary tree (except for the root of the whole tree) has an immediate predecessor or parent.
• Except for the leafs, every node has either one or two successors.
• Childrens of same parent node are called siblings.
• If an node can be reached from some other node by following an parent-child-chain, it is said that these nodes are connected by a path. The length of the path is the number of nodes in the path.
• Every node in the binary tree has a path from the root node of the tree. The height of an node is the length of that path. The height of a binary tree is the length of the longest path it contains.
• nodes connected by a path are in predecessor- successor relationship with eachother.
• Binary tree is called as a non-linear structure because of any two nodes it holds, neither has to be a successor (or predecessor) of the other.

Graphical representation

 

Traversal of the tree

A binary tree can be traversed in three ways:

inorder: left subtree, current element, right subtree

1. Go through the left subtree in inorder order
2. Go through this current node
3. Go through the right subtree in inorder order

preorder: current element, left subtree, right subtree

1. Go through this current node
2. Go through the left subtree in preorder order
3. Go through the rigth subtree in preorder order

postorder: left subtree, right subtree, current node

1. Go through the left subtree in postorder order
2. Go through the left subtree in postorder order
3. Go throught this current node

An example: Counting how frequently a word appears in a text

• We define a stringTreeNode class that holds a word and the how many times it has appeared in a text. stringTreeNode also contains a reference to the left and right child (if any).
• We define a treeNode class that holds a reference to the root element. This class also uses the stringTreeNode class and organizes the tree so that every nodes left child holds a word that is before that nodes word in alphabethical order and every right childs word is after that nodes word in alphabetical order.
• We define a method in stringTreeNode class called treeprint, that traverses the tree in inorder order and prints out the words and how many times that word appeared in the text from any given element.

 

Code example

Here is a directly compileable Java class, that uses any Java class as data. Just copy and paste it to your text editor and save it as 'stringTree.java':

import java.io.*;

public class stringTree
    {
    public stringTreeNode addNode(stringTreeNode curr, String word)
        {
        int cmp;
        if (curr == null)
            {
            curr = new stringTreeNode(word);
            curr.left = curr.right = null;
            }
            else
                {
                cmp = word.compareTo(curr.word);
                if ( cmp == 0)
                    {
                    curr.count++;
                    }
                    else if (cmp < 0)
                        {
                        curr.left = addNode(curr.left, word);
                        }
                        else
                            {
                            curr.right = addNode (curr.right, word);
                            }
                }
    return curr;
    }

    public void treeprint (stringTreeNode curr)
        {
        if (curr != null)
            {
            treeprint (curr.left); // Print the left subtree
            System.out.println(curr.count+"\t"+curr.word);
            treeprint (curr.right); // Print the right subtree
            }
        }
    } // End of class stringTree

class stringTreeNode
    {
    String word;
    int count = 0;
    stringTreeNode left = null;
    stringTreeNode right = null;

    public stringTreeNode (String word)
        {
        this.word = word;
        this.count++;
        }
    } // End of class stringTreeNode

• And we create the main class that uses the stringTree class above and reads text from the standard input stream and separates a word at a time and returns a value LETTER, if word is made of letters.

Here is a directly compileable Java class, that uses any Java class as data. Just copy and paste it to your text editor and save it as 'wcount.java':

import java.io.*;
public class wcount
    {
    public static void main (String[] args)
        {
        stringTreeNode root = null;
        stringTree tree = new stringTree();
        StreamTokenizer inputSource = new StreamTokenizer(System.in);
        inputSource.eolIsSignificant(true);
        try
            {
            inputSource.nextToken();
            }
            catch (IOException ioe)
                {
                System.out.println("Exception!\n"+ioe+"\n");
                }
        while (inputSource.ttype != inputSource.TT_EOL)
            {
            if (inputSource.ttype == inputSource.TT_WORD)
                {
                root = tree.addNode(root, inputSource.sval);
                }
            try
                {
                inputSource.nextToken();
                }
                catch (IOException ioe)
                    {
                    System.out.println("Exception!\n"+ioe+"\n");
                    }
            }

        System.out.println("Tree root: \""+root.word+"\"");
        System.out.println("\nCount:"+"\t"+"Word:");
        tree.treeprint(root);
        }
    }  // End of class wcount

Some notes about binary trees:

• Binary trees are mostly used in sorting of data and finding the sorted data (fast). These trees are called search trees.
• If every leafs height in the tree is approximately the same (the tree is balanced) any node can be found (or we can come to conclusion that it doesnt exist in this tree) with log2 n operations, where n is the number of the nodes strored in the tree.
• In the worst case, when a tree is totally made of only left (or right) children, a search takes n operations.
• So called balanced tree structures (B-trees) quarantee that only log2 n operations are used in search.

1.5 Finite Automata

A finite automata consists of

1. A finite group S = {s1,s2, ... ,sn} of states si
2. A finite group C = {c1,c2, ... ,cn} of input characters ci
3. Description t: S x C -> S

A finite automaton can be considered a machine that changes it state from si to sk = t(si, cj) when it reads an input character cj. Usually before the starting (before the machine has read a single character) it is in a defined starting state. The machine stops, when it goes to a so called terminal states (f, t(f, C) = 0).

Graphical representation

 

Code example

Counting the words and lines in an input file:

Characters are classified in the class Chartype:

• WHITE: a whitespace- character (' ', '\t')
• NEWLINE: a line change ('\n')
• EOF: end of file

States are classified in the class State:

• START: the beginning state
• WORD: the read a word state
• STOP: the ending state

We define a class Counter that implements the finite automata presented above.

public class Counter
    {
    private State state = new State();
    private Chartype chartype = new Chartype();
    private int counterState;
    private int lines;
    private int words;

    public Counter()
        {
        Reset();
        }

      // Reset the classes state and both counters
    public void Reset()
        {
        counterState = state.START;
        lines = words = 0;
        }

      // Return the number of lines
    public int getLines()
        {
        return lines;
        }

      // Return the number of words
    public int getWords()
        {
        return words;
        }

      // Do counting based on given type and current state
    public boolean Count (int type)
        {
        switch (counterState)
            {
            case state.START:
            switch (type)
                {
                case chartype.EOF:
                counterState = state.STOP;
                return false;

                case chartype.CHARACTER:
                words++;
                counterState = state.WORD;
                return true;

                case chartype.NEWLINE:
                lines++;

                case chartype.WHITE:
                return true;
                }

            case state.WORD:
            switch (type)
                {
                case chartype.EOF:
                case chartype.NEWLINE:
                lines++;

                case chartype.WHITE:
                counterState = state.START;

                case chartype.CHARACTER:
                return true;
                }

            case state.STOP:
            return false;
            }
        return false;	// If this is reached there has been an error!
        }
    }  // End of class Counter

class State
    {
    public final int START = -1;
    public final int WORD  = -2;
    public final int STOP  = -3;
    }  // End of class State

class Chartype
    {
    public final int WHITE     = -1;
    public final int NEWLINE   = -2;
    public final int CHARACTER = -3;
    public final int EOF       = -4;
    }  // End of class Chartype

• We also define a main class CountInStream that counts the number of lines and words it receives from the standard input stream by using the Counter object

import java.io.*;

class CountInStream
    {
    Chartype chartype = new Chartype();

    public static void main(String[] args)
        {
        Counter lwcounter = new Counter();
        CountInStream countObject = new CountInStream();
        while ( lwcounter.Count( countObject.nextchar() ) );
        System.out.println("Words:"+lwcounter.Words()+"\nLines:"+lwcounter.Lines());
        }

    public int nextchar()
        {
        int input;
        char inputChar;
        try
            {
            input = System.in.read();
            if (input == -1)
                {
                return chartype.EOF;
                }
            inputChar = (char) input;
            if (inputChar =='\n')
                {
                return chartype.NEWLINE;
                }
            if ( (inputChar == ' ') || (inputChar == '\t') )
                {
                return chartype.WHITE;
                }
            }
            catch (IOException ioe)
                {
                System.out.println("Exception!\n"+ioe);
                }
        return chartype.CHARACTER;
        }
    }  // End of class CountInStream