How to program my own arrays and lists

Question

I have to program several different types of binary trees. However, I'm not allowed to use utils such as arrays or collections. It is suggested to build my own array, should there be a need for it. The problem is, I don't even know where to start with this. How could I build, say, a 2D array?

Answer 1

You will have to manually create a linked list or tree through the creation of objects which each contain a pointer to the next object in the list or tree. This is an exercise that we did many times in our data structures class when I was in school. Understanding how to keep the list or tree intact through inserts and deletes is a useful exercise.

public class ListNode<T> {
  private T payload;
  private ListNode<T> nextNode;
}

public class TreeNode<T> {
  private T payload;
  private TreeNode<T> leftChild, rightChild;
}

Answer 2

You won't need arrays for building a tree. There are several books about algorithms and data structures, if you will not find what you need on wikipedia:

http://en.wikipedia.org/wiki/Binary_tree

or http://en.wikipedia.org/wiki/List_of_data_structures

(answer to question: For a 2d array, create an 1d array, and store 1d arrays in a 1d array. It is possible to emulate built in arrays by creating your own linked list implementation. But it's neither effient nor what your teacher is having in mind.)

( inspiration for the actual question, that you don't know you are asking:

Something like this is the core data structure for a binary search tree...

class Node {
     Object value;
     Node left;
     Node right;
} )