Interview Cake

C Data Structure Interfaces

Documentation to help you use our implementations of core data structures in C

Often, the most efficient answers to interview questions center on picking the right data structure. In particular, linked lists, hash tables, stacks, queues, and sets tend to show up pretty frequently.

Many languages come with these data structures built in. C does not.

If you're writing C in a coding interview and you need a data structure that's not built in, ask your interviewer how they'd like to proceed. Most interviewers will tell you to assume the data structure is already implemented. They might tell you the interface for using it, or they'll ask you to come up with it on the fly. This lets you focus on solving their question, instead of figuring out how you'd build a hash table.

That's the approach we take at Interview Cake. We'll give you minimal implementations of core data structures, which you should use however you'd like. The documentation below lays out exactly what we provide in our libraries and how to use them.

Questions? Comments? Think you've found a bug?

Please let us know how we can make this more useful for you.

Linked Lists

  • Create

    /* * Allocate and initialize a new LinkedList structure. * * Returns: A pointer to the allocated structure. */ LinkedList * linkedListNew(void);

  • Delete

    /* * Frees all elements in a previously allocated linked list. * * Parameters: * - The list to free. */ void linkedListFree(LinkedList *list);
    /* * Helper for freeing a linked list where data must be freed * in a particular way. * * Parameters: * - The list to free. * - A function to call prior to freeing the node. The function * takes the node's data as input and does any custom cleanup * required. */ void linkedListFreeWithDestructor(LinkedList *list, void (*freeData)(void *));

  • Size

    /* * Retrieve the number of elements in a linked list. * * Parameters: * - The list to retrieve the element count from * * Returns: The number of elements in the input list. */ size_t linkedListSize(const LinkedList *list);
    /* * Check if a linked list contains any elements. * * Parameters: * - The list to check * * Returns: Non-zero if the list is empty; zero otherwise. */ int linkedListIsEmpty(const LinkedList *list);

Linked List Nodes

Each linked list is made up of zero or more linked list nodes:

typedef struct LinkedListNode { void *data; /* This node's data */ struct LinkedListNode *next; /* Pointer to the next node */ } LinkedListNode;

  • Create

    /* * Create and initialize a new linked list node. The * resulting node should be freed by calling freeLinkedListNode. * * Parameters: * - The data the node should encapsulate. * - Size of the node's data, in bytes. * * Returns: The allocated and initialized linked list node. */ LinkedListNode * newLinkedListNode(const void *data, size_t dataSize);
    /* * Create and initialize a new linked list node holding an integer. The * resulting node should be freed by calling freeLinkedListNode. * * Parameters: * - The integer the node should store. * * Returns: The allocated and initialized linked list node. */ LinkedListNode * newLinkedListNodeWithIntData(int intValue);
    /* * Create and initialize a new linked list node holding a pointer. The * resulting node should be freed by calling freeLinkedListNode. * * Parameters: * - The pointer the node should store. * * Returns: The allocated and initialized linked list node. */ LinkedListNode * newLinkedListNodeWithPointerData(const void* value);

  • Delete

    /* * Free a single linked list node. * * Parameters: * - The node to free. */ void freeLinkedListNode(LinkedListNode *node);

A number of helper functions make it easy to create new nodes and append them to the end of the list.

  • Generic Node

    /* * Create a new node and insert it at the end of the linked list. * * Parameters: * - The list to append to * - The data the new node should encapsulate * - The side of the new node's data, in bytes * * Returns: The allocated and initialized linked list node. */ LinkedListNode * linkedListAppend(LinkedList *list, const void *data, size_t size);

  • String Node

    /* * Helper function for creating a new node holding a string * and inserting it at the end of the linked list. * * Parameters: * - The list to append to * - The string the new node should encapsulate * * Returns: The allocated and initialized linked list node. */ LinkedListNode * linkedListAppendString(LinkedList *list, const char* string);

  • Integer Node

    /* * Helper function for creating a new node holding an integer * and inserting it at the end of the linked list. * * Parameters: * - The list to append to * - The integer the new node should encapsulate * * Returns: The allocated and initialized linked list node. */ LinkedListNode * linkedListAppendInt(LinkedList *list, int n);

  • Pointer Node

    /* * Helper function for creating a new node holding a pointer * value and inserting it at the end of the linked list. * * Parameters: * - The list to append to * - The pointer the new node should encapsulate * * Returns: The allocated and initialized linked list node. */ LinkedListNode * linkedListAppendPointer(LinkedList *list, const void *ptr);

