2

I know what arrays are and how to use them. However, I don't know how they are implemented. I was trying to figure out if I can try to implement an array-like data structure using Java but I couldn't.

I've searched online but didn't find anything useful.

Is it even possible to implement an array-like data structure in Java? Is it possible in other languages? if so how (without using arrays of course)?

EDIT: what I want to know is how to implement an array data structure without using arrays?

Mido
  • 504
  • 2
  • 6
  • 18
  • yes. you can implement array like data structure in java and other languages[c,c++] – Shriram Feb 02 '15 at 09:54
  • 3
    What is an "array-like data structure", and why are you trying to implement your own? What do you want it for? – chrylis -cautiouslyoptimistic- Feb 02 '15 at 09:54
  • What do you mean an "array-like" structure? Sure, it is possible. create a class which contains an array (type Object). In the constructor, you set the length, or the initial data. Other manipulations go through methods. – Stultuske Feb 02 '15 at 09:54

3 Answers3

12

Arrays are contiguous sections within memory, so to create an array you would need to reserve a chunk of memory which is of size n * sizeof(type), where n is the amount of items you would like to store and the sizeof(type) would return the size, in bytes which the JVM would need to represent that given type.

You would then store a reference (pointer) to the first location of your memory segment, say 0x00, and then you use that as a base to know how much you need to move to access the elements, so a[n] would be equal to doing 0x00 + (n * sizeof(type)).

The problem with trying to implement this in Java is that Java does not allow pointer manipulation, so I do not think that building your own array type would be possible since you cannot go down to that level.

That being said, you should be able to create a linked data structure, where the nth element points to the (n + 1)th element.

Other problems why you should try other languages, such as C# (check unsafe operations), C++ or C:

  1. To my knowledge, Java does not have a sizeof function (see this).
  2. Java does not allow operator overloading. So you cannot define your own indexing operators such as [index]. You would probably need to do something like array.getElementAt(0) to get the first element.

As @ug_ recommended, you could take a look at the Unsafe class. But also as he recommended, I do not think that you should do pointer arithmetic with a language which has pointer abstraction as one of its core ideas.

Community
  • 1
  • 1
npinti
  • 51,780
  • 5
  • 72
  • 96
  • Good answer, but I would point out that you *could* do something silly with the `sun.misc.Unsafe` class that uses memory locations. However doing so would be ill advised. – ug_ Feb 02 '15 at 10:04
  • @ug_: Thanks for the information. To be honest I did not know that such class existed. Updated answer as per your recommendation. – npinti Feb 02 '15 at 10:10
0

If what you want is something like this:

MyArray ma = new MyArray(length);
ma[0] = value;

Then you can't do this in Java but you can in other languages. Look for "operator overloading".

Paco Abato
  • 3,920
  • 4
  • 31
  • 54
  • You can do this in C# / .NET, you can add an indexing property `[index here]` to your class, so you can do `myClass["foo"]` or `myClass[0]` – Davio Feb 02 '15 at 10:06
  • You can do it also in python and other languages. It's up to the OP to look for alternatives fitting his needs. – Paco Abato Feb 02 '15 at 10:19
0

I'm wondering if your thinking of a structs, vectors or link lists. These are all similar to arrays but are different.

Structs are not really in java, but you can implement them.

Read up on Structs here: www.cplusplus.com/doc/tutorial/structures/

An example Structs used in java: Creating struct like data structure in Java

I think what you are really looking for though are vectors. They are very similar to an array, but their not one.

Vectors info: www.cplusplus.com/reference/vector/vector/

Array compared to vector: https://softwareengineering.stackexchange.com/questions/207308/java-why-do-we-call-an-array-a-vector

I recommend a link list. Its kinda the same idea of an array, but without knowing your exact size. It is easier to implement.

Link lists: en.wikipedia.org/wiki/Linked_list

All these come down to the situation on what need them for. Saying , "what I want to know is how to implement an array data structure without using arrays?" is kinda open ended.

Community
  • 1
  • 1