Comp 110 List Functions

The following functions/classes can be imported from ./list via:

import { Node, cons, first, rest, toString } from "./list";

The "Node" class

Defines properties that can be found in a 'Node' object. Each node contains a reference to another node...a "list" is actually just a single node that points to another node that points to another node...etc...

class Node {
    data: string = "";
    next: Node = null;
}

An example of a list containing two nodes:

The 'cons' Function

The implementation:

export let cons = (data: string, next: Node): Node => {
    let n = new Node();
    n.data = data;
    n.next = next;
    return n;
}; 

What does it do?

By passing in a string and a node (or a function call that returns a node), a new list is created and returned!

For example:

let shortList = cons("shorty", null);
// a list with 1 node that ends in 'null'
let medList = cons("hello", cons("world", null));
// for the second parameter, cons takes in a nested 'cons' call that returns a node!
"hello"->("world"->null) becomes "hello"->"world"->null
let longList = cons("look", cons("@", cons("all", cons("those", cons("chickens", null)))));
// creates "look"->"@"->"all"->"those"->"chickens"->null

The 'first' Function

The implementation:

export let first = (n: Node): string => {
    return n.data;
}; 

What does it do?

'first' takes in a list (AKA a node that points to other nodes) and returns the node at the front of that list (AKA 'the head')

An example:

let helloWorld = cons("hello", cons("world", cons("ayeee", null)));
// helloWorld is "hello"->"world"->"ayeee"->null
let hello = first(helloWorld);
// hello is the string "hellO"

The 'rest' Function

The implementation:

export let rest = (n: Node): Node => {
    return n.next;
};

What does it do?

'rest' takes in a list (AKA a node that points to other nodes) and returns a list with the head (the first node) cut off!

An example:

let helloWorld = cons("hello", cons("world", cons("ayeee", null)));
// helloWorld is "hello"->"world"->"ayeee"->null
let world = rest(helloWorld);
// toString(world) returns "world"->"ayeee"->null

The 'toString' Function

The implementation:

export let toString = (n: Node): string => {
    if (n === null) {
        return "NULL"; // this is a base case!
    } else {
        return first(n) + " → " + toString(rest(n)); // this is recursion!
    }
};

What does it do?

'toString' takes in a list (AKA a node that points to other nodes) and returns a string of the 'data'-s contained with in a list.

Note: this function does not contain any logic that will change the list itself; it simply allows us to display the list in a more accessible way using strings.

An example:

let helloWorld = cons("hello", cons("world", cons("ayeee", null)));
print(toString(helloWorld)); // will print "hello"->"world"->"ayeee"->null