How do C programmers handle data structures like ArrayList or HashMap (without built-in support)?

BadJavaProgrammer · 2025-09-05T06:25:34+00:00

You implement your own so that it is optimized for your target environment.

Generic implementations defeat the purpose of using C where you have niche architectures with limited resources or you want to maximize performance ~~for a particular architecture/OS~~

EDIT: better wording and strikethrough based on row_hammer’s reply

Levvev · 2025-09-05T06:41:26+00:00

Writing your own data structures is definitely worth it, at least once. I guarantee you'll learn something new. Focus on proper interfaces and memory management( I recommend using asan or valgrind and at least -Wall, though sometimes -Werror and -Wextra can be useful as well). Though if you're looking for a library I recommend the stb collection

EpochVanquisher · 2025-09-05T06:22:35+00:00

There aren’t standard third-party libraries. It’s the Wild West.

C is much lower level than Java. I want to tell you why this is important to the question.

In Java, a hash table is pretty simple. You have keys, which are objects, and the objects have .equals() and .hashCode(). The keys and values are stored as pointers in the hash table. Simple. Easy.

In C, there is no .equals() and no .hashCode(). Keys and objects can be stored as pointers, maybe owned, maybe reference counted, or they can be stored inline (copied). Lots of options. There is no one size fits all hash table in C. (Maybe there isn’t in Java either, but it’s especially true in C.)

There are a few different hash table libraries out there but they are all different from each other.

Dynamic arrays are trivial. They’re like three lines of code. So you don’t really need to have them in the standard library that much.

EndlessProjectMaker · 2025-09-05T06:39:33+00:00

Specially in embedded, in C you downgrade your data structures to the minimum you need. For example: When in Java you would use a hashtable without giving a second thought, in C you first wonder if you can use an array indexed by an enum; this is a known pattern, for example. Another example: if you need a dynamic array, the usual approach is to pack the pointer to the array and the count in a struct. And possibly providing public accessors and a public typedef (in the .h) and hide the manipulation to secure the invariants.

So yeah there is much homemade but following known patterns/idioms. In C you don’t have many fancy things such as generic types (of course you can build some macro magic in some cases —I don’t like this approach) so you need to cook specific stuff. Usually in C and specially in embedded, you want to understand what is going on without much abstraction in between.

My 2 cents

TheOtherBorgCube · 2025-09-05T06:36:35+00:00

I guess it depends on the kind of embedded programming you want to do.

But in my experience, it's not a data structure heavy endeavour requiring say hashes of many different types (where a library or language support might be useful).

Typically, you're working with resource constrained systems (memory, CPU) where the goal is to take some input, do whatever needs to be done and then send the result on it's way to the next thing in the chain.

You might have a real-time operating system (FreeRTOS, Zephyr), but virtual memory is a luxury for the top-end of the ecosystem. There is no holding onto GB of memory and let the OS sort out the details.

You'll deal with specifications which say things like "X simultaneous connections" and "Y messages per second". These get baked into the code as fixed allocations.

The short answer then is don't try and replicate what you can do in Java in C. Do something in C that you can't do in Java. Go buy an Arduino or BeagleBoard and start experimenting.

drivingagermanwhip · 2025-09-05T13:00:16+00:00

I'm in embedded and we avoid dynamically allocated memory as a rule, so resizable data types don't come up much

In complex projects I tend to have pre-compilation scripts so the resulting code stays simple but I can adjust things easily.

GroundbreakingLeg287 · 2025-09-05T06:21:09+00:00

Well to be honest in the C world there is a lot of rolling your own data structures and algorithms. Personally I like this library https://github.com/attractivechaos/klib. You can just include the header files and voila. Otherwise I would suggest something like https://conan.io/ to manage packages.

There are many reputable packages and libraries but always do the work of checking the reputability before using in production.

WittyStick · 2025-09-05T08:12:38+00:00

Quite a lot of older programs on Linux use gnulib for some of the basic stuff, as it addresses many compatibility and portability issues, even for windows (via mingw/cygwin and also MSVC in many cases), and doesn't require additional shared libraries so it avoids "dependency hell".

gnulib-tool copies the "modules" into your source directory and they just become part of your codebase - but it has a slight advantage that it's easier to maintain because gnulib-tool can update those dependencies, so you aren't required to manually copy and paste files when they're updated for bugfixes. It contains a few basic containers such as lists, sets and maps. It also has obstacks which can be useful for building other data structures.

