Objectives:
Implement the Abstract Data Type (ADT) List using dynamically allocated arrays and structures.
Description
A LIST is an ordered collection of items where items may be inserted anywhere in the list.
Implement a LIST using an array as follows:
struct list {
int *items; // pointer to the array
int size; // actual size of the array
int count; // number of items in the array
};
typedef struct list *List; // pointer to the structure
Implement the following functions:
a) List newList(int size);
- will create a new List and return its pointer. Allocate space for the structure, allocate space for the array, then initialize size and count, return the pointer.
b) void isEmpty(List list);
c) void display(List list);
d) int contains(List list, int item);
e) void remove(List list, int i) ;
f) void insertAfter(List list,int item, int i);
g) void addEnd(List list,int item)
- add item at the end of the list – simply store the data at position count, then increment count. If the array is full, allocate an array twice as big as the original.
count = 5 size = 10
0 1 2 3 4 5 6 7 8 9
5
10
15
20
30
addEnd(list,40) will result to
count = 6 size = 10
0 1 2 3 4 5 6 7 8 9
5
10
15
20
30
40
h) void addFront(List list,int item)
- shift all elements to the right so that the item can be placed at position 0, then increment count. Bonus: if the array is full, allocate an array twice as big as the original.
count = 5 size = 10
0 1 2 3 4 5 6 7 8 9
5
10
15
20
30
addFront(list,40) will result to
count = 6 size = 10
0 1 2 3 4 5 6 7 8 9
40
5
10
15
20
30
i) void removeFront(List list)
- shift all elements to the left and decrement count;
count = 6 size = 10
0 1 2 3 4 5 6 7 8 9
40
5
10
15
20
30
removeFront(list) will result to
count = 5 size = 10
0 1 2 3 4 5 6 7 8 9
5
10
15
20
30
j) void remove(List list,int item)
- get the index of the item in the list and then shift all elements to the
count = 6 size = 10
0 1 2 3 4 5 6 7 8 9
40
5
10
15
20
30
remove(list,10) will result to
count = 5 size = 10
0 1 2 3 4 5 6 7 8 9
40
5
15
20
30
Remarks
