Data Structures

Repository for learning Data Structures by the group.

Array list

Complexity of

• push(arr, el) (to the end) O(1) to O(n) (in case of reallocation)
• insertion(arr, index, el) O(n) to O(2n) (in case of reallocation)
• deletion(arr, index) O(n)
• get(arr, index) O(1) [main feature]
• "insert after current" O(n) to O(2n) (in case of reallocation)

Linked list

Complexity of

• push(head, el) O(n) (can be O(1) keeping tail pointer)
• insertion(head, index, el) O(n) (at worst)
• deletion(head, index) O(n) (at worst)
• get(head, index) O(n) (at worst)
• "insert after current" O(1) [main feature]
• is_empty(head) O(1)

Stack using linked list

• stack stack_new()
• void stack_push(stack s, int element) O(1)
• int stack_pop(stack s) O(1)
• int stack_len(stack s) O(n)
• is_empty(head) O(1)

Queue using stack

Complexity of

• stack_queue_new()
• stack_queue_len(struct stack_queue s) O(n)
• stack_queue_push(struct stack_queue queue, int a) O(1)
• stack_queue_pop(struct stack_queue s) O(1) (O(n) worst case)