c-programming

commit 2bb437333b8f37d898cf46bc5adedcd11c891d1c
parent 28ae2a9b293ccad59fe54ad72a16865564df70e6
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 13 Oct 2025 17:22:36 -0500

Implemented basic dynamic array (push,pop)

Diffstat:
A
dsa/dynamic-array.c
 | 
109
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 109 insertions(+), 0 deletions(-)
diff --git a/dsa/dynamic-array.c b/dsa/dynamic-array.c
@@ -0,0 +1,109 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct{
+    int* data;
+    int size;
+    int capacity;
+}DynamicArray;
+
+DynamicArray* makeArr(int* data, int size){
+    int capacity = size * 2;
+    DynamicArray* result = malloc(sizeof(DynamicArray));
+
+    int* localData = malloc(capacity * sizeof(int));
+    for(int i = 0; i < size; ++i){
+        localData[i] = data[i];
+    }
+
+    result->data = localData;
+    result->size = size;
+    result->capacity = capacity;
+    return result;
+}
+
+
+void extendArr(DynamicArray* arr){
+    int resultingCap = arr->capacity * 2;
+    if(resultingCap == 0){
+        resultingCap = 1;
+    }
+    int* newArr = malloc(resultingCap * sizeof(int));
+    for(int i = 0; i < arr->size; ++i){
+        newArr[i] = arr->data[i];
+    }
+    free(arr->data);
+    arr->data = newArr;
+    arr->capacity = resultingCap;
+}
+
+void printArr(DynamicArray* arr){
+    for(int i = 0 ; i < arr->size; ++i){
+        printf("%3d: %4d\n", i, arr->data[i]);
+    }
+}
+
+void arrAppend(DynamicArray* arr, int element){
+    if(arr->capacity > arr->size){
+        arr->data[arr->size] = element;
+        arr->size += 1;
+    }
+    else{
+        extendArr(arr);
+        arrAppend(arr, element);
+    }
+}
+
+void arrCompress(DynamicArray* arr){
+    int resultingCap = arr->size;
+    int* newData = malloc(sizeof(int) * resultingCap);
+    for(int i = 0; i < arr->size; ++i){
+        newData[i] = arr->data[i];
+    }
+    free(arr->data);
+    arr->data = newData;
+    arr->capacity = resultingCap;
+}
+
+
+void arrPop(DynamicArray* arr){
+
+    if(arr->size == 0){
+        return;
+    }
+    // if it is at least half full, no need to resize
+    if(arr->size > arr->capacity/2){
+        arr->size -= 1;
+    }
+    else{
+        arrCompress(arr);
+        arrPop(arr);
+    }
+}
+
+int main(){
+
+    for(int i = 0; i < 10; ++i){
+
+
+        int size = 0;
+        int data [size];
+
+        DynamicArray* arr = makeArr(data, size);
+
+        for(int i = 0 ; i < 1000000; ++i){
+            arrAppend(arr,i);
+        }
+        char* before = "Size after appending:";
+        printf("%30s %10d\n", before, arr->size);
+        //printArr(arr);
+        for(int i = 0 ; i < 1000000; ++i){
+            arrPop(arr);
+        }
+        char* after = "Size after popping:";
+        printf("%30s %10d\n", after, arr->size);
+        //printArr(arr);
+        free(arr->data);
+        free(arr);
+    }
+}