Chapter 4 - Generics

Generics

Every LinkedList method written so far operates on int values. The node stores an int, Prepend takes an int, and Filter’s predicate and Map’s transform both work on ints. The entire class is tied to a single type.

That worked as long as the list only needed to hold integers. As soon as you want a list of Rectangles, the design starts to repeat itself. You could copy the LinkedListNode class, rename it to RectangleNode, and replace every int with Rectangle. Then copy LinkedList, rename it to RectangleList, and make the same replacements throughout.

Here is the original node:

class LinkedListNode
{
    public int Value;
    public LinkedListNode? Next;
 
    public LinkedListNode(int value)
    {
        this.Value = value;
        this.Next = null;
    }
}

And here is the Rectangle version:

class RectangleNode
{
    public Rectangle Value;
    public RectangleNode? Next;
 
    public RectangleNode(Rectangle value)
    {
        this.Value = value;
        this.Next = null;
    }
}

RectangleNode is the same node class with one structural change: the Value field has type Rectangle where LinkedListNode used int. The same problem would appear for StringNode, BankAccountNode, or StudentNode. You would keep copying the same class with the only difference being the type of the Value field.

Higher-order functions solved duplication where the changing part was the operation inside the loop. Here, the changing part is the type stored in the node and passed through the class. The next step is to make that type a parameter.

Type Parameters

A type parameter is a placeholder for a type, with the concrete type supplied where the class or method is used.

Here is the LinkedListNode rewritten with a type parameter:

class LinkedListNode<T>
{
    public T Value;
    public LinkedListNode<T>? Next;
 
    public LinkedListNode(T value)
    {
        this.Value = value;
        this.Next = null;
    }
}

Translation: “Define a class named LinkedListNode with a type parameter T. The Value field holds a value of type T. The Next field holds a reference to another LinkedListNode of T, or null. The constructor takes a value of type T and binds it to the Value field.”

T is not a specific type. It stands for whatever type the caller provides when creating a node. One class definition can now serve every element type.

The generic version does not change the fields or links in the node. It changes what was fixed before: the type of the Value field is now a parameter.

LinkedListNode<int> substitutes int for T, so Value is an int. LinkedListNode<string> substitutes string for T, so Value is a string. LinkedListNode<Rectangle> substitutes Rectangle for T, so Value is a Rectangle. One class definition produces as many concrete types as we need.

A generic class is a class defined with one or more type parameters.

Try it yourself.

Write a generic class named Wrapper with a type parameter T. It should have a single public field named Data of type T, and a constructor that takes a T and binds it to Data.

Reveal answer

class Wrapper<T>
{
    public T Data;
 
    public Wrapper(T data)
    {
        this.Data = data;
    }
}

Self-correct against the model above.

Try it yourself.

Translate this code to English:

LinkedListNode<string> node = new LinkedListNode<string>("hello");

Reveal answer

“Create a LinkedListNode of string with the value "hello", and store a reference to it in node.”

If your answer differed, note what you missed before continuing.

A Generic LinkedList

The LinkedList class itself needs to become generic too. Start with the constructor and Count. Count does not compare values, so it generalizes cleanly.

class LinkedList<T>
{
    private LinkedListNode<T>? head;
 
    public LinkedList()
    {
        this.head = null;
    }
 
    public void Prepend(T value)
    {
        LinkedListNode<T> newNode = new LinkedListNode<T>(value);
        newNode.Next = this.head;
        this.head = newNode;
    }
 
    public int Count()
    {
        int count = 0;
        LinkedListNode<T>? current = this.head;
        while (current != null)
        {
            count++;
            current = current.Next;
        }
        return count;
    }
}

Prepend and Count keep the same jobs they had before. The change is that Prepend now takes a value of type T, and the list stores nodes whose Value field is type T. Count still returns an int, because it counts nodes rather than values.

Append changes for the same reason: its parameter and the node it creates now use T instead of int:

