Comp 388 lab 3 - linked lists
Goals
- dynamic allocation
- first look at linked lists
Overview
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(). Your best bet 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).
Option: do the above to the LinkedTList
class, which uses a generic type T instead of a fixed type string.
The file is linkedTlist.cs. When compiling,
ignore this warning:
Type parameter `T' has the same name as the
type parameter from outer type `LinkedTList<T>'
To submit your project, create a zipfile and put it on Sakai or email it to
me at pld@cs.luc.edu.