Tag: #data-structures

We can model “infinite tape” using two stacks. Then we can navigate the list in both directions. This lets us bubble-sort the list in O(n^2) time. 2020-01-22

Implement a queue using two stacks, with one stack for the back of the queue and one for the front. Reverse the back stack onto the front stack when dequeuing to maintain the queue order. 2020-01-21

The head is the front of the queue, allowing efficient dequeue. The tail is the back of the list. To enqueue efficiently, we keep a reference to the tail. 2020-01-18

A recursive algorithm to determine if a string has all unique characters, with an analysis of its time complexity. 2020-01-04

Bitfields in C allow compact bit packing in structs, avoiding manual bitwise operations for greater safety and clarity, at the cost of some language complexity. 2017-01-04

A union in C allows one variable to hold different data types, where the storage is shared. The size of a union is at least the size of its largest member. Fields in a union have the same byte offset. 2017-01-03

Efficient packing of game player data into 16 bits using bitwise operations on a uint16_t type. 2017-01-02

Redis uses length-prefixed strings with pointers into the middle of the allocation, allowing C-string operations on the string data. 2016-12-28

C allows a single array field of incomplete type (char []) at the end of a struct definition. The size of the struct is determined by the size of the fixed fields, and the dynamic-sized array is allocated separately. 2016-12-27

A task management system using a directed acyclic graph (DAG) to represent task dependencies and priorities, allowing for more nuanced organization than a flat to-do list. 2013-12-19