public void Append(T value)
{
    LinkedListNode<T> newNode = new LinkedListNode<T>(value);
    if (this.head == null)
    {
        this.head = newNode;
        return;
    }
    LinkedListNode<T> current = this.head;
    while (current.Next != null)
    {
        current = current.Next;
    }
    current.Next = newNode;
}

Filter and Map will use Append when they build their result lists so that element order matches the original.

To create a list, specify the type in angle brackets:

LinkedList<int> numbers = new LinkedList<int>();
numbers.Prepend(42);
numbers.Prepend(17);
 
LinkedList<string> names = new LinkedList<string>();
names.Prepend("Alice");
names.Prepend("Bob");
 
LinkedList<Rectangle> shapes = new LinkedList<Rectangle>();
shapes.Prepend(new Rectangle(10, 5));
shapes.Prepend(new Rectangle(3, 8));

Translation for the first line: “Create a LinkedList of int and store a reference to it in numbers.”

Each list enforces its type. numbers.Prepend("hello") produces a compiler error because “hello” is a string, not an int. The type parameter locks the list to a single element type, just as the original LinkedList was locked to int. The difference is that the caller chooses the element type when creating the list, rather than the class author fixing it in the class definition.

Try it yourself.

Create a LinkedList<BankAccount> named accounts. Prepend two BankAccount objects: one for “Alice” with balance 500, and one for “Bob” with balance 1200. Write a call to Count and store the result in a variable named total.

Reveal answer

LinkedList<BankAccount> accounts = new LinkedList<BankAccount>();
accounts.Prepend(new BankAccount("Alice", 500));
accounts.Prepend(new BankAccount("Bob", 1200));
int total = accounts.Count();

Self-correct against the model above.

Contains and Equality

Count worked without changes because it never looks at the values. Contains does, so this is the first method where the move to generics changes the comparison rule.

The int version of Contains used == to compare values:

if (current.Value == value)

With int, that comparison is unambiguous. Two ints are equal when they hold the same numeric value. The trouble starts when T could be any type, because == means different things for different types.

For value types like int and double, == compares values directly. Two ints are equal when their numbers match. That is the behavior we want for a list of numbers.

For reference types, the default meaning of == is reference equality: it returns true only when both sides refer to the same object in memory. Two separately created Rectangle objects with the same Width and Height would compare as not equal under reference equality, because they occupy different memory locations even though their contents match. Some reference types, like string, override this default so that == compares contents. But not every type does, and the default stays in place for classes like Rectangle and BankAccount unless their authors provide an override.

Replacing int with an arbitrary T forces a decision: what should == mean here? C# resolves this by refusing to guess. Writing current.Value == value on an unconstrained type parameter is a compile-time error. The compiler cannot know in advance whether T will be an int, a Rectangle, or a string, and each of those would need different handling. So the line that worked for int does not even compile when int is replaced by T.

The alternative is .Equals(), a method that every type in C# provides. It comes from the base type that all other types inherit from, so any T is guaranteed to have it. Types that care about value equality override Equals to compare contents. int.Equals(int) compares numbers. string.Equals(string) compares characters. A well-written Rectangle class would override Equals to compare Width and Height. Types that do not override it fall back to reference equality, the same default that == uses for reference types.

Here is Contains rewritten to use .Equals():

public bool Contains(T value)
{
    LinkedListNode<T>? current = this.head;
    while (current != null)
    {
        if (current.Value.Equals(value))
        {
            return true;
        }
        current = current.Next;
    }
    return false;
}

Contains now compiles for any T, and it does the right thing whenever the element type overrides Equals. For a LinkedList<int>, it behaves exactly like the original. For a LinkedList<string>, it compares strings by their characters. For a LinkedList<Rectangle>, the behavior depends on whether Rectangle overrides Equals: if it does, Contains compares rectangles by their dimensions, and if it does not, Contains falls back to reference equality, which only reports true when the caller passes the exact same Rectangle object that was stored in the list.

