CS 225 List

Write a class called List that implements linked lists of integers.

All functions must be implemented using recursion. No loops of any kind are allowed.

The lists are always kept in increasing order. You may assume that the argu- ments to each function are already in increasing order.

Implement the functions shown below.

using System;

public class List {

class Node {
public int item;
public Node next;
}

Node first;

public List() {
first = null;
}

static Node Add(Node node, int item) {
// Helper function.
}

public void Add(int item) {
// Adds item to a list, putting in the right place so that the list
// remains in increasing order.
}

static int Length(Node node) {
// Helper function.
}

public int Length() {
// Returns the length of the list.
}

static int Count(Node node, int item) {
// Helper function.
}

public int Count(int item) {
// Returns the number of occurrences of item.
}

static int Sum(Node node) {
// Helper function.
}

public int Sum() {
// Returns the sum of the numbers in the list.
}

static Node Filter(Node node, Func test) {
// Helper function.
}

public static List Filter(List list, Func test) {
// Returns a new list containing the items from list for which the function
// test returns true.
}

static Node Copy(Node node) {
// Helper function.
}

public List Copy() {
// Makes a copy of the list (with all new nodes).
}

static Node Merge(Node node1, Node node2) {
// Helper function.
}

public static List Merge(List list1, List list2) {
// Merges two lists using the merge algorithm. Must run in linear times.
}

static string ToString(Node node) {
// Helper function.
}

public override string ToString() {
// Returns a string representation of a list that looks like [1,2,4,5,7].
// The empty list looks like [].
// A list with one item looks like [2].
}
}