Comp 388 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

• 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.