TypeScript JavaScript

Create a linked list with TypeScript

A linked list is a data structure, in which each element contains a value and has a reference to the next element in the list. The value of the element can be practically anything, from a string or a number till a complex object and these values can either be sorted or unsorted and unique or duplicated.

The first element of the linked list is called head. The main advantage of a linked list is that we can quickly insert or remove data, without having to reallocate the entire structure, however, if we want to get an element we have to traverse the linked list, starting from the head, till we find the value we search for. For this reason, a linked list has a linear access time.

In this article we are going to create a linked list and also its most important actions which are the insertion (three different types) and the deletion.

First we create a class for the linked list data structure, which contains one reference to the head element of the list:

	class LinkedList {
		private head: LinkedListItem;
		constructor(item: LinkedListItem) {
			this.head = item;
		}
	}

We now have to define a second class which provides us with objects for the elements of the linked list. The class contains two properties, one for the value of the element and one for the reference to the next element:

	class LinkedListItem {
		value: any;
		next: LinkedListItem;

		constructor(val) {
			this.value = val;
			this.next = null;
		}
	}

Now we can start adding the functionality into the LinkedList class. The first function we add is the insert function which inserts a new element in a specific position inside the linked list. The algorithm works as follow:

    // Adds the element at a specific position inside the linked list
    insert(val, previousItem: LinkedListItem) {
        let newItem: LinkedListItem = new LinkedListItem(val);
        let currentItem: LinkedListItem = this.head;

        if (!currentItem) {
            this.head = newItem;
        } else {
            while (true) {
                if (currentItem === previousItem) {
                    let tempNextItem = previousItem.next;
                    currentItem.next = newItem;
                    newItem.next = tempNextItem;
                    break;
                } else {
                    currentItem = currentItem.next;
                }
            }
        }
    }

The next function appends a new element at the end of the linked list. In that case, we have to parse the complete linked list, before we add the new element:

    // Adds the element at the end of the linked list
    append(val) {
        let currentItem: LinkedListItem = this.head;
        let newItem = new LinkedListItem(val);

        if (!currentItem) {
            this.head = newItem;
        } else {
            while (true) {
                if (currentItem.next) {
                    currentItem = currentItem.next;
                } else {
                    currentItem.next = newItem;
                    break;
                }
            }
        }
    }

The next function prepends a new element at the beginning of the linked list, so we can say that it is a push action. This action is very fast since we do not have to traverse the linked list:

    // Add the element at the beginning of the linked list
    prepend(val) {
        let newItem = new LinkedListItem(val);
        let oldHead = this.head;

        this.head = newItem;
        newItem.next = oldHead;
    }

We now want to add a remove function which removes an element from the linked list. Here how the algorithm works:

    delete(val) {
        var currentItem = this.head;

        if (!currentItem) {
            return;
        }

        if (currentItem.value === val) {
            this.head = currentItem.next;
        } else {
            var previous = null;

            while (true) {
                if (currentItem.value === val) {
                    if (currentItem.next) { // special case for last element
                        previous.next = currentItem.next;
                    } else {
                        previous.next = null;
                    }
                    currentItem = null; // avoid memory leaks
                    break;
                } else {
                    previous = currentItem;
                    currentItem = currentItem.next;
                }
            }
        }
    }

The last function we add to the LinkedList class is a getter for seeing all the values of the linked list starting from the head element till the last one. For that we use an array:

    showInArray() {
        let arr = [];
        let currentItem = this.head;

        while (true) {
            arr.push(currentItem.value);

            if (currentItem.next) {
                currentItem = currentItem.next;
            } else {
                break;
            }
        }

        return arr;
    }

I hope you enjoyed the article as much as I did writing it :). Drop a line if you have any comment. You can find the code in my GitHub account.

comments powered by Disqus