List abstraction using array

Question

Following this reference, below is the list abstraction implementation using array,

/* list.h */


/*
   List is an ordered collection(sequence) of homogeneous type elements(unique or duplicate).
   By definition, List is not suppose to have collection of heterogeneous type elements. 
   All elements in a List are related.
   List is mutable
   Each element has a position.
   If an element is deleted, then still the remaining elements sit in new order.

   Array implementation of List

*/

#include<stddef.h>
#include<stdlib.h>
#include<string.h>

#define INITIAL_LIST_SIZE 50

#define NEW_LIST 0
#define DOUBLE_THE_LIST 1
#define HALF_THE_LIST 2

typedef struct List{
  int *array;
  int lastItemPosition;
  int size;
}List;

extern List *arrayList;

void insertItem(int newItem, int location);
List* createList(List *, int);

---

/* arrayImpl.c */
#include"list.h"

List *createList(List *list, int flag){

  List *lptr = (List *)malloc(sizeof(List));

  if(flag == NEW_LIST){
    lptr->array = malloc(INITIAL_LIST_SIZE*sizeof(int));
    lptr->array = memset(lptr->array, -1, INITIAL_LIST_SIZE*sizeof(int));
    lptr->lastItemPosition = -1;
    lptr->size = INITIAL_LIST_SIZE;
  }else if(flag == DOUBLE_THE_LIST){
    lptr->array = malloc(2*(list->size)*sizeof(int));
    lptr->array = memcpy(lptr->array, list->array, list->size*sizeof(int));
    lptr->lastItemPosition = list->lastItemPosition;;
    lptr->size = 2*(list->size);
  }else if(flag == HALF_THE_LIST){
    lptr->array = malloc(((list->size)/2)*sizeof(int));
    lptr->array = memcpy(lptr->array, list->array, (list->size/2)*sizeof(int));
    lptr->lastItemPosition = list->lastItemPosition;;
    lptr->size = (list->size)/2;
  }
  return lptr;

}

void insertItem(int newItem, int index){

  /* House keeping */
  if(arrayList->lastItemPosition + 1 == arrayList->size){
    arrayList = createList(arrayList, DOUBLE_THE_LIST);
  }


  /* Insert the element */
  arrayList->array[index] = newItem;
  if(index > arrayList->lastItemPosition){
     arrayList->lastItemPosition = index;
  }

  return;
}

void deleteItem(int index){

  arrayList->array[index] = -1;
  if(index == arrayList->lastItemPosition){
    arrayList->lastItemPosition--;
  }

  /* House keeping */
  if(arrayList->size > INITIAL_LIST_SIZE){
    if(arrayList->lastItemPosition == ((arrayList->size)/2)){
      arrayList = createList(arrayList, HALF_THE_LIST);
      arrayList = createList(arrayList, HALF_THE_LIST);
    }
  }
}

---

/* main .c */
#include"list.h"

List *arrayList = NULL;

int main(void){
  arrayList = createList((List *)NULL, NEW_LIST);

}

---

Is Listfollowing abstraction and encapsulation?

Note: Encapsulation is about maintaining in-variants of ADT, after performing operations on ADT. Abstraction is a barrier between representation and usage.

Answer 1

This code is very easy to read, and very straightforward in its implementation. Nice work! Overall, it looks really good. I would say that it does follow abstraction and encapsulation fairly well. Below are some things that I think could be improved.

Functions Should Do 1 Thing

Your createList() function does 3 possible things:

1. Creates a new empty list with a set capacity
2. Creates a new list with double the capacity of an existing list, then copies the existing list to it
3. Creates a new list with half the capacity of an existing list, then copies the existing list to it

That's a little confusing. Also the name flag for the second parameter is not very helpful. If I were to keep the function as-is, I'd rename it to operation, or something like that to make it more clear. Usually a flag is a Boolean value of some sort. (It may be an int but is usually on or off.)

So I'd break createList() into 2 or 3 functions like this:

List* createList();
size_t setListSize(List* ptr, const size_t newSize);

Or you could break the second one into 2 functions, like increaseSize() and decreaseSize(), but I don't think that's necessary.

The new createList() function would just do what's inside of the if (flag == NEW_LIST) portion of your original function. For setListSize(), I'd pass in the new desired size. You can check inside the function if it's greater or less than the current size and do the appropriate thing. And the return value should be the size it was set to, which leads to my next point…

Handle Errors

None of your functions handle error cases. What if you attempt to increase the size of the list and you're out of memory? What if you want to reduce the size of the list, but can't allocate the smaller-sized array before doing the copy? With your current createList() function, it will return NULL, but none of the callers check that return value, so they could crash. Even worse, you allocate a List on the first line, then assume it worked and allocate the array. Then you assume that worked and start setting or copying to it. If any one of those steps fails, the next one will probably crash it.

If you return the size from setListSize(), the caller can check to make sure it worked and react appropriately if it didn't.

Modify the Existing List

Since your InsertItem() and DeleteItem() functions modify your list, the setListSize() function should too. Rather than create a new list, it would create the new array (either larger or smaller than the current one), do the copy, then free the existing one and replace it with the new one.