This is the first place where generics force a real design change. The int-only version could assume value semantics because int is a value type. The generic version cannot assume anything about T, so it uses the one method every type is guaranteed to have.

LinkedList<string> names = new LinkedList<string>();
names.Prepend("Alice");
names.Prepend("Bob");
names.Prepend("Carol");
 
Console.WriteLine(names.Contains("Bob"));    // displays: True
Console.WriteLine(names.Contains("Diana"));  // displays: False

Try it yourself.

Translate this code to English:

bool found = shapes.Contains(new Rectangle(10, 5));

Reveal answer

“Call the Contains method on the object referred to by shapes with a new Rectangle of width 10 and height 5 as the argument. Bind the returned value to found.”

Whether the call returns true depends on whether Rectangle overrides Equals. If it does not, the call returns false even if the list contains a Rectangle with Width 10 and Height 5, because the new Rectangle passed as the argument is a different object in memory.

If your answer differed, note what you missed before continuing.

ForEach and Filter

ForEach and Filter work with values of type T but do not need to compare them or transform them into other types. Both adapt cleanly.

ForEach:

public void ForEach(Action<T> action)
{
    LinkedListNode<T>? current = this.head;
    while (current != null)
    {
        action(current.Value);
        current = current.Next;
    }
}

ForEach still walks the list and applies an action at each node. The action now accepts a T instead of an int.

LinkedList<Rectangle> shapes = new LinkedList<Rectangle>();
shapes.Prepend(new Rectangle(10, 5));
shapes.Prepend(new Rectangle(3, 8));
shapes.Prepend(new Rectangle(15, 4));
 
shapes.ForEach(r => Console.WriteLine(r.Area()));

Output:

60
24
50

Filter:

public LinkedList<T> Filter(Func<T, bool> predicate)
{
    LinkedList<T> result = new LinkedList<T>();
    LinkedListNode<T>? current = this.head;
    while (current != null)
    {
        if (predicate(current.Value))
        {
            result.Append(current.Value);
        }
        current = current.Next;
    }
    return result;
}

Filter changes in the same way: its predicate now takes a T, and the result is still a LinkedList<T> because Filter keeps the same element type.

LinkedList<Rectangle> shapes = new LinkedList<Rectangle>();
shapes.Prepend(new Rectangle(10, 5));
shapes.Prepend(new Rectangle(3, 8));
shapes.Prepend(new Rectangle(15, 4));
shapes.Prepend(new Rectangle(6, 6));
 
LinkedList<Rectangle> squares = shapes.Filter(r => r.IsSquare());

Translation: “Call the Filter method on the object referred to by shapes, passing a predicate that takes a Rectangle r and returns the result of calling IsSquare on r. Bind the returned LinkedList of Rectangle to squares.”

The ForEach action r => Console.WriteLine(r.Area()) and the Filter predicate r => r.IsSquare() both call methods on a Rectangle. Because the list now holds values of a class type, actions and predicates can use any fields and methods the class provides.

Try it yourself.

Write a Filter call on a LinkedList<BankAccount> named accounts that keeps only accounts with a balance above 1000.

Reveal answer

LinkedList<BankAccount> wealthy = accounts.Filter(a => a.Balance > 1000);

Self-correct against the model above.

Try it yourself.

Write a ForEach call on a LinkedList<Rectangle> named shapes that displays the area of each rectangle.

Reveal answer

shapes.ForEach(r => Console.WriteLine(r.Area()));

Self-correct against the model above.

Map with Two Type Parameters

ForEach and Filter kept the same type throughout. Map changes that pattern. It can turn a LinkedList<Rectangle> into a LinkedList<int> of areas, or a LinkedList<BankAccount> into a LinkedList<double> of balances.

The earlier Map transformed ints to ints: Func<int, int>. A T-to-T version would work for scaling rectangles but not for extracting areas. The result list needs its own element type, so Map adds a second type parameter:

