abstract data type list. . .
Posted
by aldrin
on Stack Overflow
See other posts from Stack Overflow
or by aldrin
Published on 2010-04-28T05:17:05Z
Indexed on
2010/04/28
5:23 UTC
Read the original article
Hit count: 480
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
© Stack Overflow or respective owner