Implement a singly linked list in TypeScript

Share this video with your friends

Social Share Links

Send Tweet
Published 7 years ago
Updated 3 years ago

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.

~ just now

Member comments are a way for members to communicate, interact, and ask questions about a lesson.

The instructor or someone from the community might respond to your question Here are a few basic guidelines to commenting on

Be on-Topic

Comments are for discussing a lesson. If you're having a general issue with the website functionality, please contact us at

Avoid meta-discussion

  • This was great!
  • This was horrible!
  • I didn't like this because it didn't match my skill level.
  • +1 It will likely be deleted as spam.

Code Problems?

Should be accompanied by code! Codesandbox or Stackblitz provide a way to share code and discuss it in context

Details and Context

Vague question? Vague answer. Any details and context you can provide will lure more interesting answers!

Markdown supported.
Become a member to join the discussionEnroll Today