public LinkedList<U> Map<U>(Func<T, U> transform)
{
    LinkedList<U> result = new LinkedList<U>();
    LinkedListNode<T>? current = this.head;
    while (current != null)
    {
        result.Append(transform(current.Value));
        current = current.Next;
    }
    return result;
}

The  after the method name declares a new type parameter that belongs to this method. The class already has T for the source element type. Map adds U for the result element type. The transform function bridges the two: it takes a T and returns a U.

Map traverses the source list, applies the transform function to each element, and collects the results in a new list. The source list holds values of type T. The result list holds values of type U.

LinkedList<Rectangle> shapes = new LinkedList<Rectangle>();
shapes.Prepend(new Rectangle(10, 5));
shapes.Prepend(new Rectangle(3, 8));
shapes.Prepend(new Rectangle(15, 4));
 
// T = Rectangle, U = int
LinkedList<int> areas = shapes.Map<int>(r => r.Area());
 
// T = Rectangle, U = bool
LinkedList<bool> squareChecks = shapes.Map<bool>(r => r.IsSquare());

In the first call, the <int> after Map specifies that U is int. The transform function r => r.Area() takes a Rectangle and returns an int. The result is a LinkedList<int>.

In the second call, U is bool. The transform function takes a Rectangle and returns a bool. The result is a LinkedList<bool>.

The T-to-T case still works. When the transform returns the same type as the source, U happens to equal T:

// T = Rectangle, U = Rectangle
LinkedList<Rectangle> doubled = shapes.Map<Rectangle>(r =>
    new Rectangle(r.Width * 2, r.Height * 2));

The more general version still covers the simpler one.

Try it yourself.

Write a Map call on a LinkedList<BankAccount> named accounts that extracts each account’s balance into a LinkedList<double>.

Reveal answer

LinkedList<double> balances = accounts.Map<double>(a => a.Balance);

Self-correct against the model above.

Try it yourself.

Write a Map call on a LinkedList<int> named numbers that converts each integer to its string representation using .ToString().

Reveal answer

LinkedList<string> labels = numbers.Map<string>(n => n.ToString());

Self-correct against the model above.

Fold with Two Type Parameters

Fold has the same issue as Map. The earlier version hard-coded the accumulator as int. For a LinkedList<Rectangle>, you might fold to an int (total area), a double (average), or a string (summary). The accumulator type needs its own parameter too.

The generic Fold keeps the same recursive shape as the int-only version. A public Fold takes the initial value and the combine function, and delegates to a private Fold that takes a node, the accumulator, and the combine function. Both methods carry T from the class and U from the method.

public U Fold<U>(U initial, Func<U, T, U> combine) =>
    Fold<U>(this.head, initial, combine);
 
private U Fold<U>(LinkedListNode<T>? node, U acc, Func<U, T, U> combine) =>
    node switch
    {
        null => acc,
        _ => Fold<U>(node.Next, combine(acc, node.Value), combine)
    };

T is the element type, carried by the class. U is the accumulator type, declared as a method-level type parameter on both Fold overloads. The combine function takes the current accumulator (a U) and the current element (a T), and returns the updated accumulator (a U).

The recursive structure is the same as before. The difference is that the accumulator is now U, and the node type is LinkedListNode<T>?. The method overloading pattern still works without any new rules.

LinkedList<Rectangle> shapes = new LinkedList<Rectangle>();
shapes.Prepend(new Rectangle(10, 5));
shapes.Prepend(new Rectangle(3, 8));
shapes.Prepend(new Rectangle(15, 4));
 
int totalArea = shapes.Fold<int>(0, (acc, r) => acc + r.Area());

Trace through this call. The chain holds the Rectangles in order 15×4, 3×8, 10×5 (head to tail, since Prepend adds at the front):

Fold(node(15x4), 0, combine)
    = Fold(node(3x8), combine(0, 60), combine)
    = Fold(node(3x8), 60, combine)
    = Fold(node(10x5), combine(60, 24), combine)
    = Fold(node(10x5), 84, combine)
    = Fold(null, combine(84, 50), combine)
    = Fold(null, 134, combine)
    = 134

