Build self-referencing type aliases in TypeScript
We usually think of types as something that can define a single layer of an object: with an interface we normally specify a list of a few properties and their respective types. If any one of those properties is another object we must refer again to its type. This is a finite process, as eventually we will get to a flat object, that doesn’t reference any other objects. Trees and Linked Lists are dynamic data structures, that can have infinitely many levels of depth. A type alias in TypeScript can use generics and refer to itself - this can be used to create these potentially infinitely long data structures. We will also explore using Linked Lists for building a Redux time travelling debugger.
Instructor: [00:01] In TypeScript, we can declare types that reference themselves. We can build a node of a binary tree where each node has a value. It also has a left and a right property which are themselves reference to other tree nodes.
[00:14] We can also build a node of a linked list, where again each node has a value, but also reference to the next node in the list. While most types have a finite structure, these types can potentially grow infinitely.
[00:28] This will pass compilation just fine because linked lists can potentially grow to infinite sizes. How can we apply this? Redux is great because it offers us the ability to track everything happening in our app with actions.
[00:42] These actions are usually going to have a shape like this. As we're using the app, these actions, as they're happening, will start to stack up. They're going to start creating new state snapshots each time.
[00:54] Let's say we want to build a rewind button that allows us to travel back in time through our app and explore the different states it was in before some of the actions happened. To do that, we'd need each one of these actions to hold a reference to the previous action.
[01:10] A linked list sounds like a suitable data structure for that, as we want to be moving back and forth between the items without unwinding any potential stack. We might also want to experiment adding new actions between other actions. Linked lists are very good for that.
[01:26] I'll start by creating an interface for each node. I'll store both the current value, which is going to be the action itself, the next node, which is going to be a reference to the action node that follows this one, and the previous node, which is useful for going back in time between actions.
[01:46] I already have these two mock actions. I'll just create the corresponding nodes for them. The previous and next values for the first node will initially be null because nothing has happened yet.
[01:59] The previous value of the second action node will be the first action node. The next one will be null because this is the latest action in our app. Then I'll go back and mark the next value of the first node as the second node.
[02:13] I'm just giving examples here. Usually, the creation of these nodes would probably be abstracted away into the Redux store implementation, should this actually get built.
[02:24] This is interesting. I have access to the node for the first action. I can just keep going forward in time by looking at the next values. Eventually, I can extract the proper action from it.
[02:35] This will pass TypeScript validation because as far as it's concerned, we're still following the linked list interface. This is obviously not very safe, as at some point, in this case right here, the value will be undefined.
[02:47] Any time I try to call next after it, we're going to get an error, as we've reached the end of the list. We can use a while loop to build a safer traversal mechanism that stops when it reaches an undefined previous value.
Oh! I think you might have strict or strictNullChecks enabled in your tsconfig.json - https://www.typescriptlang.org/tsconfig/#strictNullChecks
In which case you are 100% correct, your second example would be appropriate for stricter type checks. Thanks for pointing that out!
Yup, that was it I had strict set.
When I write
I get the error
Type 'null' is not assignable to type 'LinkedNode<Action>'.for next and prev. That's what I thought would happen, so I'm wondering why your IDE isn't throwing an error. Shouldn't it be: