Is it possible to provide an implementation of the List ADT discussed in Lecture
ID: 3907230 • Letter: I
Question
Is it possible to provide an implementation of the List ADT discussed in Lecture 1 using an array or a linked list so that all of its methods have a time complexity of O(1) except traverse? Briefly explain your answer
A list of elements of type T is a finite sequence of elements of T with the following operations:
1.Construct the list, leaving it empty.
2.Determine whether the list is empty or not.
3.Determine whether the list is full or not.
4.Find the size of the list.
5.Clear the list to make it empty.
6.Insert an entry at a specified position of the list.
7.Remove an entry from a specified position in the list.
8.Retrieve the entry from a specified position in the list.
9.Replace the entry at a specified position in the list.
10.Traverse the list, performing a given operation on each entry.
Implementation Issues (Focus on List)
Two ways to implement a list
1. Contiguous implementation
a. Contiguous: Elements are next to each other
b. A list implemented using an array is a contiguous list
c. A list implemented using a vector is also a contiguous list
2. Linked implementation
a. Linked list is a list in which each entry contains a pointer giving the location of the next entry
b. Pointer: An object, often a variable, that stores the location (that is the memory address) of some other object
Also called a link or a reference
Traversal
template <class List_entry>
void List<List_entry> :: traverse(void (*visit)(List_entry &))
/* Post: The action specified by function(*visit) has been performed on every entry of the List , beginning at position 0 and doing each in turn. */
{
for (int i = 0; i < count; i++)
(*visit)(entry[i]);
}
Explanation / Answer
Constructing a list using array will make most of the operation O(1)
template <class T>
class List {
private:
T *data;
int max;
int size;
public:
List( int a){ ----1.O(1)
data = new T[a];
max = a;
size = 0;
}
bool isEmpty(){ --------------2. O(1)
return size == 0;
}
bool isFull(){ -------------- 3. O(1)
return size == max;
}
int getSize(){ ----------------4. O(1)
return size;
}
void clear(){ ----------------5. O(1)
size = 0;
}
void add(T a , int n){ ---------------6 . O(n)
if (size < max){
if (n <= size){
for (i= size; i>=n; i--){
data[i+1] = data[i];
}
data[n] = a;
size++;
}
else {
cout << "Invalid index ");
}
}
else {
cout << "List is full ";
}
}
void remove(T a , int n){ ---------------7 . O(n)
if (size == 0){
if (n <= size){
for (i= n+1; i < size; i++){
data[i-1] = data[i];
}
size--;
}
else {
cout << "Invalid index ");
}
}
else {
cout << "List is empty ";
}
}
T getItem(int a){ ------------------------------8. O(1)
if (a < size)
return data[a];
else
cout << "Invalid data "
}
void replace(T a, int n){ ------------------------9.O(1)
if (size == 0){
if (n <= size){
data[n] = a;
}
else {
cout << "Invalid index ");
}
}
else {
cout << "List is empty ";
}
}
void traverse(){ -----------------------------------10 O(n)
for (int i = 0; i<size; i++)
cout << data[i] << " ";
cout << endl;
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.