Typescript Generics Data Structures

Author: Grant Ralls [email protected] https://www.grantralls.net

Foreword

I created this package for the value of practice. I wanted my own implementation of a Linked List using Typescript with Generics to use in future home-projects. Consider this a work in progress, not ready for production.

Compatibility

This is designed to be compatible with ES2017. This works best (at the time of writing) with Node 10+.

Example

Node 10.8.x

const LinkedList = require("linkedlist").LinkedList;

const newList = new LinkedList();

newList.append(3);
newList.contains(3); // true

Typescript

import { LinkedList } from 'linkedlist';

// number can be changed to another type.
const newList = new LinkedList<number>();

newList.append(4);
newList.contains(4); // true

API (Using Typescript)

Linked List

append(value: Type) returns void

The append function adds value to the end of the list.

Usage:

const newList = new LinkedList<number>();
newList.append(3);

prepend(value: Type) returns void

The prepend function adds value to the beginning of the list.

Usage:

const newList = new LinkedList<number>();
newList.prepend(3);

copy() returns LinkedList

The copy function deeply copies the list it is being run on.

Usage:

const newList = new LinkedList<number>();
const newCopy = newList.copy();

contains(value: type) returns boolean

The contains function searches iteratively for the first instance of value in the list.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);

newList.contains(2); // true
newList.contains(5); // false

getHeadValue() returns Type of List

The getHeadValue function returns the data of the head (far-left-end) node of the list. The return type is consistent with the type of the List.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);

newList.getHeadValue(); // 1

getTailValue() returns type of List

The getTailValue function returns the data of the tail (far-right-end) node of the list. The return type is consistent with the type of the List.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);

newList.getTailValue(); // 2

getSize() returns number

The size function returns the number of nodes in the list.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);

newList.getSize(); // 2

removeHead() returns void

The removeHead function removes the current head node from the list. The new head is determined as the next node from the previous head.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);
newList.removeHead();

newList.getHeadValue(); // 2

removeTail() returns void

The removeTail function removes the current tail node from the list. The new tail is determined as the previous node from the previous tail.
Note: The runtime for this function is O(n). This list is not doubly linked, therefore it needs to be fully iterated over to find the second to last node.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);
newList.removeTail();

newList.getTailValue(); // 1

removeAtIndex(indexOfNodeToRemove: number) returns void

The removeAtIndex function removes the node at the specified index. The two adjacent nodes are then chained together. Note: The runtime for this function is O(n). This list is not doubly linked, therefore it needs to be iterated over to find the node to remove.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);
newList.append(3);
newList.removeAtIndex(1);

// before removeAtIndex newList: 1 -> 2 -> 3
// after removeAtIndex newList: 1 -> 3

newList.getHeadValue(); // 1
newList.getTailValue(); // 3
newList.getSize(); // 2

getValueAtIndex(desiredIndex: number) returns type of List

The getValueAtIndex function returns the data of the node at the index specified. Note: The runtime for this function is O(n). This list is not doubly linked, therefore it needs to be iterated over to find the node to retrieve.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);
newList.append(3);

const result = newList.getValueAtIndex(1);

console.log(result); // 2

traverse() returns IterableIterator

The traverse function is a generator function that returns an Iterable Iterator. See Javascript Generator Docs for more info.

Usage:

const newList = new LinkedList<number>();
newList.append(1);
newList.append(2);

const listIterator = newList.traverse();

for (const value in listIterator) {
    console.log(value);
}

// Console: 1 2

Queue

push(value: Type) returns void

The push function adds value to the back of the queue.

Usage:

const newQueue = new Queue<number>();
newList.push(1);

pop(value: Type) returns T

The pop function removes the node at the front of the queue and returns the data that node was holding.

Usage:

const newQueue = new Queue<number>();
newList.push(1);

console.log(newList.pop()); // 1

front() returns T

The front function returns the data at the front of the queue.

Usage:

const newQueue = new Queue<number>();
newQueue.push(1);

console.log(newQueue.front()); // 1

back() returns T

The back function returns the data at the back of the queue.

Usage:

const newQueue = new Queue<number>();
newQueue.push(1);
newQueue.push(2);

console.log(newQueue.back()); // 2

size() returns T

The size function returns the number of nodes in the queue.

Usage:

const newQueue = new Queue<number>();
newQueue.push(1);
newQueue.push(2);
newQueue.push(2);

console.log(newQueue.size()); // 3

empty() returns boolean

The empty function returns true if the queue has no nodes associated with it.

Usage:

const newQueue = new Queue<number>();

console.log(newQueue.empty()); // true

newQueue.push(1);

console.log(newQueue.empty()); // false