Return value: 134.

The accumulator is an int. The elements are Rectangles. The combine function bridges the two by calling r.Area() on each Rectangle and adding the result to the accumulator.

Here is a fold that produces a string instead:

string summary = shapes.Fold<string>("Sizes:", (acc, r) =>
    acc + " " + r.Width + "x" + r.Height);

The initial value is the string “Sizes:“. The combine function appends each Rectangle’s dimensions. When + is applied to a string and an integer, C# converts the integer to a string and concatenates them. After all three iterations, summary holds "Sizes: 15x4 3x8 10x5".

Try it yourself.

Write a Fold call on a LinkedList<BankAccount> named accounts that computes the total balance across all accounts. The balance is a double.

Reveal answer

double total = accounts.Fold<double>(0.0, (acc, a) => acc + a.Balance);

The initial value is 0.0 (a double). The combine function adds each account’s Balance to the accumulator.

Self-correct against the model above.

Try it yourself.

Trace accounts.Fold<double>(0.0, (acc, a) => acc + a.Balance) on a list containing BankAccounts for Alice (500), Bob (1200), and Carol (350) in chain order from head to tail. Show the recursive unwinding.

What is the return value?

Reveal answer

Fold(node(Alice), 0.0, combine)
    = Fold(node(Bob), combine(0.0, 500), combine)
    = Fold(node(Bob), 500.0, combine)
    = Fold(node(Carol), combine(500.0, 1200), combine)
    = Fold(node(Carol), 1700.0, combine)
    = Fold(null, combine(1700.0, 350), combine)
    = Fold(null, 2050.0, combine)
    = 2050.0

Return value: 2050.0.

Compare your answer and note what you missed.

Type Inference

Every Map and Fold call so far has included the type parameter explicitly: shapes.Map<int>(r => r.Area()), shapes.Fold<int>(0, (acc, r) => acc + r.Area()). That made the new type parameter easy to see while we were introducing it.

Once the pattern is familiar, though, writing <int> every time starts to repeat information the compiler may already know.

The compiler already knows that r => r.Area() returns an int, because the Area method on Rectangle returns int. It also knows that 0 in the Fold call is an int. So the next question is whether C# can determine U on its own.

It can. C# examines the types of the arguments and figures out what the method’s type parameter must be.

Type inference is the compiler determining a type parameter from the types of the arguments, without the programmer writing it explicitly.

Here are the same calls written both ways:

// Explicit type parameter
LinkedList<int> areas = shapes.Map<int>(r => r.Area());
int totalArea = shapes.Fold<int>(0, (acc, r) => acc + r.Area());
 
// Inferred type parameter
LinkedList<int> areas = shapes.Map(r => r.Area());
int totalArea = shapes.Fold(0, (acc, r) => acc + r.Area());

For Map, the compiler looks at the lambda’s return type: r.Area() returns an int, so U must be int. For Fold, the compiler looks at the type of the initial value: 0 is an int, so U must be int. The initial value’s type and the lambda’s return type need to agree, since both represent U.

A few more examples:

// Compiler sees: lambda returns bool. U = bool.
LinkedList<bool> checks = shapes.Map(r => r.IsSquare());
 
// Compiler sees: lambda returns string, initial value is a string. U = string.
string summary = shapes.Fold("Sizes:", (acc, r) =>
    acc + " " + r.Width + "x" + r.Height);
 
// Compiler sees: lambda returns Rectangle. U = Rectangle.
LinkedList<Rectangle> scaled = shapes.Map(r =>
    new Rectangle(r.Width * 2, r.Height * 2));

In each case, the type parameter is determined from the arguments, so the call reads more cleanly without it.

Inference applies to method-level type parameters like U in Map and Fold. Class-level type parameters like T in LinkedList<T> are not inferred. When creating a new list, we still write new LinkedList<int>() or new LinkedList<Rectangle>(). The compiler has no arguments to examine at the point of creation, so there is nothing to infer from.

