Skip to main content
remove premature thanks
Source Link
chicks
  • 2.9k
  • 3
  • 18
  • 30

I want to show you my implementation of the array list in C. Is there something I can improve or fix? Thanks

I want to show you my implementation of the array list in C. Is there something I can improve or fix? Thanks

I want to show you my implementation of the array list in C. Is there something I can improve or fix?

Source Link

Array List C implementation

I want to show you my implementation of the array list in C. Is there something I can improve or fix? Thanks

Header

#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H

#include <stdlib.h>

static const int AL_INITIAL_CAPACITY = 16;

struct array_list {
    int *array;
    size_t capacity;
    size_t count;
};

struct array_list *al_new(void);
int al_destroy(struct array_list **list);

int al_ensure_capacity(struct array_list *list, size_t capacity);

int al_push_back(struct array_list *list, int data);
int al_pop_back(struct array_list *list, int *data);
int al_push_front(struct array_list *list, int data);
int al_pop_front(struct array_list *list, int *data);

int al_is_valid_index(struct array_list *list, int index);
int al_get(struct array_list *list, int index, int *data);
int al_set(struct array_list *list, int index, int data);

int al_insert(struct array_list *list, int index, int data);
int al_delete(struct array_list *list, int index);

int al_find(struct array_list *list, int data);
int al_find_last(struct array_list *list, int data);
int al_contains(struct array_list *list, int data);

int al_is_empty(struct array_list *list);
int al_clear(struct array_list *list);

int al_delete_first(struct array_list *list, int data);
int al_delete_last(struct array_list *list, int data);

int al_print(struct array_list *list);

#endif //ARRAY_LIST_H

Source

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "array_list.h"

struct array_list *al_new(void) {
    struct array_list *list = malloc(sizeof(*list));
    if (list == NULL) {
        return NULL;
    }
    list->array = malloc(sizeof(*(list->array)) * AL_INITIAL_CAPACITY);
    list->capacity = AL_INITIAL_CAPACITY;
    list->count = 0;
    for (int i = 0; i < list->capacity; ++i) {
        list->array[i] = 0;
    }
    return list;
}

int al_destroy(struct array_list **list) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    free((*list)->array);
    (*list)->capacity = 0;
    (*list)->count = 0;
    free(*list);
    *list = NULL;
    return 0;
}

int al_ensure_capacity(struct array_list *list, size_t capacity) {
    if (list == NULL) {
        return -1;
    }
    size_t old_capacity = list->capacity;
    if (old_capacity < capacity) {
        list->capacity = (capacity + capacity / 2);
        list->array = realloc(list->array, sizeof(*(list->array)) * list->capacity);
        if (list->array == NULL) {
            return -1;
        }
        for (size_t i = old_capacity; i < list->capacity; ++i) {
            list->array[i] = 0;
        }
    }
    return 0;
}

int al_push_back(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    list->array[list->count] = data;
    ++(list->count);
    return 0;
}

int al_pop_back(struct array_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    *data = list->array[list->count - 1];
    list->array[list->count - 1] = 0;
    --(list->count);
    return 0;
}

int al_push_front(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    memmove(&(list->array[1]), list->array, list->count * sizeof(*(list->array)));
    list->array[0] = data;
    ++(list->count);
    return 0;
}

int al_pop_front(struct array_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->array[0];
    }
    memmove(list->array, list->array + 1, list->count * sizeof(*(list->array)));
    list->array[list->count] = 0;
    --(list->count);
    return 0;
}

int al_is_valid_index(struct array_list *list, int index) {
    if (list == NULL) {
        return -1;
    }
    return index >= 0 && index < list->count ? 0 : -1;
}

int al_get(struct array_list *list, int index, int *data) {
    if (list == NULL || !al_is_valid_index(list, index)) {
        return -1;
    }
    *data = list->array[index];
    return 0;
}

int al_set(struct array_list *list, int index, int data) {
    if (list == NULL || !al_is_valid_index(list, index)) {
        return -1;
    }
    list->array[index] = data;
    return 0;
}

int al_insert(struct array_list *list, int index, int data) {
    if (list == NULL || al_is_valid_index(list, index) < 0) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    memmove(&(list->array[index + 1]),
            &(list->array[index]),
            (list->count - index) * sizeof(*(list->array)));
    list->array[index] = data;
    ++(list->count);
    return 0;
}

int al_delete(struct array_list *list, int index) {
    if (list == NULL || al_is_valid_index(list, index) < 0) {
        return -1;
    }
    memmove(&(list->array[index]),
            &(list->array[index + 1]),
            sizeof(*(list->array)) * list->count);
    list->array[list->count] = 0;
    --(list->count);
    return 0;
}

int al_find(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        if (list->array[i] == data) {
            return data;
        }
    }
    return -1;
}

int al_find_last(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    for (int i = (int)list->count - 1; i >= 0; --i) {
        if (list->array[i] == data) {
            return data;
        }
    }
    return -1;
}

int al_contains(struct array_list *list, int data) {
    return al_find(list, data) ? 0 : -1;
}

int al_delete_first(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    int index = al_find(list, data);
    if (index >= 0) {
        al_delete(list, index);
    }
    return 0;
}

int al_delete_last(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    int index = al_find_last(list, data);
    if (index >= 0) {
        al_delete(list, index);
    }
    return 0;
}

int al_is_empty(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    return list->count == 0 ? 0 : -1;
}

int al_clear(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        list->array[i] = 0;
    }
    list->count = 0;
    return 0;
}

int al_print(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    if (list->count == 0) {
        printf("list is empty\n");
        return 0;
    }
    for (int i = 0; i < list->count; ++i) {
        printf("array list node %d: %d\n", i, list->array[i]);
    }
    return 0;
}