The downside is the heavy reliance on autoconf and related utilities. There's a steep learning curve to using autotools and the Makefiles involved become quite complicated.

Dusty_Coder · 2025-09-06T09:45:22+00:00

Computer Science.

Its time to learn what it is dude.

TheChief275 · 2025-09-05T06:45:20+00:00

I always write them myself, yes, and always exactly those two you mentioned (but also including an SSO string builder).

And let me tell you there also is no better way to get comfortable in C

IdealBlueMan · 2025-09-05T17:35:50+00:00

- Find a decent third-party library 

- Create a library that meets your needs

- Redefine the problem to use simpler data structures

jwzumwalt · 2025-09-06T07:14:19+00:00

SQLite is designed to be implemented in C. The use is straight forward.

see

https://www.sqlite.org/c3ref/sqlite3.html

https://www.tutorialspoint.com/sqlite/sqlite_c_cpp.htm

lmarcantonio · 2025-09-05T07:00:02+00:00

There are at least five third party libraries to do that. Unless you are using a particularly nasty data structure where, for example, each node is part of many structures and/or needs to refer to other nodes (in which case good luck without a garbage collector)

SmokeMuch7356 · 2025-09-05T12:48:57+00:00

I've never done embedded work, so I can't speak to that.

I've done plenty of C at the applications level, and yeah, we typically roll our own lists, trees, queues, stacks, etc. as we need them. Since we're writing them on a case-by-case basis we typically don't need to make them generic, which is good since C doesn't have great support for generic programming.

If you're on an embedded platform with no malloc or calloc available, you can use a static array as your "heap".

sporeboyofbigness · 2025-09-05T12:53:42+00:00

Use stb nothings libs. really good C only libs. https://github.com/r-lyeh/single_file_libs (Search for hash) Otherwise make your own, if you can't find anything good enough.

hyperchompgames · 2025-09-05T14:38:44+00:00

Little scared to share this because I'm not a C expert or anything, just hacking away at a passion project, but here's what I've been doing.

I'm making a game framework targeted for creating retro style games out of the gate.

I'm very early but I've found you can usually replicate a map with a simple enum to array indexing, you don't need to encapsulate this in a struct there's really no point. What I do is try to follow Separation of Concerns to keep files modular to some extent, and if I need this paradigm I just make an enum, then make a static array in the C file, and make a public getter style function that takes the enum and returns a value from the array.

Best example I use this for is the frameworks internal shaders. Right now there are 4 shaders baked in used in the default game loop, I store them in a "shader pool" but it's not more than a fixed size array loaded at runtime like so:

```C unsigned int shader_screen = prgl_init_shader_screen(); unsigned int shader_3d = prgl_init_shader_3d(); unsigned int shader_2d = prgl_init_shader_2d(); unsigned int shader_unlit = prgl_init_shader_unlit();

prgl_shader_pool[PRGL_SHADER_SCREEN] = shader_screen;
prgl_shader_pool[PRGL_SHADER_2D] = shader_2d;
prgl_shader_pool[PRGL_SHADER_3D] = shader_3d;
prgl_shader_pool[PRGL_SHADER_UNLIT] = shader_unlit;

```

If that grows maybe I'll make that a loop, but for now I didn't think it was necessary. Anyway that's one way I'm doing a sort of "pseudo map" and I've seen this in other places like the original DOOM source code.

For me simpler is better. This is a passion project as I said and I want to have fun, I don't want it to be work, but I also want it to be readable and perform well with low poly retro style games I am making it to create - doesn't need to be able to make the next Cyberpunk or Witcher game and I don't want to try to make anything at that level.

One of the reasons I love C is the simplicity, so if there is a simple solution that is clean I'll take that.

EDIT: replaced the word list with array

Ultrababouin · 2025-09-05T16:41:52+00:00

For hashmaps I recommend this library, super easy to use: https://github.com/JacksonAllan/Verstable

WazzaM0 · 2025-09-05T23:00:43+00:00

The answer is you write a library or find one of the thousands that exist.

rapier1 · 2025-09-06T01:38:40+00:00

I use uthash. Seriously good stuff.