Stacks

  • Create

    /* * Create a new stack. * * Returns: The allocated and initialized stack. */ Stack * stackNew(void);

  • Delete

    /* * Free all elements in a stack, along with the stack itself. * * Parameters: * - The stack to free */ void stackFree(Stack *stack);

  • Check Empty

    /* * Check if a stack contains any elements. * * Parameters: * - The stack to check * * Returns: Non-zero if the stack is empty; zero otherwise. */ int stackIsEmpty(const Stack *stack);

  • Push

    /* * Push a new item onto the top of the stack. * * Parameters: * - The stack to push the item onto * - The value the new item should hold * - Size of the value, in bytes */ void stackPush(Stack *stack, const void *value, size_t valueSize);
    /* * Push a string onto the top of the stack. * * Parameters: * - The stack to push the item onto * - The string that should be stored in the new item */ void stackPushString(Stack *stack, const char *str);

  • Peek

    /* * Access the top item on the stack. * * Parameters: * - The stack to access * * Returns: A pointer to the item at the top of the input stack. */ void * stackPeek(const Stack *stack);

  • Pop

    /* * Remove the item at the top of the stack. * * Note: Pointers from previous calls to stackPeek * should not be used after calling stackPop. * * Parameters: * - The stack to remove an item from */ void stackPop(Stack *stack);

Queues

  • Create

    /* * Create a new queue. * * Returns: The allocated and initialized queue. */ Queue * queueNew(void);

  • Delete

    /* * Free all elements in a queue, along with the queue itself. * * Parameters: * - The queue to free */ void queueFree(Queue *queue);

  • Check Empty

    /* * Check if a queue contains any elements. * * Parameters: * - The queue to check * * Returns: Non-zero if the queue is empty; zero otherwise. */ int queueIsEmpty(const Queue *queue);

  • Size

    /* * Retrieve the number of elements in a queue. * * Parameters: * - The queue to retrieve the element count from * * Returns: The number of elements in the input queue. */ size_t queueSize(const Queue *queue);

  • Enqueue

    /* * Insert a new item at the back of the queue. * * Parameters: * - The queue to add the item to * - The value the new item should hold * - Size of the value, in bytes */ void queueEnqueue(Queue *queue, const void *data, size_t dataSize);
    /* * Insert a new item at the back of the queue. This helper * is somewhat simpler if the item to be inserted is a pointer. * * Parameters: * - The queue to add the item to * - The pointer value the new item should hold */ void queueEnqueuePointer(Queue *queue, const void *data);

  • Dequeue

    /* * Remove the item at the front of the queue. * * Parameters: * - The queue to dequeue the item from * * Returns: The value at the front of the queue. */ void * queueDequeue(Queue *queue);
    /* * Remove the item at the front of the queue and dereference it, * returning the result. * * Parameters: * - The queue to dequeue the item from * * Returns: The result of dereferencing the value at the front * of the queue. */ void * queueDequeuePointer(Queue *queue);

Sets

  • Create

    /* * Create and initialize a new set. * * Returns: The new set. */ void stackPop(Stack *stack);

  • Clear

    /* * Delete all items in the set, but not the set itself. * * Parameters: * - The set to clear */ void setClear(Set *set);

  • Delete

    /* * Delete all items in the set and the set itself. * * Parameters: * - The set to delete */ void setFree(Set *set);

  • Size

    /* * Check if a set is empty or not. * * Parameters: * - The set to check * * Returns: Non-zero if the set is empty; zero otherwise. */ int setIsEmpty(const Set *set);
    /* * Retrieve the number of items in the set. * * Parameters: * - The set whose size we need * * Returns: The number of elements in the set. */ size_t setSize(const Set *set);

  • Contains

    /* * Check if an item is present in the set. * * Parameters: * - The set to check * - The item to check for * - Size of the item, in bytes * * Returns: Non-zero if the item is present in the set; zero otherwise. */ int setContains(const Set *set, const void *item, size_t size);
    /* * Check if a character is present in the set. * * Parameters: * - The set to check * - The character to check for * * Returns: Non-zero if the character is present in the set; zero otherwise. */ int setContainsChar(const Set *set, char c);
    /* * Check if a pointer is present in the set. * * Parameters: * - The set to check * - The pointer to check for * * Returns: Non-zero if the pointer is present in the set; zero otherwise. */ int setContainsPointer(const Set *set, const void *ptr);
    /* * Check if a string is present in the set. * * Parameters: * - The set to check * - The string to check for * * Returns: Non-zero if the string is present in the set; zero otherwise. */ int setContainsString(const Set *set, const char *str);

  • Insert

    /* * Insert an item into the set. * * Parameters: * - The set to modify * - The item to insert * - Size of the item, in bytes */ void setInsert(Set *set, const void *item, size_t size);
    /* * Insert a character into the set. * * Parameters: * - The set to modify * - The character to insert */ void setInsertChar(Set *set, char c);
    /* * Insert a pointer into the set. * * Parameters: * - The set to modify * - The pointer to insert */ void setInsertPointer(Set *set, const void *ptr);
    /* * Insert a string into the set. * * Parameters: * - The set to modify * - The string to insert */ void setInsertString(Set *set, const char* str);

  • Erase

    /* * Remove an item from the set. * * Parameters: * - The set to modify * - The item to remove * - Size of the item, in bytes */ void setErase(Set *set, const void *item, size_t size);
    /* * Remove a character from the set. * * Parameters: * - The set to modify * - The character to remove */ void setEraseChar(Set *set, char c);
    /* * Remove a pointer from the set. * * Parameters: * - The set to modify * - The pointer to remove */ void setErasePointer(Set *set, const void *p);
    /* * Remove a string from the set. * * Parameters: * - The set to modify * - The string to remove */ void setEraseString(Set *set, const char* str);

