Description
Object Oriented Linked List Implementation
Arrays have their limitations. Their size should be known in advance during compile time.
Inserting a new element in an array is a costly operation because it involves the shifting of
elements. Resizing an array is also a very costly operation because it involves the creation
of a new array and the copying of all the elements to the new structure. These limitations
can be avoided by using a Linked List data structure.
In this assignment you will be designing and implementing a Linked List Class to manage a
doubly linked list.
A linked list data structure is a collection of elements called nodes. Each element can hold
data along with a pointer to the next element. Doubly linked list structures hold two
pointers in each element instead of one. The first pointer points to the next element, and
the second one points to the previous element in the list.
Let’s start by designing and implementing a doubly linked list data structure step by step.
Note that we will need to define two classes. One that defines a node structure and one
that manages the doubly linked list structure and behavior.
Question 1 (5 pts)
Create a class called Node having the following data members and methods:
● Int data member to hold the data in each element
● A pointer to Node to hold the pointer to the next element
● A pointer to Node to hold the pointer to the previous element
● A default constructor Node() that initializes the data members appropriately
● A destructor ~Node() that makes sure all dynamically allocated memory was
appropriately deleted (if any)
● A personalized constructor that will create a node and assign its data and pointers
to the given values passed as arguments Node( int data, Node* next, Node*
previous )
You can make all members public for simplicity. However, if you want to make the data
members private, make sure to provide methods permitting the interaction with the data
like Setters and Getters for example.
Question 2 (15 pts)
Create a class called DLLStructure (for Doubly Linked List Structure) having the following
data members and methods:
● A pointer to the first element of the list
● A pointer to the last element of the list
● A default constructor that initializes an empty list
● A destructor that makes sure all elements in the list are being destroyed (calling
delete operator for each element in the list)
● A personalized constructor that will create a list from an array passed as argument,
meaning that the list will have the same number of elements as the array and each
element will have its data assigned to the value from the corresponding array
element (you may need to pass the array’s size as an argument as well). Make sure
to call the new operator to dynamically create a new Node element for each value
in the array.
Make sure that all of your data is declared private and your methods are declared public.
The class declaration may look something like this:
Question 3 (5 pts)
Implement a method in DLLStructure that will loop over all the elements in the list and
print their values to the screen. The signature of the method will be
void DLLStructure ::PrintDLL()
Question 4 (10 pts)
Implement a method in DLLStructure that will insert a new element in the linked list after
the first occurence of the value provided by the first argument and having the value
provided in the second argument. The signature of the method will be
void DLLStructure ::InsertAfter( int valueToInsertAfter, int valueToBeInserted)
If valueToInsertAfter was not found in the list, add the new value at the end of the list.
Question 5 (5 pts)
Use the method InsertAfter to implement another method InsertBefore that inserts a
new element in the linked list before the first occurence of the value provided by the first
argument and having the value provided in the second argument.
The signature of the
method will be
void DLLStructure ::InsertBefore( int valueToInsertBefore, int valueToBeInserted)
Remember that this method should call InsertAfter in its implementation.
If valueToInsertBefore does not exist in the list, the new value should be added at the
beginning of the list (the first element).
Question 6 (10 pts)
Implement a method in DLLStructure that will delete the first occurence of the value
provided as argument. If the value does not exist, do nothing.
void DLLStructure ::Delete(int value)
Remember that you have to update the previous element’s next pointer, as well as the next
element’s previous pointer to reflect the new list after deleting the appropriate value.
Question 7 (10 pts)
Implement a method in DLLStructure that will sort the elements in ascending order
void DLLStructure ::Sort()
Question 8 (5 pts)
Implement a method in DLLStructure that will return TRUE if the list is empty and FALSE
otherwise
bool DLLStructure ::IsEmpty()
Question 9 (5 pts)
Implement the following getter methods GetHead and GetTail in DLLStructure that will
return the value of the first and last node respectively
int DLLStructure ::GetHead()
int DLLStructure ::GetTail()
Question 10 (5 pts)
Implement GetSize method that will return the number of elements present in the list
int DLLStructure ::GetSize()
What would be the best implementation of GetSize if this method is requested very often?
In other terms, how can we avoid looping over the elements of the list each time the
GetSize method gets called?
Question 11 (10 pts)
Implement GetMax and GetMin methods that will return the maximum and minimum data
values present in the list
int DLLStructure ::GetMax()
int DLLStructure ::GetMin()
What would be the best implementation of GetMax and GetMin if these methods are
requested very often? In other terms, how can we avoid looping over the elements of the
list each time the GetMax or GetMin method gets called? Please provide your answer inside
a cout statement in the main() function to print it out to the screen when the TA runs your
program.
Question 12 (15 pts)
What will happen if we rely on the default copy constructor that is provided by the compiler
to copy the elements of a list into a new one? Please provide your answer inside a cout
statement in the main() function to print it out to the screen when the TA runs your
program.
If the default copy constructor is not reliable (and you should explain why), can you
provide a copy constructor for the class DLLStructure that, given a reference to a
DLLStructure object, would copy all its elements to a newly created DLLStructure.
DLLStructure& DLLStructure::DLLStructure( DLLStructure& dlls)
Use the following main() function to test your code:
int main() {
// Q 1, 2, 3 should obviously be implemented successfully
// in order to run the following code
int array[5] = {11, 2, 7, 22, 4};
DLLStructure dll(array, 5); // note that 5 is the size of the array
dll.printDLL(); // the output should be: 11, 2, 7, 22, 4
// Q 4
dll.InsertAfter(7, 13); // To insert 13 after the first occurence of 7
dll.printDLL(); // the output should be: 11, 2, 7, 13, 22, 4
dll.InsertAfter(25, 7); // To insert 7 after the first occurence of 25
dll.printDLL(); // the output should be: 11, 2, 7, 13, 22, 4, 7
// Q 5
dll.InsertBefore(7, 26); // To insert 26 before the first occurence of 7
dll.printDLL(); // the output should be: 11, 2, 26, 7, 13, 22, 4, 7
dll.InsertBefore(19, 12); // To insert 12 before the first occurence of 19
dll.printDLL(); // the output should be: 12, 11, 2, 26, 7, 13, 22, 4, 7
// Q 6
dll.Delete(22);
dll.printDLL(); // the output should be: 12, 11, 2, 26, 7, 13, 4, 7
// Q 7
dll.Sort();
dll.printDLL(); // the output should be: 2, 4, 7, 7, 11, 12, 13, 26
// Q 8
if dll.IsEmpty():
cout << “The list is empty” << endl;
// Q 9
cout << “Head element is: ” << dll.getHead() << endl;
cout << “Tail element is: ” << dll.getTail() << endl;
// Q 10
cout << “Number of elements in the list is: ” << dll.getSize() <<
endl;
// Q 11
cout << “Max element is: ” << dll.getMax() << endl;
cout << “Min element is: ” << dll.getMin() << endl;
9
// Q 11 theory question
// print to the screen the written answer for the theory question
// Q 12 theory question
// print to the screen the written answer for the theory question
// Q 12
DLLStructure dll2 (dll);
dll2.printDLL(); // the output should be: 2, 4, 7, 7, 11, 12, 13, 26
return 0;
}