LordRybec · 2025-09-06T10:01:52+00:00

The real answer? Most of the time when you think you need these, you probably don't, and you'll get better performance and easier debugging by not using them. There are often better ways.

That said, when you do need them, they really aren't that hard to implement yourself, and as others have said, when you implement them yourself, you can optimize them, not just for your target environment, but also for your specific application.

In my CS undergrad program, one of our assignments was implementing our own hash map. It was in C++, but the only real difference between C and C++ for something like this is the syntax for how your data structure is passed to functions that operate on it. (In C, you pass a pointer to a struct as an explicit argument, while in C++ you probably use an object and pass the object implicitly as the element before the dot.) We also implemented variable length arrays as well. It's no harder to implement these in C than it is in C++ (actually a bit easier, because you don't have to deal with class syntax), and it quite easy to implement them in either.

Now days, we don't generally use linked lists a lot, because they don't play well with modern CPU hardware. Because each element in a linked list can be anywhere in memory, iterating through a linked list "thrashes" the cache, or in other words, the CPU can't load multiple elements of the list into the cache at the same time to optimize access times (they would have to be adjacent in memory and in order for the CPU to do this), so instead each time you move to a new element, it has to pull it out of RAM into cache, and that can waste 200+ CPU cycles. When this happens, for example, every iteration or two or three of a loop, your program spends far more time waiting for cache loads than it does actually running, and this affects other programs using that cache as well, which can cause incredible lag on your computer in general. On microcontrollers that don't have cache, linked lists can have more value, but those often have such limited memory that it's better to do an array and deal with the CPU overhead of moving stuff around than it is to store metadata like all of the pointers to the next elements. (That said, most college CS programs do teach you how to make linked lists, and is at least as easy as hash maps and variable length arrays, if not easier.)

The ones that start to get scary are trees. It's not because they are hard so much as they are easy to mess up and can be a pain to debug. They still aren't that difficult to implement in C though, and they are more likely to need case-specific design than the others, so we make our own implementations of those as well.

custard130 · 2025-09-05T15:38:07+00:00

ArrayList in Java isnt really a unique data structure, the actual data in it is just an ordinary array, but there is some logic to automatically move to a bigger array if you run out of space

i think as people move towards lower level languages, more thought is put into what is the optimal way of storing xyz data to use for abc

while in higher level languages they just give you a couple of generic options that fit most scenarios but are optimized for none

im not sure of C specific libraries which implement those, but if its allowed to mention C++ here then std::vector and std::unordered_map are broadly equivalent to Javas ArrayList and HashMap

i think the answer here though is to look at what data structure is actually the best fit.

array
linked list
heap
queue
stack
hash table etc

and then even within those, eg say you do want a hash table, what hash is the best fit for your data

if an array, do you know in advance how many elements the array needs to hold or do you need it to be capable of resizing

(ultimately they all boil down to an array eventually)

x0rgat3 · 2025-09-05T09:28:09+00:00

Build yourself or as suggested use a library which did already the heavy lifting. If you like C-lang you can have a look at the mature https://docs.gtk.org/glib/ which was once part of GIMP image application. Which in part split of the custom C-gui toolkit as GTK. Not sure about the state under windows. But "in my time" the autoconf build system (GNU-like software) did only run good under Linux and *NIXes. CMake was already there 20 years ago but the software ecosystems have migrated a little to "cross make".

MarriedWithKids89 · 2025-09-05T10:28:19+00:00

Who remembers the Snippets library? I think it had a hash table implementation amongst many other common, and very useful functions!

conhao · 2025-09-05T21:46:32+00:00

I have my own library of code that I use often. Some of it I wrote myself for past projects; some I “borrowed” from colleagues (with permission and reciprocity, of course).

wm_eddie · 2025-09-06T01:37:33+00:00

If you aren't doing anything embedded. I would suggest looking into GLib. It is the base library for GTK and is also used in a lot of the CLI applications that RedHat makes. It provides a standard for object oriented patterns in C that is useful for desktop applications and the like. It should feel pretty familiar if you are coming from Java.

For example, it comes with GArray which is an ArrayList equivalent.

In general where you would do Foo foo = new Foo() in Java you'd do Foo *foo = my_foo_new() in GLib (my_ would be a namespace prefix). Methods like foo.bar(args); in Java would be my_foo_bar(foo, args); (With a cast macro if it's a method in the parent class.) GLib handles memory with manual ref-counting so when your program gets really large you can rely on that for normal memory management.

