Comp 110 Linked List/Node Functions

Linked List Functions

There are some functions that make working with linked lists more fun. These include cons to help us construct a list, first to get out the first item in a list, and rest to get everything else in the list except the first item. We'll look closer at these now:

cons

The cons function is used to build up linked lists. It takes in the value that you are adding to your list and the list that you are adding the value onto.

Note: When we say a function takes in values, we are referring to the function's parameters. In this case, the cons function has two parameters: 

  • a value of the same type as the values in the list
  • a list you are starting with. This can also be null if you want to construct a brand new list

The cons function returns a new list with the value added to the front.

cons function implementation

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

This function first takes in a string parameter, data. It makes a new Node object and sets that object's data property to be the string parameter data taken in by the function. It also takes in a Node parameter, next. This next value taken in as a parameter by the function is assigned to the next property of the Node object we made. So, the object's data and next properties now reflect the information passed into the function.

Since Node is a recursive data type, we know that whatever Node object we passed in could have a next property that refers to another Node. And that Node could have a next property that refers to another Node. In this way, with all these next properties linking to other Node objects, we've got a list. So making a new Node and connecting its next property to the front of another list of Nodes just adds it and makes it the new front of the list!

Example with cons

let courses: Node = cons("comp101", null); 
// courses is the list "comp101"->null
courses = cons("comp110", courses); 
// this makes the list "comp110"->"comp101"->null
// and assigns that list to the courses variable
 
// we could've combined those two lines into one:
let classes: Node = cons("comp110", cons("comp101", null));

first

The first function finds the first item in a list. If first is given an empty list, we'll get an error. So, the only parameter first has is a Node, n. This is because first is taking in a list, which is really just a series of Node objects whose next properties connect to form a list. So, the Node we pass in is really giving us the list we want to find the first item of.

first function implementation

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

Since we want to know what the first item in the list is, and the first function takes in the Node that starts our list, all the function does is return the data property of the Node it took in. The Node passed in starts off the list. But for this function all we need to return is the data of the first item in the list, and the first item in the list is in the Node that starts the list (the one that is the parameter of the function!) so we can just access and return the data property of the Node that was the parameter.

Example with first

// continuing with where we left off in previous examples
let s: string = first(classes); 
// s is "comp110"
 
let depts: Node = cons("computer science", cons("biology", cons("mathematics", null)));
// depts is "computer science"->"biology"->"mathematics"->null
let f: string = first(depts); 
// f is "computer science"

rest

The rest function will take in a list and give back a sublist of that original list. The sublist it returns will have all the same items as the original list except it will be missing the first item in the original list. If it is given an empty list, we'll get an error. So, the only parameter rest has is a non-empty list. This means that since a list is a chain of connected Node objects, the parameter will be of type Node.

rest function implementation

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

The rest function takes in a Node, n. This is the Node that starts off the list, and its next property links to the next Node in the list. The goal of the rest function is to return a list containing all items in the first list except the starting item, so this means we want our returned list to start with the next Node after the given Node. To do this, we return the next property of the Node we are given. So, the function returns the Node that used to be second in our original list, which then links on to everything else that came after it in the starting list! Now, the new list we return starts at the second item of the original list and still has everything else that came after it from before!

Example with rest

// continuing with same example
 
let restOfClasses: Node = rest(classes);
// restOfClasses is the list "comp101"->null
 
let otherDepts: Node = rest(depts);
// otherDepts is the list "biology"->"mathematics"->null
 
 
let list: Node = cons("linked", null);
// list is "linked"->null
let restOfList: Node = rest(list);
// restOfList is null