3
$\begingroup$

I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash function servers the purpose of computing from the key the index in the array where the value is stored. I have also learned that trees may be stored as arrays. Given that arrays are said to be efficient (for lookup, if not insert/delete) due to the way they match memory addressing in the von Neumann architecture, is it generally the case that all other structures are basically "supersets" or "super-structures" of the array?

After all, the array is nothing more than a contiguous collection of memory "cells", so we can think of an int as a single cell array. And we can think of a struct as an array where elements are not necessarily of the same type. I struggle to think how any other data structure could be constructed in any other way, but I guess it's best that I ask here to be sure.

EDIT: Just to be perfectly clear and correct, I do understand that a memory cell and a data element are not necessarily the same thing, an element may occupy more than one memory cell. The distinction between the two is a minor detail that shouldn't detract from the question.

$\endgroup$
  • $\begingroup$ Would you consider linked lists to be "array-like"? $\endgroup$ – Yuval Filmus Oct 28 '19 at 9:35
  • $\begingroup$ My question is about how the structure is implemented, not whether the structure is itself array-like. I wouldn't consider a linked list to be array-like, but it would be part of my question: are linked lists implemented with arrays? Are all data structures so implemented? $\endgroup$ – Theo d'Or Oct 28 '19 at 9:38
  • $\begingroup$ CPUs access memory as a big array. In this sense, everything is an array. $\endgroup$ – Yuval Filmus Oct 28 '19 at 9:41
  • $\begingroup$ But does that also mean every structure is implemented with arrays? In addition to structs and primitive values like ints, floats and chars, which are array-like as indicated in my question. I want to understand whether trees, linked lists etc. are using arrays for their implementation. $\endgroup$ – Theo d'Or Oct 28 '19 at 10:52
  • $\begingroup$ I'm not sure what it means for a data structure to be implemented "with arrays". That's why I asked you about linked lists. I suggest taking a look at a standard implementation of linked lists in C. $\endgroup$ – Yuval Filmus Oct 28 '19 at 10:54
1
$\begingroup$

Your question is a bit vague, but it seems that you're missing one mechanism: dynamic memory allocation. Some data structures such as linked lists are heavily based on dynamic memory allocation, and so although linked lists are very similar to arrays in function, they are implemented very differently.

Dynamic memory allocation is treated as a primitive in C. System libraries are supposed to implement the malloc() and free() primitives, with the support of the operating system. While eventually memory is accessed (in the CPU level) as one long array (perhaps some of it implemented as virtual memory), this is all hidden under the hood as far as the C programmer is considered (unless they choose to tinker with it).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Our discussion of linked lists exposes the fact that my question is somewhat mis-stated, with too much focus on arrays, rather than the whole gamut of primitive, native offerings of C. I focused on arrays due to the discovery that hash tables are based on them, and that they may be the base of trees as well. Dynamic memory allocation doesn't change much, as it may be used to create arrays. I just wanted to be sure that there was no way of creating data structures - which C does not offer natively - in some native way that I didn't know about. It now seems obvious that this can't be done. $\endgroup$ – Theo d'Or Oct 28 '19 at 15:55
  • $\begingroup$ I think the answer to my question must be both "no" and "yes": no, arrays are not used by all non-native data structures, and yes, there is no way of creating such structures other than by using what C offers natively. All non-native data structures are "super-structures" of the native functionality. If you edit your answer to make this clear, I will accept it. $\endgroup$ – Theo d'Or Oct 28 '19 at 16:27
  • $\begingroup$ You’re welcome to write your own answer instead. $\endgroup$ – Yuval Filmus Oct 28 '19 at 16:38
  • $\begingroup$ I don't want to do that as I could be wrong. I'm looking for an authoritative answer. $\endgroup$ – Theo d'Or Oct 28 '19 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.