vincentnguyenduc / c-dsa

A data structures and algorithms library in C

C-DS

A Data Structures and Algorithms Library in C

Data Structures

1. Stack
   • Array Stack
   • Linked Stack
2. Queue
   • Priority Queue
   • Array Queue
   • Linked Queue
   • Circular Queue
3. Set
   • Array Set
   • Bit-vector Set
4. List
   • Array List
   • Sorted List
   • Linked List
5. Hash Table
   • Open Addressing
   • Separate Chaining
6. Tree
   • Binary Tree
   • Binary Search Tree
7. Heap

Algorithms

1. Sorting Algorithms:
   • Bubble Sort
   • Selection Sort
   • Insertion Sort
   • Merge Sort
   • Quick Sort
   • Tree Sort
   • Heap Sort

c-dsa's Issues

What up bro

I skimmed through your code, and I have some stuff to say.

I found you from my friend telling me how he's going to a hackathon and one of his teammates is Khiem Le and you follow Khiem Le.

ArrayList

In this snippet of code, I highly suggest not storing the comparison procedure as a field of the structure. Most procedures don't require the comparison procedure, so you're just wasting 8 bytes. It's much better to create a typedef of a comparison procedure and use that as the type for a parameter for procedures that actually require comparing within the data structure. For example, the following code:

typedef int (*Comparator)(const void *, const void *);

int list_find_index(const ArrayList *list, const void *item, Comparator comparator);

You actually use this idiom in all your implementations, so I'll omit this everywhere else.

LinearProbeTable

In this, due to data alignment, you're actually wasting 32 bytes here. In addition to the last critique about wasting bytes by storing the procedures in the data structure itself, due to data alignment, (assuming you're on x86-64) there's 4 bytes hidden after the table_size field, and another 4 bytes after the size_index field. This is because both of the fields are 4 bytes wide followed by an 8-byte wide field. I'm not going to get too far into this; it's best to look into this here.

Another thing is cache efficiency. This is another complex topic, but essentially, if you're often going to be working with all the keys or a group of keys, or all the values or a group of values, it's best to have one side of an array of just keys and the other side of just values:

The above graphic is terribly unproportional, and the intersecting line should be at the middle of the rectangle. If you want to dig deeper into cache efficiency, look here.

Conclusion

It's actually 5:31 AM as of writing this, so if you want me to critique you more, or if you want me to help you in general, you can message @kingemhyr (me) on Discord.