Building a data structure

4 minute read


In today’s writing, I want to think about building up a data structure. The data structure I’m aiming for is an array. The question is: where to start?

Starting with a simple memory

One course I taught last semester was an introductory course in VHDL, CET466 Logic Design at Central Connecticut State University. One of the questions on the final exam gave the students the VHDL listing below and asked them what it does.

This code is what I’d call a dual-port memory: it’s a memory device that can be read from and written two at the same time via two separate address and data busses. This particular instance is very small: it has two bits for the address lines and four bits for the data. That there are only two bits for the address lines means it has a total of four different possible addresses (00,01,10, and 11).

Moving to a real computer

The VHDL code above was run on an Altera FPGA board like the one shown below. This is a small FPGA, but it is even smaller compared with general purpose computers.

A real computer’s memory is significantly bigger. A real desktop or laptop computer is probably a 64-bit machine. That 64 means that the address space is 64 bits instead of the two bits in the above VHDL code. That implies a total number of addresses of 264 or 18,446,744,073,709,551,616 pieces of memory.

The other difference between the VHDL code above and the real memory is that the data width is generally a byte or 8 bits.

There are some limitations. Most computers can’t actually use all 64 bits. They are limited to either 48 or 52 bits, however this is not a practical limitation as, currently, no computer can physically house that amount of memory.

A simple example

Rather than deal with 64-bit addresses, I’m going to simplify things and look at where I started my computing journey with 16-bit addresses. This means that instead of writing an address as 0xdeadbeefdeadbeef in hexadecimal we can write it as 0xc035.

I’ll keep the data size of 8 bits (1 byte).

So a part of the computer’s memory could look like this:


Now suppose we want to do something like this in Java:

byte example[];    		// declaring array
example = new byte[5];	// allocating memory to array

or this in C++:

char example[5];


char *example;
example = new char [5];

Differences between Java and C++

Note that the syntax in the Java and C++ is quite similar in many ways. However, there are differences:

  • Java has a byte type. To get something similar in C++ we need to use the char type.
  • C++ has two ways to make an array of a particular size. One uses the array syntax, the other uses pointer syntax.

The other big difference between Java and C++ is that Java has a virtual machine that manages memory and C++ doesn’t. The upshot of that is whenever the new keyword is used in C++, there must be a delete keyword somewhere to clean up the allocated memory. We’ll talk more about this much later.

What does this look like in our 16-bit memory world?

So, getting back to our example, we’ve allocated memory for a length five array.

VariableAddressValueJava AccessC++ Access 1C++ Access 2
none0x00000x00 N/A N/A N/A
example0x10000x00 example[0] example[0] example
0x10010x00 example[1] example[1] example + 1
0x10020x00 example[2] example[2] example + 2
0x10030x00 example[3] example[3] example + 3
0x10040x00 example[4] example[4] example + 4
none0xffff0x00 N/A N/A N/A

Much more to talk about

There is much more to talk about. The above is a simplistic view of how memory gets allocated. For example, both Java and C++ use different parts of memory for different things: the stack, the heap, and static.

However, this was aimed as just a starting point. I’ll return to a more detailed discussion of this at a later stage.