Try it yourself.

For each call, identify what the compiler infers U to be. Then rewrite the call with the explicit type parameter to confirm.

LinkedList<BankAccount> accounts = new LinkedList<BankAccount>();
accounts.Prepend(new BankAccount("Alice", 500));
accounts.Prepend(new BankAccount("Bob", 1200));
 
LinkedList<double> balances = accounts.Map(a => a.Balance);
LinkedList<string> owners = accounts.Map(a => a.Owner);
double total = accounts.Fold(0.0, (acc, a) => acc + a.Balance);

Reveal answer

For accounts.Map(a => a.Balance): a.Balance is a double, so U = double. Explicit version: accounts.Map<double>(a => a.Balance).

For accounts.Map(a => a.Owner): a.Owner is a string, so U = string. Explicit version: accounts.Map<string>(a => a.Owner).

For accounts.Fold(0.0, (acc, a) => acc + a.Balance): the initial value 0.0 is a double, so U = double. Explicit version: accounts.Fold<double>(0.0, (acc, a) => acc + a.Balance).

If your answers differed, check the return type of each lambda and the type of the initial value.

Putting It Together

At this point, the same linked list methods from the previous section work on any element type. The code below uses BankAccount, but the pattern is the same for rectangles, strings, or other classes:

LinkedList<BankAccount> accounts = new LinkedList<BankAccount>();
accounts.Prepend(new BankAccount("Alice", 500));
accounts.Prepend(new BankAccount("Bob", 1200));
accounts.Prepend(new BankAccount("Carol", 350));
 
// Display each account's owner
accounts.ForEach(a => Console.WriteLine(a.Owner));
 
// Keep only accounts with balance over 400
LinkedList<BankAccount> wealthy = accounts.Filter(a => a.Balance > 400);
 
// Extract all balances into a list of doubles
LinkedList<double> balances = accounts.Map(a => a.Balance);
 
// Sum all balances
double total = accounts.Fold(0.0, (acc, a) => acc + a.Balance);
 
// Compose: sum of balances for accounts over 400
double wealthyTotal = accounts
    .Filter(a => a.Balance > 400)
    .Fold(0.0, (acc, a) => acc + a.Balance);

The call style matches the int-only versions. The difference is that the values flowing through these methods are BankAccounts rather than ints.

Before generics, answering “what’s the total balance for accounts over 400?” would have required a custom method with a hand-written loop for that specific type. Now the same Filter and Fold methods work here too. Filter produces a LinkedList<BankAccount> containing Alice and Bob (both above 400). Fold sums their balances: 500 + 1200 = 1700.0.

Try it yourself.

Write a chained expression on a LinkedList<Rectangle> named shapes that keeps only rectangles with area greater than 30, then computes the sum of their areas.

Reveal answer

int totalArea = shapes
    .Filter(r => r.Area() > 30)
    .Fold(0, (acc, r) => acc + r.Area());

Filter keeps rectangles whose area exceeds 30. Fold sums the areas of the remaining rectangles.

Self-correct against the model above.

Try it yourself.

Write code that creates a LinkedList<Rectangle>, prepends three rectangles, uses Map to produce a LinkedList<string> where each string is the rectangle’s width followed by “x” followed by its height (for example, “10x5”), and then calls ForEach to display each string.

Reveal answer

LinkedList<Rectangle> shapes = new LinkedList<Rectangle>();
shapes.Prepend(new Rectangle(10, 5));
shapes.Prepend(new Rectangle(3, 8));
shapes.Prepend(new Rectangle(15, 4));
 
LinkedList<string> labels = shapes.Map(r => r.Width + "x" + r.Height);
labels.ForEach(s => Console.WriteLine(s));

Self-correct against the model above.

Review

Attempt each exercise from memory, then search this section to check your answers, then note what you missed.

