TypeScript Call-by-Reference Confusion

Question

Folks,

while familiarizing myself with TypeScript, I ran into serious troubles getting a straightforward LinkedList implementation to work properly.

Here's the source code - I'll describe the problem in detail below.

class LinkedList<ListType> {

     firstElement:ListItem<ListType> = null;

     /**
      * add Element in Front of List
      */
     addElementFirst(element: ListType) {
         var newItem:ListItem<ListType> = new ListItem<ListType>();

         newItem.setElement(element);
         newItem.setNextItem(this.firstElement);

         this.firstElement = newItem;
     }

    /**
     * add Element at End of List;
     */
    addElementLast(element: ListType) {

         var newItem:ListItem<ListType> = new ListItem<ListType>();
         newItem.setNextItem(null);
         newItem.setElement(element);

         //find last Element;
         var li:ListItem<ListType> = this.firstElement; //THIS IS
         while (li!=null) li=li.getNextItem(); //WHERE IT
         li = newItem; //BREAKS!
    }


    dumpListContents() {

         var li:ListItem<ListType> = this.firstElement;
        var i:number = 0; 
        while (li!=null) {
            console.log(i+". "+li.getElement());
            li=li.getNextItem(); 
            i++
        }

    }


}

class ListItem<ListType> {
    private element:ListType;
    private nextItem: ListItem<ListType>;

    setElement(element:ListType) {

        this.element=element;

    }

    getElement():ListType {

        return this.element;

    }


    setNextItem(nextItem:ListItem<ListType>) {

        this.nextItem=nextItem;


    }

    getNextItem():ListItem<ListType> {

        return this.nextItem;    

    }

}


var foo:LinkedList<string> = new LinkedList<string>();
var bar:LinkedList<string> = new LinkedList<string>();

console.log("Playing with foo");
foo.addElementFirst("first");
foo.addElementFirst("second");
foo.addElementFirst("third");

foo.dumpListContents();

console.log("Playing with bar");
bar.addElementLast("first");
bar.addElementLast("second");
bar.addElementLast("third");

bar.dumpListContents();

The code above implements a simple typed LinkedList using Generics a long the lines as its done in other OO languages. The problem is that addElementFirst works perfectly, but addElementLast fails miserably.

Why is that the case? My strong assumption is that the assignments

  var li:ListItem<ListType> = this.firstElement; //THIS IS
  while (li!=null) li=li.getNextItem(); //WHERE IT
  li = newItem; //BREAKS!

assign a value to a local variable (instead of passing a reference!) and hence, all changes subsequently made to the data structure in addElementLast are local and do not operate on the original data structure all. The resulting JS code looks as follows and substantiates this assumption:

 LinkedList.prototype.addElementLast = function (element) {
        var newItem = new ListItem();
        newItem.nextItem = null;
        newItem.element = element;
        //find last Element;
        var li = this.firstElement;
        while (li != null)
            li = li.nextItem;
        li = newItem;
    };

Theoretically spoken, I fear that I fell that assignment semantics differ largely from Java here, where analog code would work, as all assignments would be made using references only.

Is there an easy conceptual way around this problem? Can I force the underlying JavaScript to stricly use references?

Best Regards, Elias

Answer 1

All you're doing is assigning the newItem to the local variable li

//find last Element;
var li:ListItem<ListType> = this.firstElement;
while (li!=null) li=li.getNextItem();
//At this point, li is null.  All you're doing is assigning the newItem to your variable
li = newItem;

What you need to do is utilise your setNextItem method after looping to your last element:

//find last Element;
var li:ListItem<ListType> = this.firstElement;
while (li.getNextItem()!=null) li=li.getNextItem();
//At this point, li is the last element
li.setNextItem(newItem);

Note that we don't assign li to the next item when it is null, so it remains pointing at the last item in the list. Finally, in case the list doesn't have any elements, we need to handle that:

//find last Element;
if (this.firstElement == null) {
    this.firstElement = newItem;
} else {
    var li:ListItem<ListType> = this.firstElement;
    while (li.getNextItem()!=null) li=li.getNextItem();
    //At this point, li is the last element
    li.setNextItem(newItem);
}