3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ notice that your insert and delete functions are currently referring to the arrayListglobal, and not an arbitrary List pointer. \$\endgroup\$ – Dave Cousineau Nov 19 '16 at 6:07
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Two questions: 1) Can I fit, linked list implementation code smoothly in this code? 2) Can you give encapsulation example in my code? \$\endgroup\$ – overexchange Nov 19 '16 at 0:40
  • \$\begingroup\$ Yes, it should be easy enough to modify the existing code with the suggestions above. I'll try to write up an example. \$\endgroup\$ – user1118321 Nov 19 '16 at 1:47
  • \$\begingroup\$ Am working on linked list implementation. Please wait for me \$\endgroup\$ – overexchange Nov 19 '16 at 1:59
  • \$\begingroup\$ Let me know when you're ready for my example. \$\endgroup\$ – user1118321 Nov 19 '16 at 3:51
  • 1
    \$\begingroup\$ You say that it follows encapsulation and abstraction "fairly well"? I don't think it demonstrates encapsulation or abstraction hardly at all. But I don't think there's much that can be done about it in C anyway. (I suppose maybe it's as good as can be expected in C.) \$\endgroup\$ – Dave Cousineau Nov 19 '16 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.