Comp 388 lab 3 - linked lists
Goals
- dynamic allocation
- first look at linked lists
Overview
Consider my simple linked list demo, available at linkedlist.cs.
You are to add the following methods to the class:
- int size(): returns the length of the list. You can either count the
elements of the list one-by-one, or else add a count_ field to the
LinkedList class and keep it appropriately updated.
- T Get(int n): retrieves contents of nth cell, with the numbering
starting at 0. It should return null
if n is "out of range". I provided a simple version that fails
completely if n is out of range (ie n > size(). Your best bet is to
notice in the loop if p==null, and simply return null in that case.
- void Set(int n, T val): update the value of the nth cell, if
0<=n<size(); do nothing otherwise.
- void insertAfter(int n, T val): inserts a new cell with value val
following cell n, again counting from 0. The cell formerly at position
n+1 is now at position n+2. This entails modifying the next
field of cell n.
- LinkedList reverse(): Note that this returns a new
list representing the reversed list. Use clone() as a model; I recommend
a reverseCells() method.
All the methods (except maybe the first) are O(n): you have to
step through the list to position n. If you add a count_ field, then
size() is O(1); otherwise it too is O(n).
There is also a C++ version, linkedlist.cpp.
For this, I want you to implement a destructor, that calls
delete() on each cell as it is being deallocated; this is done in lieu of
garbage collection. However, you can skip reverse(). The complete list is
- int size()
- T get(int n).
- void Set(int n, T val)
- void insertAfter(int n, T val)
- ~LinkedList(), which should go through each cell and delete() it. You
do this with delete(q), if q is a pointer to the Cell. Note the
destructor output, indicating when it is called.
In C++, use NULL (or 0) instead of null.
To submit your project, create a zipfile and put it on Sakai or email it to
me at pld@cs.luc.edu.