A list of elements of type T is a finite sequence of elements of T with the foll
ID: 3907306 • Letter: A
Question
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]);
}
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
Explanation / Answer
template<class T>
class List{
private:
T *data;
int max;
int num;
public:
List(int a){ ---------------------------(1)
data = new T[a];
max = a;
num = 0;
}
bool isEmpty(){ -------------------(2) O(1)
return num == 0
}
bool isFull(){ -------------------(3) O(1)
return num == max
}
int getSize(){ -------------------(4) O(1)
return num == max
}
int empty(){ -------------------(5) O(1)
num = 0;
}
void insert(T a, int n){ -------------------(6) O(n)
if (n <= size){
if (size < max){
if (n == size){
data[n] = a;
size++;
}
else {
for (int i = size; i>=n; i--){
data[i+1] = data[i];
}
data[n] = a;
size++;
}
}
}
}
void remove(T a, int n){ -------------------(7) O(n)
if (n <= size){
for (int i = n+1 ; i<size; i++){
data[i-1] = data[i];
}
size--;
}
}
T retrieve(int n){ -------------------(8) O(1)
if (n <= size){
return data[n]
}
}
T replace(T a, int n){ -------------------(9) O(1)
if (n <= size){
data[n] = a;
}
}
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.