19 Mutable Singly Linked Lists (Part 1)

Let's define mutable singly-linked lists in OCaml.

type 'a node = {
	value: 'a;
	mutable next: 'a node;
}

type 'a node = { value : 'a; mutable next : 'a node; }

Okay, that seems like a good place to start, but what if we need to end our list? The last element of our list will need to have a next field. OCaml provides options for this, so let's make the next field an option. Let's also add an abstraction function.

(** An ['a node] is a node of a mutable singly-linked
	list. It contains a value of type ['a], and
	optionally, a pointer to the next node.*)
type 'a node = {
	value: 'a;
	mutable next: 'a node option;
}

type 'a node = { value : 'a; mutable next : 'a node option; }

Now let's create a type for liked lists (not just the node). This can hold information like the size of the list.

(** An ['a mlist] is a mutable singly-linked list with
	elements of type ['a]. *)
type 'a mlist = {
	mutable first: 'a node option;
}

type 'a mlist = { mutable first : 'a node option; }

Now let's write some code to create lists. We'll first implement singleton lists, lists of a single value.

(** [create_node v] is a node containing the value [v]
	with no link to another node. *)
let create_node v = {
	value = v;
	next = None;
}

(** [singleton v] is a singly-linked list containing
	exactly one value, [v]. *)
let singleton v = {
	first = Some (create_node v)
}

val create_node : 'a -> 'a node = <fun>

val singleton : 'a -> 'a mlist = <fun>

Now let's make a list!

singleton 3110;;

- : int mlist = {first = Some {value = 3110; next = None}}