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.

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.

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'

There are several special functions in 'introcs' that allow us to manipulate lists!

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

Note: the above example utilizes generic types as referenced in lecture 14.