Comp 388 lab 3 - linked lists
Goals
- dynamic allocation
- first look at linked lists
Overview
Part 1: Consider my simple linked list demo, available at linkedstrlist.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
LinkedStrList class and keep it appropriately updated.
- string 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(). Perhaps the simplest
implementation is to notice in the loop if p==null, and simply return
null in that case.
- void Set(int n, string val): update the value of the nth cell, if
0<=n<size(); do nothing otherwise.
- void insertAfter(int n, string 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.
- LinkedStrList 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).
Part 2: There is also a C++ version, linkedlist.cpp.
It uses a template parameter T (in C# these are called generic type
parameters). 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 in the demo file, 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.