Comp 110 Linked List Overview

What is a Linked List?

'Linked List' is the term used to refer to a data structure consisting of Node objects. A list may also simply be empty.

Each Node object has two properties; data (a number, string, etc) and next (another Node). Nodes in the same list must have the same data type.

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

Via these next properties, a chain of nodes is created. The next of the last Node in the List will point to 'null.' This means that linked lists are null terminated.

Creating a List:

let myList: Node; //declares a list
myList = cons("Hello, cons("World, null)); //initializes the list using "cons"

Important Concepts for Lists:

Null is essentially a reference to nowhere. When using recursion, our base case (that determines when the recursive calls end) will usually involve testing for 'null'

In 110, there is a 'Node' class and several functions that are available to import - 

import { Node, cons, first, rest, toString } from "./list";
// by importing from "./list" you now have access to the Node class and these functions!

Lists are phenomenal for learning recursive concepts! Recursion with lists will also look a little different from the recursion we have done so far. We can build lists recursively, as well as determine things about already constructed lists, seen below.

Searching for a value in a list...

//findEmployee prints a string depending on whether a particular employee name is present in the list
let findEmployee = (list: Node<string>, name: string): string => {
    if (list === null) {
        return name + " isn't in this list";    // we have gotten to the end of the list...employee was not in the list
    } else if (first(list) === name) {          // does the current node at the front of the list contain employee?
        return "We found " + name + "!";
    } else {
        return findEmployee(rest(list), name);          // employee hasnt been found yet, so we continue the search
    }
};

//countEmployees recursively returns the number of employees in the list
let countEmployees = (list: Node<string>): number => {
    if (list === null) {
        return 0;
    } else {
        return 1 + countEmployees(rest(list));
    }
};

let salesmen = cons("Jim", cons("Dwight", cons("Andy", null)));
let executives = cons("Jan", cons("Michael", cons("David", null)));
let beetFarmers = cons("Dwight", null);

print(findEmployee(salesmen, "Michael")); //-> prints "Michael isn't in this list"
print(findEmployee(executives, "Michael")); //-> prints "We found Michael!"

print(countEmployees(salesmen)); //-> prints 3
print(countEmployees(beetFarmers)); //-> prints 1
print(countEmployees(null)); //-> prints 0