Near99/data-structures-and-algorithms-in-c

Data structures and algorithms in C - Study Notes

Practical Data structures and Algorithms in C

October-22-2022 Update

Well It's been a while since I started coding data structures in C, had a lot of fun and learned a lot from it. C is just the best for basic data structures I encourage anyone who wants to get better at data structures to coding with C for a while to really feel the beauty of data structures and algorithms in your bones. However, C is such a low level language compared to most of the high level languages which brings us some inconvenience to practice algorithm problems. Some of the algorithm questions listed below are not done in C for example. I would suggest to stop coding in C from what I've done in this repo and switch to C++ if you are really into c style programming, or any other modern languages you like such as Java, Python, JavaScript just to name a few. Best of luck!

Array

✔️ Vector implementation.

• vector_create() - create a new vector.
• vector_destory() - destory a vector.
• vector_extend_capacity() - double the capacity automatically when needed.
• vector_shrink_capacity() - shrink the capacity automatically when needed.
• vector_push() - add element to the end of the vector.
• vector_pop() - remove the last element from the vector and return that element.
• vector_at() - return the element at given index.
• vector_is_empty() - if the vector is empty.
• vector_find() - return the first index of the given element.
• vector_size() - size of the vector.
• vector_capacity() - current capacity.
• vector_insert() - insert new element at given index and shift trailing elements to the right.
• vector_delete() - delete the element at given index and shift trailing elements to the left.
• vector_remove() - remove all matched elements.

Array algorithm practice questions:

• Two Sum
• Validate Subsequence.
• Best Time to Buy and Sell Stock.
• Move Element to End.
• Spiral Traverse.
• Longest Peak.
• First Duplicate Value.

List

✔️ Singly linked list with tail implementation.

• list_create() - create a new linked list.
• list_insert_front() - insert a node at front of the list.
• list_insert_back() - insert a node at end of the list.
• list_insert_by_index() - insert a node at the given index.
• list_search_by_index() - search a node at the given index and return its value.
• list_pop_front() - remove the first node of the list.
• list_pop_back() - remove the last node of the list.
• list_traverse() - traverse the list and print the value.
• list_recursive() - traverse the linked list recursively servers as a helper function to list_traverse() api.
• list_destory() - destory the list and release the memory.
• list_remove() - remove the node by the given value.
• list_empty() - if list is empty.
• list_size() - size of the list.

Linked-list algorithm practice questions:

• Reverse Linked List.
• Remove Kth Node From End.
• Remove Duplicates From Linked List.
• Sum of Linked Lists.
• Merge Linked List.
• Detect Cycle in a Linked List.
• Delete the Middle Node of a Linked List.

Stack

✔️ Stack implementation with linked list.

• stack_create() - create a new stack.
• stack_push() - add an element to the stack.
• stack_pop() - remove an element from the stack.
• stack_is_empty() - if stack is empty.

Stack algorithm practice questions:

• Balanced Brackets.
• Next Greater Element.

Queue

✔️ Queue implementation with linked list.

• queue_create() - create a new queue.
• queue_enqueue() - add an element to the end of the queue.
• queue_dequeue() - remove an element at the front of the queue.
• queue_empty() - if queue is empty.

✔️ Queue implementation with array.

• queue_create() - create a new queue.
• queue_enqueue() - add an element to the end of the queue.
• queue_dequeue() - remove an element at the front of the queue.
• queue_empty() - if queue is empty.
• queue_full() - if queue is full.
• queue_size() - size of the queue.

Queue algorithm practice questions:

• None for now.

Dictionary

✔️ Dictionary implementation with hash map.

• hashmap_create() - create a new hash map.
• hashmap_insert() - insert an element to the dictionary.
• hashmap_search() - search an element by key.
• hashmap_delete() - delete an element by key.
• hashmap_exist() - if exist.
• _hasing() - generate hash index.

Dictionary algorithm practice questions:

• Not applicable as it is usually used with other data structures when solving algorithm problems.

Trees

✔️ Binary Search Tree implementation.

• bst_create() - create a new binary search tree.
• bst_insert() - insert an element to the BST.
• bst_print_ascending() - print BST nodes in ascending order.
• bst_print_descending() - print BST nodes in descending order.
• bst_get_min() - get minimum node in the BST.
• bst_get_max() - get the maximum node in the BST.
• bst_node_count() - count nodes in the BST.
• bst_traverse_inorder() - traverse inorder (left, current, right).
• bst_traverse_preorder() - traverse preorder (current, left, right).
• bst_traverse_postorder()- traverse postorder (left, right, current).
• bst_search() - if value is in the tree.
• bst_get_height() - get the height of the BST.
• bst_valid() - if is a valid BST.

BST algorithm practice questions:

• Validate BST.
• BST Traverse.
• Invert Binary Tree.

Priority Queue && Binary Heap

✔️ Priority Queue implementation with heap.

• p_queue_create() - create a new priority queue.
• p_queue_insert() - insert an element to the queue.
• p_queue_fine_min() - find the minimum element in the queue.
• p_queue_extract_min() - delete the minimum element in the queue.
• p_queue_size() - size of the queue.
• p_queue_is_empty() - if the queue is empty.
• p_queue_is_full() - if the queue is full.
• p_queue_parent() - helper function, get the parent's index.
• p_queue_young_child() - helper function, get the child's index.
• p_queue_bubble_up() - helper funtionc, bubble the smallest element to the top.
• p_queue_bubble_down() - helper funtionc, bubble root down if it's not the smallest to its childs.

Heap practice questions:

• Heap Sort.