Data Structure Programming

• Data structure programming usually requires the manipulation of large amount of data. The exact size of data is unknown during the compile time. Therefore, regular array would not be useful since it requires the exact knowledge of the size.
• Object-oriented programming helps to simplify the programming by introducing the concept of ‘object’ for each unit of data.
• Source code and example usage of linked-list, stacks and trees are presented here to illustrate the usage of each technique.

Stacks

• Stacks is the easiest among data structure techniques. It functions based on FILO(First In Last Out) concept. The first element pushed on top of stack becomes the last to be popped out.

Figure 1. Stack operation.

• Depends on the object type, different stack frames are needed each target object. Integers require different stack frame compared to floating-point.
• CStack template class is created to avoid the need to create separate management code. The same code is reusable for every object.
• For example

CStack<int> intStack;

CStack<float> floatStack;

CStack<userdefined> userStack;

intStack.Push(…)

userStack.Push(…)

Singly Linked-List

• Singly linked-list is the collection of data by arranging data units into a chain.
• Each data unit(node) contains a pointer which points to the next element.
• Depends on the object type, different node frames are needed each target object. Integers require different node frame compared to floating-point.
• Different from arrays which need to be declared its size upon instantiation, singly linked-list allocates memory dynamically.
• CSinglyList template class is created to avoid the need to create separate management code. The same code is reusable for every object.
• For example

CSinglyList<int> intList;

CSinglyList<float> floatList;

CSinglyList<userdefined> userList;

intList.Insert(…)

userList.Next(…)

Figure 2. Singly List operation.

• Source code with an example usage:

• For  proper compilation, it is suggested that the user extracts the files according to the directory structure in the zipped file, ie unzip to the root directory using folder names.
• The example given demonstrates the usage of singly linked-list to hold the pets and its name. 

• SinglyList.zip - SinglyList example and usage.

 

Doubly Linked-List

• Doubly linked-list is the collection of data by arranging data units into a chain.
• Each data unit(node) contains a pointer which points to the next element and a pointer to the previous element.
• Depends on the object type, different node frames are needed each target object. Integers require different node frame compared to floating-point.
• Different from arrays which need to be declared its size upon instantiation, singly linked-list allocates memory dynamically.
• Doubly linked-list is preferred over singly linked-list in the case where elements in the list are needed to be scrolled to and fro from current node frequently.
• CDoublyList template class is created to avoid the need to create separate management code. The same code is reusable for every object.
• For example

CDoublyList<int> intList;

CDoublyList<float> floatList;

CDoublyList<userdefined> userList;

intList.Insert(…)

userList.Next(…)

Figure 3. Doubly List operation.

Binary Tree

• Binary tree structure is used when the order of data unit(node) is critical. The nodes are arraged in tree-like structure based on logical difference between nodes, ie "greater than(>)" or "lesser than(<)".
• Each node contains a "left" pointer which points to the left node in the hierarchy which logically lesser than current node. It also contains a "right" pointer which points to the right node which is greater than current node.
• There should not be more than 1 identical node in the list.
• Since the tree is organized when each node is inserted. Finding specific node in the list is fast. It needs not visit all nodes in order to find a node.
• However, the nodes should be inserted as random(not by ascending or descending order) as can be during the creation of tree to obtain a balanced tree. Otherwise, the tree reduces to singly linked-list.
• CTree template class is created to avoid the need to create separate management code. The same code is reusable for every object.
• For example

CTree<int> intList;

CTree<float> floatList;

CTree<userdefined> userList;

intList.Insert(…)

userList.Left(…)

Figure 4. Doubly List operation.

• Source code with an example usage:

• For  proper compilation, it is suggested that the user extracts the files according to the directory structure in the zipped file, ie unzip to the root directory using folder names.
• The example given demonstrates the usage of binary tree to store pets in sorted order.

• BinTree.zip - Binary tree example and usage.