Part 1: Definitions

Write the definitions from memory, then find them in this section to check.

What is a type parameter?
What is a generic class?
What is type inference?

If any of your answers differed from the definitions in this section, note what you missed and write the corrected version.

Part 2: Translations

Translate each piece of code to English.

LinkedList<string> names = new LinkedList<string>();
names.Prepend("Alice");
LinkedList<int> areas = shapes.Map<int>(r => r.Area());
LinkedList<int> areas = shapes.Map(r => r.Area());
double total = accounts.Fold(0.0, (acc, a) => acc + a.Balance);
LinkedList<BankAccount> rich = accounts.Filter(a => a.Balance > 1000);

Check your translations against the patterns shown earlier in this section.

Part 3: Writing Code

Write the code for each description. Do not look at the examples in this section.

Define a generic class named Pair with a type parameter T. It should have two public fields, First and Second, both of type T, and a constructor that takes two T values and binds them to the corresponding fields.
Create a LinkedList<Rectangle> named rooms. Prepend three Rectangle objects with different dimensions.
Write a Filter call on rooms that keeps only rectangles whose area is at least 40.
Write a Map call on rooms that produces a LinkedList<bool> indicating whether each rectangle is a square.
Write a Fold call on rooms that computes the total perimeter of all rectangles.
Write a chained expression on rooms that keeps rectangles wider than 5, then extracts their areas into a LinkedList<int>.

Part 4: Tracing

Trace shapes.Fold(0, (acc, r) => acc + r.Area()) where shapes contains Rectangles 4×3, 6×2, 5×5 (head to tail). Show the recursive unwinding, the same way we traced Fold earlier in this section.

What is the return value?

Part 5: Type Inference

For each call, identify what the compiler infers U to be.

shapes.Map(r => r.Area())
shapes.Map(r => r.IsSquare())
shapes.Map(r => r.Width + "x" + r.Height)
shapes.Fold(0, (acc, r) => acc + r.Perimeter())
shapes.Fold("", (acc, r) => acc + r.Area() + " ")

Part 6: Concept Connections

Explain why Map needs a method-level type parameter (U) but Filter does not. What is different about what the two methods return?
Explain why class-level type parameters (T in LinkedList<T>) must be written explicitly, but method-level type parameters (U in Map) can be inferred.
Higher-order methods parameterized behavior: methods accepted functions as inputs so the caller could decide what to do at each node. Generics parameterize type: LinkedList<T> accepts a type so the caller can decide what kind of data the list holds. Describe these two forms of abstraction in your own words, and explain how a method like Map uses both at the same time.
The recursive int-only Fold used method overloading on int parameters. The generic Fold in this section uses method overloading on parameters that involve both T and U. Describe what changed between the two versions and what stayed the same. Why does the method overloading pattern still work when type parameters are involved?
The generic Contains uses .Equals() instead of ==. Explain why == does not work on an unconstrained type parameter, and describe what could go wrong when calling Contains on a LinkedList<Rectangle> if the Rectangle class does not override Equals.

The linked list started as an int-only class. Generics changed the stored type from a fixed choice into a parameter, so the same structure now works for rectangles, bank accounts, strings, or anything else.

These same ideas show up throughout C#‘s standard library. List<T>, Dictionary<TKey, TValue>, and Queue<T> are generic classes. LINQ methods like Where, Select, and Aggregate are higher-order methods on generic collections. This chapter builds the basic ideas those library features use.

Previous: Section 4 - Higher-Order Methods

Fundamentals of Computer Science

Explorer

Chapter 4 - Generics

Generics

Type Parameters

A Generic LinkedList

Contains and Equality

ForEach and Filter

Map with Two Type Parameters

Fold with Two Type Parameters

Type Inference

Putting It Together

Review

Part 1: Definitions

Part 2: Translations

Part 3: Writing Code

Part 4: Tracing

Part 5: Type Inference

Part 6: Concept Connections

Table of Contents

Backlinks