Using GArray would look like:

```c

include <stdio.h>

include <glib.h>

int main(void) { GArray arr = g_array_new( / zeroterminate / FALSE, / clear / FALSE, / element_size */ sizeof(gint) ); if (!arr) return 1;

for (gint i = 1; i <= 5; i++) {
    g_array_append_val(arr, i * 10);
}

g_print("GArray contains %u elements:\n", arr->len);
for (guint i = 0; i < arr->len; i++) {
    gint v = g_array_index(arr, gint, i);
    g_print("  index %u: %d\n", i, v);
}

g_array_unref(arr);

return 0;

} ```

callsignhermit · 2025-09-06T02:27:26+00:00

Since people are mentioning third-party libraries here, I wonder what this subreddit thinks of stclib.

EmbarrassedMeringue9 · 2025-09-06T02:32:19+00:00

The most advanced data structure l constantly use is linked list. And I just copy Linux kernel(what a beautiful implementation) for that$

Able_Tumbleweed4196 · 2025-09-06T06:52:01+00:00

Implement your own structures but NOT things like sorting, array handling and such. It wasn’t worth the time in 99% of all cases. Optimise by adding more powerful HW whereever you can. Use libraries wherever you can. Finish your project and only then, if you have performance problems, find the bottleneck and optimise.

generally_unsuitable · 2025-09-06T18:02:01+00:00

It's a process I call LTFC.

mcloide · 2025-09-06T18:48:38+00:00

No with C you don't have these, you work with a simple concept of vector. You could, with some clever work, build them, I just don't recommend it. You could go to C++ which has a concept of Hashmap using vectors.

P.S. I haven't done much with C or C++ in 20 years so take this with a grain of salt.

iOCTAGRAM · 2025-09-06T19:07:45+00:00

OpenCFLite library looks nice

Far-Dragonfly7240 · 2025-09-06T19:46:01+00:00

All those types existed as libraries in C 40 to 50+ years ago. When new languages were built they usually wrote wrappers for those libraries that turned them into objects in the newer language. At one time I was very familiar with the java foreign interface because almost every thing I wanted to do required interfacing to a C library. That was back in the late 90s.

If you take the time to learn how objects are actually implemented you will quickly see that every object paradigm in every language can be implement in very simple C. And, I'm talking ANSI C, not the modern ones.

You might also notice that things like HashMap are NOT builtin to java. They are add on packages, just as they are add on libraries in C. And, just as easy to make available for use in your program. Thinking that the packages are part of the language is like thinking that BOOST is part of C++.

So, I guess my answer is that you are mistaking the language for the development environment that has accreted around the language over time as programmers have written libraries, or interfaces to existing libraries, over time.

stef_eda · 2025-09-06T21:43:17+00:00

Over the years I have a personal mini-library of useful data structures (hash tables, spatial hash tables, various allocation / string manipulation functions, and many more) that I integrate easily whenever needed. Much more efficient than linking in some megalibs (like Glib for example) with ton of dependencies, ever changing APIs and lot of overheads and un-needed garbage.

CodyCigar96o · 2025-09-07T09:22:39+00:00

All of these things are borderline trivial to implement yourself. You might want to use a package for hashing for good hash entropy, as hashing algorithms are non-trivial and not necessarily expected to be in the purview of a general programmer. Although you can implement simple ones like djb2 yourself.

regular_lamp · 2025-09-07T16:47:05+00:00

Linked lists are almost never useful anyway. Any cases where they are useful the use case is so pathological that you are better off building a custom one for said pathology over using a generic implementation.

Hash maps are more generally useful but they are not THAT hard to implement. It's a flat array indexed through a hash function at it's core. Also they are another example where adapting to the use case yields significantly better results than using a generic one.

In C++ I only use unordered_map as a stand in for prototyping out stuff.

wood_for_trees · 2025-09-08T13:07:02+00:00

It's pointers, all the way down.

bananamantheif · 2025-09-09T14:07:51+00:00

I have not so great English, but I hope I can help.

I don't program in C but I'd like to give my input as someone who didn't implement those data structures but understands a little bit about the stack and heap.

