Assignment 1 Linked Lists, Stacks, Queues

Data Structures
Assignment 1
Linked Lists, Stacks, Queues

In this assignment, you are required to implement a linked list, stack, queue, and a simple version
control system.
You may test your implemented data structures using the test cases provided to you. Please note
that your code must compile at the mars server under the Linux environment.
Your Linux accounts have been created on the Mars server. The server is accessible from outside
LUMS, therefore, you can log into Mars from home too.
Here is how you can access the Mars server:
Mars hostname: 203.135.62.10
Mars port number: 46002
Username: your-roll-number (e.g., 19100132)
Password: your-roll-number
You can log into Mars using ssh (ssh -p 46002 mars.lums.edu.pk) or telnet.
Start early as the assignment would take time.

PART 1:
DOUBLY LINKED LIST
In this assignment, you will be applying what you learnt in class to implement different
functionalities of a linked list efficiently. The basic layout of a linked list is given to you in the
LinkedList.h file.
The template ListItem in LinkedList.h represents a node in a linked list. The class LinkedList
implements the linked list which contains pointers to head and tail and other function declarations.
You are also given a file, test1.cpp for checking your solution. However, you are only allowed to
make changes in LinkedList.cpp file.
NOTE: When implementing functions pay special attention to corner cases such as deleting from
an empty list.
Member functions:
Write implementation for the following methods as described here.
 LinkedList():
o Simple default constructor.
 LinkedList(const LinkedList<T& otherList):
o Simple copy constructor, given pointer to otherList this constructor copies all
elements from otherList to new list.
 ~LinkedList():
o Never forget to deallocate the memory!
 void InsertAtHead(T item):
o Inserts item at start of the linked list.
 void InsertAtTail(T item):
o Inserts item at the end of the linked list.
 void InsertAfter(T toInsert, T afterWhat):
o Traverse the list to find afterWhat and insert the toInsert after it.
 ListItem<T *getHead():
o Returns pointer to the head of list.
 ListItem<T *getTail():
o Returns pointer to tail.
 ListItem<T *searchFor (T item):
o Returns pointer to item if it is in list, returns null otherwise.
 void deleteElement(T item):
o Find the element item and delete it from the list.
 void deleteHead():
o Delete head of the list.
 Void deleteTail():
o Delete tail of the list.
 int length():
o Returns number of nodes in the list.
PART 2:
STACKS AND QUEUES
In this part, you will use your implementation of a linked list to write code for different methods of
stacks and queues. As Part 1 is a pre-requisite for this part so you must have attempted Part 1 before
you attempt this part.
STACK:
Stack class contains LinkedList type object. You are allowed to access all members of LinkedList
for your implementation of stack (and queue).
Member functions:
Write implementation for following methods as described here.
 Stack():
o Simple base constructor.
 Stack(const Stack<T& otherStack):
o Copies all elements from otherStack to the new stack.
 ~Stack:
o Deallocate any memory your data structure is holding.
 void push(T item):
o Pushes item at top of the stack.
 T top():
o Returns top of stack without deleting it.
 T pop():
o Return and delete top of the stack.
 int length():
o Returns count of number of elements in the stack.
 bool isEmpty():
o Return true if there is no element in stack, false otherwise.
QUEUE:
Member functions:
Write implementation for following methods as described here.
 Queue():
o Simple base constructor.
 Queue(const Queue<T& otherQueue):
o Copy all elements of otherQueue into the new queue.
 ~Queue():
o Deallocate any memory your data structure is holding.
 void enqueue(T item):
o Add item to the end of queue.
 T front():
o Returns element at the front of queue without deleting it.
 T dequeue():
o Returns and deletes element at front of queue.
 int length():
o Returns count of number of elements in the queue.
 bool isEmpty():
o Return true if there is no element in queue, false otherwise.
PART 3:
VERSION CONTROL SYSTEM
Version Control Systems (VCSs), such as Git and Apache Subversion, are tools that help in the
management of project files by keeping track of changes made to the source code over time. You
have been coding for quite a while now and you will understand how irritating it becomes when
you make changes to your stable code to add some new modification but end up destroying
functionality of the stable methods as well. A VCS keeps track of these changes and allows you to
turn the clock around and return to a version of your choice. While VCSs like Git are designed to
manage huge repositories of files, however, for simplification we will design a VCS which only
keeps track of changes in a single file. In this part, we will use our implementation of a list, stack
and queue to design a simple VCS that keeps record of changes you make in a file.
In the VCS.h file provided to you, VCS_node is the individual node in your version control system.
Message string is for any message you want to associate with the change such as ‘Changed Dijkstra
algorithm with Bellman-Ford algorithm’, whereas the time_stamp contains the information of when
certain change was committed, in your case treat time_stamp as version of your file i.e., start with
0 and increase it discretely with every commit (0,1,2…).
We are leaving it up to you to decide between stack or queue as containers for your VCS. You have
studied in class, characteristics of both containers and the advantages and disadvantages they
have over each other. Use this knowledge to make your choice. You need to come up with at least
one argument in favor of whichever data structure you choose.
NOTE: You need to specify what version the user is currently on. To specify the current version of
the file, you can either use top/front of whichever data structure you are using or create a separate
variable.
Member functions:
Write implementation for following methods as described here.
 VCS(string fname):
o Simple base constructor, fname contains the name of original file you will be
keeping track of.
 ~VCS():
o Deallocate memory.
 void commit(string message):
o This function is the core of VCS. When commit is called, you will read contents of
original file and store them in the container (stack/queue). Also, make a separate
version of this file and write contents of the commit to this version. For example,
for a file with file named “random”, whenever commit is called you will make a
newer version of this file with file name convention of filename+time_stamp+.txt
and write contents of original file at that point to this newer version [e.g.
random0.txt, random1.txt, random2.txt …].
 void status():
o Prints the information (Associated message and version number) about all nodes
on the VCS. For checking purposes, you may print information of last 5 commits
only.
 string undo():
o Undo method takes user to one version back without losing information of the
current version. For example, if you had 3 versions v1, v2 and v3 in order and you
were on v3 currently, the undo method will return you to v2 but it will not lose v3.
Retrieve the version number from node, read the file content associated to that
version number, write them to original file and return contents of that file in a
string.
 string redo():
o Redo method takes user one step forward. Building on the example from
previous paragraph, if you were on v2, calling redo will return v3 back without
losing information of v2. Rest of the implementation will be like undo method.
 string revert(int t_stamp):
o Revert method finds the version with time_stamp having value t_stamp and
returns data stored in that version to user. While doing so it does not alter order in
which nodes were already placed in VCS. For Example: if you had 5 versions v0, v1,
v2, v3 and v4 and you were currently on v4, calling revert(2) will return you content
of v2 and if you call undo from here you will be returned contents of v1. Similar to
undo and redo, you will have to update original file according to version number as
well.
Note: You need to figure out how you will be implementing the above functionalities. You are only
allowed to use just two containers declared in the VCS.h file. Take this as a hint.
Happy Coding �
SUBMISSION CONVENTION:
ZIP all the files and name the file as PA1_rollnumber.zip.