How to program my own arrays and lists

Question

I need to program several different types of binary trees. However, I am not allowed to use utils, such as arrays or collections. It is suggested to create your own array, if necessary. The problem is that I don’t even know where to start. How can I build, say, a 2D array?

Answer 1

You will have to manually create a linked list or tree by creating objects, each of which contains a pointer to the next object in the list or tree. This is an exercise that we have done many times in our class of data structures when I was in school. A useful exercise is understanding how to keep a list or tree intact through insertions and deletions.

  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 do not need arrays to build a tree. There are several books on algorithms and data structures if you do 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 the question: for a 2d array, create a 1d array and save the 1d arrays in the 1d array. You can emulate the built-in arrays by creating your own implementation of linked lists. But that doesn’t mean the teacher has in mind.)

(inspiration for the actual question, that you do not know what you are asking:

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

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

Answer 3

with a linked list. here is the code: http://www.roseindia.net/java/jdk6/LinkedListExample.shtml

Answer 4

Change Well, all the lists are mentioned, but do not forget that you can implement binary trees also on arrays, for example, on heaps. So we have something like:

 public class BinaryTree { private int[] tree; // assuming each node holds an integer. private int nodeCount; public BinaryTree (int nodes) { tree = new int[nodes * 2]; nodeCount = nodes; } public int getRoot() { return tree[0]; } private int getPositionOfNode(int value) { for(int i = 0; i < nodeCount; i++) { if(tree[i] == value) { return i; } } return -1; } public int getLeftChildOfNode(int node) { int pos = getPositionOfNode(node); if(pos != -1) { return tree[pos * 2]; } return pos; } public int getRightChildOfNode(int node) { int pos = getPositionOfNode(node); if(pos != -1) { return tree[pos * 2 + 1]; } return pos; } public int getParentOfNode(int node) { int pos = getPositionOfNode(node); if(pos != -1) { return tree[pos / 2]; } return pos; } } 

In this structure, if a node is in position i, its children will be in positions 2 * i and 2 * i + 1.

Answer 5

 public class TwoDArray { private Object[] values; public TwoDArray(int n, int m) { values = new Object[n * m]; } public void set(int i, int j, Object x) { ... } public Object get(int i, int j) { ... } } public class BinTree { private BinTree left; private BinTree right; private Comparable value; public void insert(Comparable x) { ... } } 

Something like that? It shouldn't be that hard.

Answer 6

I will start by assuming that you are forbidden to use even primitive types of Java arrays. In this case, you will have to go back to the basics and start managing the memory yourself. You will need to start by allocating a byte array or ByteBuffer of the appropriate size. Then access to this data block will be processed using what would be simple math pointer in C.

Example 1D array of 16 ints:

 byte[] mem = new byte[16 * 4] ; // Ints are 4 bytes long // Write a value to the 8th element of our "array" index = 8 ; int value = 31415926 ; mem[4 * index + 0] = (byte)( value >> 24 ) ; mem[4 * index + 1] = (byte)( ( value << 8 ) >> 24 ) ; mem[4 * index + 2] = (byte)( ( value << 16 ) >> 24 ) ; mem[4 * index + 3] = (byte)( ( value << 24 ) >> 24 ) ; 

Reading a value outside this would be reversing the process and calculating the stored int value.

Note. The process of setting and getting values ​​is simpler with ByteBuffer, as it allows you to get and put primitive Java types into an array of bytes.