Data and Memory
We have been using structs to define custom types since Chapter 1. A struct groups related fields under one name: a Door has IsOpen and IsLocked, a Rectangle has Width and Height, a Student has Name and Score. Structs have carried us through three chapters, but three limitations have been building up.
The first: initialization is manual. Every time we create a struct, we write separate lines to bind each field. In Chapter 2, we solved this with Make functions like MakeRectangle and MakeStudent, but those are workarounds we write ourselves. The language does not help.
The second: structs are value types. Copying a struct copies all its fields into an independent duplicate. In Chapter 3, we saw that this can cause confusion when a struct contains a reference-type field like an array, because the copy shares the array with the original. More broadly, value semantics mean two variables can never refer to the same struct object. Sometimes sharing is exactly what we want.
The third: all fields are public. In Chapter 1, when we introduced the public keyword, we said: “Imagine a bank account with a balance field. You might want to prevent code from directly setting the balance to any value.” We never delivered on that idea. Structs gave us no way to hide a field.
Classes solve all three problems. They provide built-in initialization, reference semantics, and access control. We learn the mechanics in the first half of this section using simple examples, then apply them to build a new kind of collection in the second half.
Classes
A class is a reference type definition that groups fields and methods into a single unit.
Structs are value types: variables hold the data directly. Classes are reference types: variables hold a reference to an object that lives elsewhere in memory. We saw this with arrays in Chapter 3, where arrays are reference types. Classes let us define our own.
Here is a familiar struct:
struct Rectangle
{
public int Width;
public int Height;
}Here is the same data as a class:
class Rectangle
{
public int Width;
public int Height;
}Translation: “Define a class named Rectangle with public integer fields Width and Height.”
The syntax is nearly identical. The keyword changed from struct to class. The fields, the braces, the public markers are all the same. The difference is in how the type behaves, and we see that difference when we create objects and copy variables.
Creating Objects with new
With a struct, declaring a variable reserves space for the data directly:
Rectangle rect; // struct: space for Width and Height exists now
rect.Width = 10;
rect.Height = 5;With a class, declaring a variable only creates a reference. The object itself must be created explicitly with new:
Rectangle rect = new Rectangle(); // class: create an object, store a reference
rect.Width = 10;
rect.Height = 5;Translation: “Create a Rectangle object and store a reference to it in rect. Bind 10 to the Width field of the object stored at rect. Bind 5 to the Height field of the object stored at rect.”
The discrete actions for new Rectangle():
- Allocate memory for a Rectangle object (with space for Width and Height)
- Create a reference variable named rect
- Store a reference to the new object in rect
This is the same mechanism we used for arrays. new int[5] created an array object and stored a reference in a variable. new Rectangle() creates a Rectangle object and stores a reference in a variable.
rect
┌──────┐
│ ref ──────> ┌──────────────┐
└──────┘ │ Width: 10 │
│ Height: 5 │
└──────────────┘
The variable rect holds a reference to the Rectangle object, which lives elsewhere in memory.
Try it yourself.
Translate this code to English:
Rectangle box = new Rectangle();
box.Width = 20;
box.Height = 8;Write your answer before revealing ours.
Reveal answer
“Create a Rectangle object and store a reference to it in box. Bind 20 to the Width field of the object stored at box. Bind 8 to the Height field of the object stored at box.”
If your answer differed, note what you missed before continuing.
Constructors
Creating a class object still takes multiple lines: create with new, then bind each field. In Chapter 2, we solved this for structs with Make functions:
Func<int, int, Rectangle> MakeRectangle = (w, h) =>
{
Rectangle r = new Rectangle();
r.Width = w;
r.Height = h;
return r;
};
Rectangle box = MakeRectangle(10, 5);Description: “MakeRectangle takes a width and a height, creates a new Rectangle with those values, and returns it.”
Classes have a built-in version of this pattern.
A constructor is a special method that shares its name with the class it constructs. It initializes a new object’s fields when the object is created.
class Rectangle
{
public int Width;
public int Height;
public Rectangle(int width, int height)
{
this.Width = width;
this.Height = height;
}
}The constructor is the block starting with public Rectangle(int width, int height). It lives inside the class definition, its name matches the class name, and it takes parameters that it uses to bind values to the new object’s fields.
Description: “The Rectangle constructor takes a width and a height, and binds them to the corresponding fields of the new object.”
this, when used within a constructor or method, is a keyword that refers to the object it is being called on. this.Width means “the Width field of this particular object.”
To create a Rectangle, we now write:
Rectangle box = new Rectangle(10, 5);Translation: “Create a Rectangle object with width 10 and height 5, and store a reference to it in box.”
Here is what happens:
- Allocate memory for a Rectangle object
- Run the constructor with arguments 10 and 5
- Inside the constructor: bind 10 to this.Width, bind 5 to this.Height
- Store a reference to the new object in box
Compare the two approaches. The Make function and the constructor both take parameters and produce a ready-to-use object. The constructor moved the function inside the class, replaced the explicit new and field assignments with this.field = parameter, and eliminated the explicit return because new handles both creation and return. At the call site, one line replaces four. The Make function was the workaround; the constructor is the built-in version.
Try it yourself.
Write a class definition with a constructor from this description:
Define a class named Point with public integer fields X and Y. Define a constructor that takes two integers (x and y) and binds them to the corresponding fields.
Reveal answer
class Point
{
public int X;
public int Y;
public Point(int x, int y)
{
this.X = x;
this.Y = y;
}
}Self-correct against the model above.
Try it yourself.
Translate this code to English:
Point origin = new Point(0, 0);Reveal answer
“Create a new Point object with x 0 and y 0, and store a reference to it in origin.”
If your answer differed, note what you missed before continuing.
Copying: Reference Semantics
With structs, copying a variable copies all the field values. The two copies are independent:
// Struct behavior (Chapter 1):
Rectangle a;
a.Width = 10;
a.Height = 5;
Rectangle b = a;
b.Width = 99;
// a.Width is still 10. The copies are independent.With classes, copying a variable copies the reference, not the object. Both variables end up referring to the same object:
// Class behavior:
Rectangle a = new Rectangle(10, 5);
Rectangle b = a;
b.Width = 99;
Console.WriteLine(a.Width); // displays 99Translation for Rectangle b = a;: “Make a reference to a Rectangle named b, link it to the object at a.”
a
┌──────┐
│ ref ──────> ┌──────────────┐
└──────┘ │ Width: 99 │
│ Height: 5 │
b └──────────────┘
┌──────┐ ^
│ ref ─────────────┘
└──────┘
After the assignment, both a and b refer to the same Rectangle object. When we changed Width through b, the change was visible through a because both names lead to the same object. This is reference type behavior: copying the variable copies the reference, not the data.
State table:
| after line | a.Width | a.Height | b points to |
|---|---|---|---|
| 1 | 10 | 5 | — |
| 2 | 10 | 5 | same object as a |
| 3 | 99 | 5 | same object as a |
Try it yourself.
What does this code display?
Point p = new Point(3, 7);
Point q = p;
q.Y = 100;
Console.WriteLine(p.Y);Reveal answer
Output:
100
q = p copies the reference, so both p and q point to the same Point object. q.Y = 100 changes that object’s Y field, and p.Y reads the same field.
If your answer differed, trace through each line and identify where your reasoning went wrong.
The Class Boundary
A class creates a boundary between inside code and outside code.
Inside the boundary, every member of a class can see every other member. The constructor can access fields. Methods can read fields, write fields, and call other methods. Nothing inside the class needs permission to interact with anything else inside the class.
Outside the boundary, code that uses the class only sees what the class allows. Two keywords control this.
A public member is accessible from outside the class.
A private member is accessible only from inside the class that defines it.
Here is a class where one field is public and the other is private:
class BankAccount
{
private int balance;
public string Owner;
public BankAccount(string owner, int initial)
{
this.Owner = owner;
this.balance = initial;
}
}The constructor can access both fields because it lives inside the class. Outside code can only reach Owner:
BankAccount acct = new BankAccount("Alice", 500);
Console.WriteLine(acct.Owner); // OK: Owner is public
Console.WriteLine(acct.balance); // Error: balance is private
acct.balance = 0; // Error: balance is privateThe only way to interact with balance from outside would be through public methods defined inside the class. We build those when we give objects behavior. For now, the important thing is that the boundary exists and that public vs private determines what crosses it.
Try it yourself.
Consider this class:
class Vault
{
private string code;
public bool IsLocked;
public Vault(string secretCode)
{
this.code = secretCode;
this.IsLocked = true;
}
}For each line of outside code, determine whether it compiles or produces an error. Explain why.
Vault v = new Vault("abc123");
Console.WriteLine(v.IsLocked);
Console.WriteLine(v.code);
v.IsLocked = false;
v.code = "hacked";Reveal answer
Line 1 compiles. The constructor is public, so outside code can create Vault objects.
Line 2 compiles. IsLocked is public, so outside code can read it.
Line 3 produces an error. code is private. Outside code cannot read it.
Line 4 compiles. IsLocked is public, so outside code can write to it.
Line 5 produces an error. code is private. Outside code cannot write to it.
If your answer differed, note what you missed before continuing.
What a Class Contains
A class can contain four kinds of members. A member is anything declared inside a class: fields, constructors, methods, and properties are all members.
- Fields store data. We have seen these:
Width,Height,balance. - Constructors initialize a new object. We just learned these: the Make function from Chapter 2, moved inside the class.
- Methods perform operations on the object’s data. We build these when we give objects behavior.
- Properties provide controlled access to fields. We cover these alongside methods.
All four live inside the class boundary. All four can see each other.
In previous chapters, we wrote standalone functions that took an object as a parameter. A method lives inside the class instead. It operates on a specific object, and that object is this. The object on the left side of the dot becomes this inside the method. We trace this mechanism in full once we start building methods.
We also know from Chapter 1 that Func produces a value and Action produces nothing. Methods have the same split: a method with a return type like int or bool produces a value, and a method with return type void produces nothing. We develop this with concrete examples once we give our objects behavior.
Linked Lists
We now have a new kind of type. Classes give us reference semantics, constructors, and access control. The rest of this section uses those tools to build a new kind of collection.
In Chapter 3, we chose the size of every array at creation, and that size could never change. At the time, this was a minor detail. Now it becomes a problem.
Suppose we have an array of scores and want to add one more:
int[] scores = {85, 92, 78};
// We want to add 90, but there's no room.There is no scores.Add(90). The array has three slots, all full. To fit a fourth value, we must create a new, larger array and copy everything over:
int[] scores = {85, 92, 78};
int[] bigger = new int[scores.Length + 1];
for (int i = 0; i < scores.Length; i++)
{
bigger[i] = scores[i];
}
bigger[scores.Length] = 90;
scores = bigger;That is seven lines of code to add one value, and it copies every existing element in the process. For an array of 1,000 elements, adding one means copying all 1,000.
Inserting at the front is worse. Suppose we want to put 90 at the beginning:
int[] scores = {85, 92, 78};
int[] bigger = new int[scores.Length + 1];
bigger[0] = 90;
for (int i = 0; i < scores.Length; i++)
{
bigger[i + 1] = scores[i];
}
scores = bigger;Create a new array, place the new value at index 0, copy every existing element into the next position, then rebind scores to the new array. For 1,000 elements, that is 1,000 copies plus the overhead of allocating a new array.
These problems share a root cause. Arrays store elements in contiguous memory. That contiguous layout is what makes index-based access fast: shift by i and you are at the element. But it also means adding or removing elements requires rearranging the entire structure. Every element after the insertion point must be copied to a new position, or an entirely new array must be allocated and filled.
What if the elements did not need to sit next to each other in memory? What if, instead of relying on position, each element simply knew where the next one was?
Picture a chain where each link holds a value and a reference to the next link:
┌──────┐ ┌──────┐ ┌──────┐
│ 85 │───>│ 92 │───>│ 78 │───> (end)
└──────┘ └──────┘ └──────┘
To add 90 at the front, create a new link and point it at the old first link:
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ 90 │───>│ 85 │───>│ 92 │───>│ 78 │───> (end)
└──────┘ └──────┘ └──────┘ └──────┘
The existing chain is untouched. No element moved. We created one new link, pointed it at the old first link, and the insert was done.
Building a Node
To build this chain, we need a type that bundles a value with a reference to the next item. A struct cannot do this. A struct is a value type, so a Node struct containing a Node field would mean every node contains a full copy of the next node, which contains a full copy of the next one, and so on. The size is infinite. A struct cannot contain a field of its own type.
A class can. Because classes are reference types, a LinkedListNode field holds a reference to another node, not a copy of one:
class LinkedListNode
{
public int Value;
public LinkedListNode? Next;
public LinkedListNode(int value)
{
this.Value = value;
this.Next = null;
}
}Description: “LinkedListNode is a class with two fields: an integer Value and a nullable reference to the next node. Its constructor takes an integer, stores it in Value, and sets Next to null.”
Token by token for the class definition:
class: we are defining a new reference typeLinkedListNode: the name of the typepublic int Value;: a public integer field named Valuepublic LinkedListNode? Next;: a public nullable LinkedListNode field named Next
The ? after LinkedListNode means this field is allowed to hold null. null means “no object.” A reference variable or field holding null does not point to anything. The last node in a chain has nothing after it, so its Next field holds null.
We saw earlier that the default value for string variables is null, and that arrays of reference types start with null in every slot. The same idea applies here. When a node’s Next field is null, there is no next node, and the chain ends. Code that walks a linked list follows Next references from node to node, and when it reaches null, the traversal is finished.
Attempting to access a field through null produces an error:
LinkedListNode last = new LinkedListNode(99);
// last.Next is null
Console.WriteLine(last.Next.Value); // Error: NullReferenceExceptionlast.Next evaluates to null. Null does not refer to any object, so there is no Value field to read. The program crashes. Any code that follows Next references must check for null before proceeding.
Try it yourself.
Describe this class in English:
class Song
{
public string Title;
public Song? NextSong;
public Song(string title)
{
this.Title = title;
this.NextSong = null;
}
}Write your answer before revealing ours.
Reveal answer
“Song is a class with two fields: a string Title and a nullable reference to the next Song. Its constructor takes a string title, stores it in Title, and sets NextSong to null.”
If your answer differed, note what you missed before continuing.
Try it yourself.
Write a class definition with a constructor from this description:
Define a class named Task with a public string field Description and a public nullable Task field NextTask. Define a constructor that takes a string description, binds it to the Description field, and binds null to NextTask.
Reveal answer
class Task
{
public string Description;
public Task? NextTask;
public Task(string description)
{
this.Description = description;
this.NextTask = null;
}
}Self-correct against the model above.
Building a Chain
With our LinkedListNode class and constructor, we can build the three-node chain from the diagrams above:
LinkedListNode a = new LinkedListNode(85);
LinkedListNode b = new LinkedListNode(92);
LinkedListNode c = new LinkedListNode(78);
a.Next = b;
b.Next = c;After the three constructor calls, we have three independent nodes. Each has a Value and a Next field holding null:
a b c
┌──────┐ ┌──────┐ ┌──────┐
│ ref ──>┌──────────┐ │ ref ──>┌──────────┐ │ ref ──>┌──────────┐
└──────┘ │ V: 85 │ └──────┘ │ V: 92 │ └──────┘ │ V: 78 │
│ N: null │ │ N: null │ │ N: null │
└──────────┘ └──────────┘ └──────────┘
After a.Next = b;, the Next field of a’s object holds a reference to b’s object:
a b c
┌──────┐ ┌──────┐ ┌──────┐
│ ref ──>┌──────────┐ │ ref ──>┌──────────┐ │ ref ──>┌──────────┐
└──────┘ │ V: 85 │ └──────┘ │ V: 92 │ └──────┘ │ V: 78 │
│ N: ref ─────────> │ N: null │ │ N: null │
└──────────┘ └──────────┘ └──────────┘
After b.Next = c;, node b’s Next points to node c:
a b c
┌──────┐ ┌──────┐ ┌──────┐
│ ref ──>┌──────────┐ │ ref ──>┌──────────┐ │ ref ──>┌──────────┐
└──────┘ │ V: 85 │ └──────┘ │ V: 92 │ └──────┘ │ V: 78 │
│ N: ref ─────────> │ N: ref ─────────> │ N: null │
└──────────┘ └──────────┘ └──────────┘
The three nodes form a chain. Starting from a, we reach b through a.Next and c through a.Next.Next. The last node’s Next is null, marking the end.
Translation for a.Next = b;: “Link the reference b to a’s Next field.”
After this line, a.Next and b point to the same node object. Storing a reference into a field works the same way as storing a reference into a variable: both sides end up referring to the same object.
Now consider the problem we started with: adding a value at the front. With an array, this required allocating a new array and copying every element. With our chain:
LinkedListNode newFront = new LinkedListNode(90);
newFront.Next = a;
a = newFront;Description: “Create a new node with value 90, link it to the current front of the chain, then update a to point to the new front.”
Three lines, and nothing in the existing chain moved. For a chain of 1,000 nodes, adding at the front still takes three lines and touches zero existing nodes.
This structure is a linked list: an ordered collection of nodes where each node holds a value and a reference to the next node.
A node is one element of a linked list, containing a value and a reference to the next node (or null).
The variables a, b, and c are reference variables. The Next fields are also references, and those references are what create the links between nodes.
Try it yourself.
Draw the memory diagram for this code:
LinkedListNode x = new LinkedListNode(5);
LinkedListNode y = new LinkedListNode(15);
x.Next = y;How many objects exist in memory? How many reference variables are there? What does x.Next.Value evaluate to?
Reveal answer
Two objects in memory (the node with value 5 and the node with value 15). Two reference variables (x and y).
x y
┌──────┐ ┌──────┐
│ ref ──>┌──────────┐ │ ref ──>┌──────────┐
└──────┘ │ V: 5 │ └──────┘ │ V: 15 │
│ N: ref ──────────────>│ N: null │
└──────────┘ └──────────┘
x.Next.Value evaluates to 15. Follow the references: x refers to the first node, x.Next refers to the second node, x.Next.Value is the Value field of the second node.
If your answer differed, note what you missed before continuing.
Try it yourself.
Write code that creates a three-node linked list holding the values 10, 20, and 30 in order. Use variables named first, second, and third. Wire them into a chain.
Reveal answer
LinkedListNode first = new LinkedListNode(10);
LinkedListNode second = new LinkedListNode(20);
LinkedListNode third = new LinkedListNode(30);
first.Next = second;
second.Next = third;Self-correct against the model above.
Try it yourself.
What does this code do? Trace the state and draw the final memory diagram.
LinkedListNode p = new LinkedListNode(1);
LinkedListNode q = new LinkedListNode(2);
LinkedListNode r = new LinkedListNode(3);
p.Next = q;
q.Next = r;
r.Next = p;Reveal answer
The first five lines build a three-node chain: p then q then r. The sixth line, r.Next = p, stores a reference to p’s node in r’s Next field. This creates a cycle: following Next from any node eventually leads back to the same node.
┌──────────┐ ┌──────────┐ ┌──────────┐
│ V: 1 │────>│ V: 2 │────>│ V: 3 │
│ N: ref │ │ N: ref │ │ N: ref │
└──────────┘ └──────────┘ └──────────┘
^ │
└──────────────────────────────────┘
There is no null in the chain. Any traversal that follows Next without a stopping condition will loop forever. This is one of the things that can go wrong when outside code has direct access to the Next fields. We return to this problem when we discuss protecting data.
Compare your answer and note what you missed.
Copying Linked List Nodes
Reference semantics apply to linked list nodes the same way they apply to any class object. Copying a node variable copies the reference, not the node:
LinkedListNode a = new LinkedListNode(10);
LinkedListNode b = a;
b.Value = 99;
Console.WriteLine(a.Value); // displays 99Both a and b refer to the same node. Changing the Value through b is visible through a.
Try it yourself.
What does this code display?
LinkedListNode x = new LinkedListNode(5);
LinkedListNode y = new LinkedListNode(10);
x.Next = y;
LinkedListNode z = x;
z.Value = 100;
Console.WriteLine(x.Value);
Console.WriteLine(x.Next.Value);Reveal answer
Output:
100
10
z = x copies the reference, so z and x point to the same node. z.Value = 100 changes that node’s Value to 100, and x.Value reads the same field, producing 100.
x.Next still refers to the node y refers to, whose Value is 10. Assigning z did not affect the Next field or the second node.
If your answer differed, trace through each line and identify where your reasoning went wrong.
Try it yourself.
What does this code display?
LinkedListNode a = new LinkedListNode(1);
LinkedListNode b = new LinkedListNode(2);
a.Next = b;
LinkedListNode c = a.Next;
c.Value = 50;
Console.WriteLine(b.Value);Reveal answer
Output:
50
a.Next holds a reference to the same object that b refers to. Assigning a.Next to c copies that reference, so c, b, and a.Next all refer to the same node. c.Value = 50 changes that node’s Value. b.Value reads the same field, producing 50.
Compare your answer and note what you missed.
Arrays vs Linked Lists
We started with the cost of adding to an array: allocate a new array, copy every element, then discard the old one. Linked lists avoid that cost entirely. But linked lists give up something arrays have: direct access by index.
To reach element 500 in an array, shift by 500 from the start. That takes one step regardless of the array’s size.
To reach node 500 in a linked list, follow 500 Next references from the first node, one at a time. That is 500 steps.
Neither structure is always better. Arrays are fast when you need to access elements by position. Linked lists are fast when you need to add or remove elements without moving the rest. Choosing between them depends on what operations the program needs most.
The linked list gives us a reason to learn every tool in this chapter: classes to define nodes, constructors to build them, methods to traverse them, and encapsulation to protect their structure. Those tools apply to any class we build in the future, not just linked lists.
Review
Before continuing, test yourself on what you’ve learned. 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 class?
- What is a constructor?
- What does
thisrefer to? - What is a member?
- What does public mean for a member?
- What does private mean for a member?
- What is a linked list?
- What is a node?
- What does null mean?
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.
-
class Counter { public int Count; } -
Rectangle r = new Rectangle(4, 6); -
LinkedListNode n = new LinkedListNode(7); -
n.Next = other; -
LinkedListNode copy = original;
public LinkedListNode(int value)
{
this.Value = value;
this.Next = null;
}Check your translations against the patterns shown earlier in this section.
Part 3: Writing Code
Write C# code for each description.
-
Define a class named Waypoint with a public double field Latitude, a public double field Longitude, and a public nullable Waypoint field NextWaypoint. Write a constructor that takes two doubles (lat and lon), binds them to the corresponding fields, and binds null to NextWaypoint.
-
Create a Waypoint object with latitude 33.47 and longitude -82.01, and store a reference to it in a variable named start.
-
Create a second Waypoint with latitude 34.05 and longitude -83.99, store it in destination, and wire start’s NextWaypoint field to point to destination.
-
Define a class named Student with a public string field Name, a public integer field Score, and a constructor that takes a string name and an integer score and binds them to the corresponding fields.
Part 4: Memory Diagrams
Draw the memory diagram for this code. Show reference variables, objects, and all references between them.
LinkedListNode a = new LinkedListNode(10);
LinkedListNode b = new LinkedListNode(20);
LinkedListNode c = new LinkedListNode(30);
a.Next = b;
b.Next = c;
LinkedListNode d = b;How many objects exist in memory? How many reference variables are there? Do any variables share an object? If so, which ones?
Part 5: Predict the State
What does this code display?
LinkedListNode p = new LinkedListNode(1);
LinkedListNode q = new LinkedListNode(2);
p.Next = q;
LinkedListNode r = p;
r.Next = new LinkedListNode(3);
Console.WriteLine(p.Next.Value);
Console.WriteLine(q.Value);Trace through each line. Pay attention to which variables share objects and which Next references change.
Part 6: Struct vs Class
Explain why a linked list node must be a class (reference type) rather than a struct (value type). Your explanation should address both the self-referencing field and the sharing behavior that a linked list requires.
Part 7: The Class Boundary
Consider this class:
class Counter
{
private int count;
public Counter(int start)
{
this.count = start;
}
}For each line of outside code, determine whether it compiles or produces an error. Explain why.
Counter c = new Counter(0);
Console.WriteLine(c.count);
c.count = 10;Part 8: Arrays vs Linked Lists
A program stores a list of 10,000 student IDs. The program frequently needs to add new IDs at the front and remove IDs from the front, but rarely needs to look up an ID by position. Would an array or a linked list be a better fit? Explain your reasoning in terms of the operations involved.
You now know how to define your own reference types. You can write class definitions, constructors, and create objects. You can draw memory diagrams that distinguish reference variables from the objects they refer to. You understand the boundary between inside and outside a class. And you have used those tools to build a new kind of collection: a linked list, where adding elements requires no copying and no rearranging.
Next, we give these objects behavior.