Description
Objective
This is an individual assignment which has two parts.
1. Part 1 involves implementing a simple Doubly Linked List and a Doubly Linked List template ADT, and analyzing
the complexity of your implementation.
2. Part 2 involves writing applications of Linked List and writing a report.
Part I: Implementing Doubly Linked List
• Program Instructions
Download the program 221-A3-13c-code.tar from the course website. Use the 7-zip software to extract the
files in Windows, or use the following command in Linux.
tar xfv 221-A3-13c-code.tar
Three programs in separate folders are included.
1. “Simple Doubly Linked List”for integers
(a) Contains a list node sturcture and associated functions. Doubly linked lists of integers can be constructured
using just the structure of list node.
(b) You need to complete the following functions in the SimpleDoublyLinkedList.cpp.
i. insert_before
ii. insert_after
iii. delete_before
iv. delete_after
The above functions insert an integer or remove a node around the current list node.
(c) Type the following commands to compile the program.
make clean
make
(d) The main program includes an example of contructing a doubly linked list, and demonstrates how to use it
and display it. Type the following command to execute.
2
./SimpleDoublyLinkedList
2. “Doubly Linked List”for integers
(a) Most code is extracted from the lecture slides. An exception structure is defined to complete the program.
(b) You need to complete the following functions in the DoublyLinkedList.cpp.
i. copy constructor
ii. assignment operator
iii. output operator
Make sure the i. and ii. functions do a deep copy of the input list, that is, copying each node one by one.
(c) Type the following commands to compile the program.
make clean
make
(d) The main program includes examples of creating doubly linked lists, and demonstrates how to use them.
Type the following command to execute.
./Main
3. Template “Doubly Linked List”for general type
(a) Convert the doubly linked list in program 2 to a template, so it creates lists of general types other than
integer.
(b) Read C++ slides, page 16-22 at http://www.stroustrup.com/Programming/19_vector.ppt
(c) Follow the instructions below:
i. Templates should be defined in a .h file. Move the content of DoublyLinkedList.cpp and
DoublyLinkedList.h to TemplateDoublyLinkedList.h
ii. Add template
