Implement a singly linked list in TypeScript
In a singly linked list each node in the list stores the contents of the node and a reference (or pointer in some languages) to the next node in the list. It is one of the simplest way to store a collection of items.
In this lesson we cover how to create a linked list data structure and how to use its strengths to implement an O(1) FIFO queue.
[00:00] A link list is simply a list of nodes. Each node has a value and a link to the next node in the list till we arrive at the end of list where next will be undefined.
[00:13] The link list data structure itself simply maintains the head node. The trick to writing a link list and really any data structure with a concept of a node -- for example, a binary tree -- is to first define a node.
[00:30] Let's jump into TypeScript and define what we mean by a node. We go ahead and create a generic interface for the link list node. Each node will have a value and an optional pointer to the next node which will be, again, a link list node.
[00:49] Now let's go ahead and model the link list as a generic class for values of type t. All that we really need to do is to store a reference to the head. Although this class can be considered complete, it puts the burden of doing safe manipulation of next pointers on the users of this class.
[01:12] We can easily provide our users a utility add method that lets them add an item to the link list. To make it easy for us to add an item in o of fun run time, we should track the current tail of the link list, so we go ahead and add a member for that.
[01:32] Now we go ahead and create the add method. It simply takes value of type t.
[01:38] We go ahead and create a new link list node with the given value. This node will be our new tail. If this is the first node that we are seeing, we will also initialize the head.
[01:53] Additionally, if we already have the tame load, it's next pointer should be updated to this new node. Finally we set this new node as our current tail. Great, so now our users can easily and safely add items to the link list.
[02:10] As an added convenience to our users, we can also provide a method that generates an iterator of all the values in the list. You simply start at the head which illustrates a good reason to have a reference to the head.
[02:24] Within a value, as long as we have a current item, we simply yield its value. Finally, we update our current to the next value, which may or may not be there.
[02:34] Now let's go ahead and demonstrate this function in action. We go ahead and create a link list of numbers. We add a few numbers to the list.
[02:48] Next we simply iterate over the values from the link list and log them out. Now if you go ahead and demo the file, you can see that the values returned from the list match what we added.
[03:06] As a final exercise, we can easily add a first in, first out LINQ operation to the link list which also operates in o
[03:14] Fun. We go ahead and add a method with the class. The method will simply return either a value or undefined if you're out of values.
[03:28] We will only return a value while we still have a valid head reference. We grab the value from our head, update our head to be the next value. If our new head is undefined, it means we will be out of items after this DQ operation and should update our data to match.
[03:49] Finally, with our maintenance of head and tail out of the way, we simply return the retrieved value. This example demonstrates the real beauty of a link list. Any operation that only requires a constant number of next reference manipulations can be implemented in such a way to have o fun run time.