Set Iterators

Set iterators can be used to access items in the set.

  • Start

    /* * Returns an iterator for accessing elements within the * set. * * Note: The iterator is not guaranteed to remain consistent * after a insert or erase operation. * * Parameters: * - The set to we will be iterating through * * Returns: A set iterator reference for use in other SetIterator calls. */ SetIterator setIterationStart(const Set *set);

  • Next

    /* * Move a set iterator to another element in the set. * * Note: Prior to retrieving values from the iterator, check * that it has not exhausted all elements with setIterationIsEnd * * Parameters: * - The set iterator to advance * * Returns: A set iterator referencing the next element in the set. */ SetIterator setIterationNext(const SetIterator it);

  • End

    /* * Check if a set iterator has exhausted all elements in the set. * * Parameters: * - The set iterator to check * * Returns: Non-zero if the iterator has exhausted all items; zero otherwise. */ int setIterationIsEnd(const SetIterator it);

  • Access Char Value

    /* * Access the value in the current set element as a character. * * Parameters: * - The set iterator whose item should be accessed * * Returns: The value stored in the item referenced by the current set iterator. */ char setIteratorGetCharValue(const SetIterator it);

  • Access Pointer Value

    /* * Access the value in the current set element as a pointer. * * Parameters: * - The set iterator whose item should be accessed * * Returns: The value stored in the item referenced by the current set iterator. */ void * setIteratorGetPointerValue(const SetIterator it);

  • Access String Value

    /* * Access the value in the current set element as a string. * * Parameters: * - The set iterator whose item should be accessed * * Returns: The value stored in the item referenced by the current set iterator. */ char * setIteratorGetStringValue(const SetIterator it);

Hash Tables

  • Create

    /* * Allocate and initialize a new hash table. * * Returns: A pointer to the new hash table. */ HashTable * hashTableNew(void);

  • Delete

    /* * Free all elements in a hash table and the hash table itself. * * Parameters: * - The hash table to free */ void hashTableFree(HashTable *hashTable);
    /* * Free all elements in a hash table, calling the provided destructor * function on all values. Then, free the hash table itself. * * Parameters: * - The hash table to free * - A function to call on the hash table's values to free them */ void hashTableFreeWithDestructor(HashTable *hashTable, void (*freeValue)(void *));

  • Size

    /* * Retrieve the number of items in a hash table. * * Parameters: * - The hash table to access * * Returns: The number of key / value pairs in the hash table. */ size_t hashTableSize(const HashTable *hashTable);
    /* * Check if a hash table is empty or not. * * Parameters: * - The hash table to check * * Returns: Non-zero if the hash table has no elements; zero otherwise. */ int hashTableIsEmpty(const HashTable *hashTable);

  • Contains

    /* * Check if a key is present in the hash table. * * Parameters: * - The hash table to access * - The key to search for * * Returns: Non-zero if the hash table contains the provided key, zero otherwise. */ int hashTableContainsKey(const HashTable *hashTable, const char *key);

  • Insert

    /* * Insert a new key / value pair into the hash table. * * Parameters: * - The hash table to modify * - The key for the new key / value pair * - The value for the new key / value pair * - Size of the value, in bytes * * Returns: Non-zero if the key / value pair was inserted, zero if * the key was already present in the hash table. */ int hashTableInsert(HashTable *hashTable, const char *key, const void *value, size_t valueSize);
    /* * Insert a new key / value pair into the hash table. * This helper is simpler to call if the value is an integer. * * Parameters: * - The hash table to modify * - The key for the new key / value pair * - The integer value for the new key / value pair * * Returns: Non-zero if the key / value pair was inserted, zero if * the key was already present in the hash table. */ int hashTableInsertInt(HashTable *hashTable, const char *key, int value);
    /* * Insert a new key / value pair into the hash table. * This helper is simpler to call if the value is a pointer. * * Parameters: * - The hash table to modify * - The key for the new key / value pair * - The pointer value for the new key / value pair * * Returns: Non-zero if the key / value pair was inserted, zero if * the key was already present in the hash table. */ int hashTableInsertPointer(HashTable *hashTable, const char *key, const void *value);
    /* * Insert a new key / value pair into the hash table. * This helper is simpler to call if the value is a size_t. * * Parameters: * - The hash table to modify * - The key for the new key / value pair * - The size_t value for the new key / value pair * * Returns: Non-zero if the key / value pair was inserted, zero if * the key was already present in the hash table. */ int hashTableInsertSize(HashTable *hashTable, const char *key, size_t value);

  • Erase

    /* * Remove a new key / value pair from the hash table. * * Parameters: * - The hash table to modify * - The key for the key / value pair to remove * * Returns: Non-zero if the key / value pair was removed, zero if * the key was not present in the hash table. */ int hashTableErase(HashTable *hashTable, const char *key);
    /* * Remove a new key / value pair from the hash table, calling * the provided destructor on the value. * * Parameters: * - The hash table to modify * - The key for the key / value pair to remove * - A function to call with the value in order to free it * * Returns: Non-zero if the key / value pair was removed, zero if * the key was not present in the hash table. */ int hashTableEraseWithDestructor(HashTable *hashTable, const char *key, void (*freeValue)(void*));

  • Find

    /* * Retrieve the value associated with a key in the hash table. * * Parameters: * - The hash table to query * - The key to search for * * Returns: A pointer to a copy of the value provided when the key * was first inserted, or NULL if the key is not in the * hash table. */ void * hashTableFind(const HashTable *hashTable, const char *key);
    /* * Retrieve the pointer value associated with a key in the hash table. * * Parameters: * - The hash table to query * - The key to search for * * Returns: A dereferenced pointer to a copy of the value provided * when the key was first inserted, or NULL if the key is * not in the hash table. */ void * hashTableFindPointer(const HashTable *hashTable, const char *key);

Hash Table Iterators

Hash table iterators can be used to access key / value pairs in the hash table.

  • Start

    /* * Returns an iterator for accessing elements within the * hash table. * * Note: The iterator is not guaranteed to remain consistent * after an insert or erase operation. * * Parameters: * - The hash table to we will be iterating through * * Returns: A hash table iterator reference for use in other HashTableIterator calls. */ HashTableIterator hashTableIterationStart(const HashTable *hashTable);

  • Next

    /* * Move a hash table iterator to another element in the hash table. * * Note: Prior to retrieving values from the iterator, check * that it has not exhausted all elements with hashTableIterationIsEnd * * Parameters: * - The hash table iterator to advance * * Returns: A hash table iterator referencing the next element in the hash table. */ HashTableIterator hashTableIterationNext(const HashTableIterator it);

  • End

    /* * Check if a hash table iterator has exhausted all elements in the hash table. * * Parameters: * - The hash table iterator to check * * Returns: Non-zero if the iterator has exhausted all items; zero otherwise. */ int hashTableIterationIsEnd(const HashTableIterator it);

  • Access Key

    /* * Access the key in the current hash table iterator element. * * Parameters: * - The hash table iterator whose key should be accessed * * Returns: The key associated with the item referenced by the provided * hash table iterator. */ const char * hashTableIteratorKey(const HashTableIterator it);

  • Access Value

    /* * Access the value in the current hash table iterator element. * * Parameters: * - The hash table iterator whose value should be accessed * * Returns: The value associated with the item referenced by the provided * hash table iterator. */ void * hashTableIteratorValue(const HashTableIterator it);
. . .