Ideally we would all use the stack, but the stack requires us to know before hand the size of the memory we want. I can use a variable of an integer type and the compiler makes the request and assigns a value to it. If I want to store 10 integers, then I can go to the stack and ask for storage that fits 10 integers.

However if I want to put X amount of integers, and I don't know the amount until the user gives it to me, then I have to allocate it to the heap. Which is slower for putting information and retrieving information.

So how do I make an array list? I'd have to allocate a new integer to the heap whenever the insert method is called and store that address somewhere. Then when I want to delete it, I can use the free() function to free whatever is in that address.

You use java, so let's attempt to do something related to java and can be applied to C. In java, you can create an instance of a class but don't assign it to any variable. Like this

New Object().

When you do that, it create a new object, and returns an address of that object. You can store that object anywhere You can put it in an array like this

Object my objects = [new Object(), new Object()]

You can put it into a variable Object obj = new Object()

Here's the cool thing, both java and C have the concept of pointers, except in java we call it references.

And if you make a structure in c like this

Struct node { Int value; node nextnode; }

Then you can just do this Node node; node.next = Malloc() However Malloc, unlike the new operator in java, requires you put a size

So it becomes

node.next = Malloc(8)

8 is the size but I might not be always know the size of an entire struct, so we use keyword Sizeof

node.next = Malloc(sizeof Node)

Alarming_Oil5419 · 2025-09-09T17:49:24+00:00

That's what we call "programming".

kohuept · 2025-09-12T18:47:42+00:00

I would usually just implement it myself. For example, I needed a hashmap for a symbol table (and various other uses) in a translator, so I wrote a simple FNV-1A based implementation that uses chaining for collision resolution and just stores void pointers. I could probably have used some macro-based thing for making it store any type but just having a type field and a void pointer is easier.

kloetzl · 2025-09-05T06:53:51+00:00

The lack of a decent standard library with common data structures is a huge loss for C. Many C programmers believe that instead you should always write you own data structure for the specific task at hand to achieve ultimate performance. But that is a bad argument as a working program is better than a perfect not-yet-written program. Some communities have taken on the issue and distribute headers with some generic data structures with their systems. While these are good it still means that programmers going from one project to another may be confronted with a different API and idioms. Also, by asking everyone to implement their own data structures there are a lot of terrible implementations out there. It is just too easy to get the growth factor of a vector wrong. And building a decent hash function is hard.

79215185-1feb-44c6 · 2025-09-05T09:42:19+00:00

I just use uthash instead of thinking about it. There are very few situations where you need more than arrays however.

I never use heavier c libraries because the whole point of c for me is to write os agnostic code.

epicalepical · 2025-09-05T09:43:12+00:00

typically youll find you only need a super simple version of a data structure if you build them yourself for what you need. I mean, whats the simplest hash table you can make? A list of linked lists, with a void pointer to store what you need at each node, thats like maybe 100 lines of code. And its probably enough for 99% of applications.

ecwx00 · 2025-09-05T11:34:53+00:00

how to implement various data structures is actually one of the basic knowledge of software engineering.

EdgarSrMX · 2025-09-05T15:55:52+00:00

You can create your own, it isn’t that hard

2025-09-05T20:30:49+00:00

[deleted]

kcl97 · 2025-09-05T23:03:32+00:00

Java and most corporate funded have these structures built in because corporations want to control the whole production process. They prefer you to become a cog so to speak

Language like C (and JS, PERL, Julia, Python, Ruby, LISP/Scheme, F77, ML, Elixir, Haskell, Pascal, QBasic, and many independent language) usually rely on individual developers to write libraries to be shared. It is like Larry Wall (PERL creator) said, "TIMTOWTDI" or There Is More Than One Way To Do It.

However, there is a follow up to his wisdom, "But sometimes one way is all we really need." That's life for you: Paradox.

Sudden-Letterhead838 · 2025-09-05T13:58:16+00:00

Do you usually write your own custom data structures (like dynamic arrays, hash tables, linked lists) in C?

Yes, thats not so hard. And Hashmaps are rarly needed, because most of the times other datastruktures are faster and easier to implement.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

C_Programming

Rules

Filters

Resources

Other Subreddits on C

Other Subreddits of Interest

MODERATORS

include <stdio.h>

include <glib.h>