Skip to content

Instantly share code, notes, and snippets.

@ZachSaucier

ZachSaucier/doubly-linked-list.ts

Last active May 6, 2023 18:58
Show Gist options
  • Save ZachSaucier/d88d6699f9f21ef63dd3af0b1fd1f10d to your computer and use it in GitHub Desktop.
Save ZachSaucier/d88d6699f9f21ef63dd3af0b1fd1f10d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ZachSaucier revised this gist May 6, 2023. 1 changed file with 7 additions and 0 deletions.
    7 changes: 7 additions & 0 deletions doubly-linked-list.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -287,4 +287,11 @@ export class DoublyLinkedList<T> {
    tmp = tmp.next;
    }
    }

    // Removes all nodes from the linked list, reseting it
    public clear() {
    this.head = undefined;
    this.tail = undefined;
    this.size = 0;
    }
    }
  2. ZachSaucier revised this gist May 6, 2023. 1 changed file with 11 additions and 0 deletions.
    11 changes: 11 additions & 0 deletions doubly-linked-list.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -33,6 +33,17 @@ export class DoublyLinkedList<T> {
    public isEmpty(): boolean {
    return this.size === 0;
    }

    // Returns an array of all of the linked list's values
    public toArray(): T[] {
    const arr: T[] = [];
    let tmp = this.head;
    while (tmp != undefined) {
    arr.push(tmp.value);
    tmp = tmp.next;
    }
    return arr;
    }

    // Returns the index of the node of the linked list with the given value, -1 if not found
    public indexOf(value: T) {
  3. ZachSaucier revised this gist May 6, 2023. 1 changed file with 4 additions and 0 deletions.
    4 changes: 4 additions & 0 deletions usage.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,4 @@
    // Specify the type of value when constructing the linked list
    const ll = new DoublyLinkedList<string>();
    ll.insertAtTail("0")
    // ...
  4. ZachSaucier created this gist May 6, 2023.
    279 changes: 279 additions & 0 deletions doubly-linked-list.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,279 @@
    // Note: This doubly linked list implementation is meant to cover most any use
    // case of doubly linked lists. You likely don't need all of the functions
    // included for your use case.

    class DoublyLinkedListNode<T> {
    public value: T;
    public next?: DoublyLinkedListNode<T>;
    public prev?: DoublyLinkedListNode<T>;

    constructor(value: T) {
    this.value = value;
    }
    }

    export class DoublyLinkedList<T> {
    // The first node of the linked list
    private head?: DoublyLinkedListNode<T>;
    // The last node of the linked list
    private tail?: DoublyLinkedListNode<T>;
    private size: number = 0;

    constructor() { }

    //////////////////////////////////////////////
    // Info (including getting value) functions //
    //////////////////////////////////////////////

    public length(): number {
    return this.size;
    }

    // Returns whether or not the linked list has at least 1 node
    public isEmpty(): boolean {
    return this.size === 0;
    }

    // Returns the index of the node of the linked list with the given value, -1 if not found
    public indexOf(value: T) {
    if (this.isEmpty()) {
    return -1;
    }
    let index = 0;
    let tmp = this.head;
    while (tmp != undefined) {
    if (tmp.value === value) {
    return index;
    }
    tmp = tmp.next;
    index++;
    }
    return -1;
    }

    // Returns the value of the first node in the linked list
    public getHead(): T | undefined {
    if (this.head != undefined) {
    return this.head.value;
    }
    return undefined;
    }

    // Returns the value of the last node of the linked list
    public getTail(): T | undefined {
    if (this.tail != undefined) {
    return this.tail.value;
    }
    return undefined;
    }

    // Returns the value of the node of the linked list at the given index
    public getByIndex(index: number): T | undefined {
    if (index < 0 || index > this.size || this.isEmpty()) {
    return undefined;
    }

    if (index > this.size / 2) {
    let i = (this.size - 1) - index;
    let tmp = this.tail!;
    while (i > 0) {
    tmp = tmp.prev!;
    i--;
    }
    return tmp.value;
    }
    else {
    let tmp = this.head!;
    for (let i = 0; i < index; i++) {
    tmp = tmp.next!;
    }
    return tmp.value;
    }
    }

    /////////////////////////
    // Inserting functions //
    /////////////////////////

    // A helper function to remove a given node from the linked list
    private insertNonEndNodeAtIndex(value: T, index: number) {
    const newNode = new DoublyLinkedListNode(value);
    if (this.isEmpty()) {
    this.head = newNode;
    this.tail = newNode;
    this.size++;
    }
    else {
    if (index > this.size / 2) {
    let i = this.size - index;
    let tmp = this.tail!;
    while (i > 0) {
    tmp = tmp.prev!;
    i--;
    }
    newNode.next = tmp.next;
    newNode.prev = tmp;
    tmp.next = newNode;
    }
    else {
    let tmp = this.head!;
    for (let i = 0; i < index - 1; i++) {
    tmp = tmp.next!;
    }
    newNode.next = tmp.next;
    newNode.prev = tmp;
    tmp.next = newNode;
    }
    }
    }

    // Inserts a new node with the given value at the index provided
    // If the index provided is not reachable, it will error
    public insertAtIndex(value: T, index: number) {
    if (index < 0 || index > this.size) {
    throw RangeError(`Index ${index} is out of range of linked list with range ${this.size}`);
    }

    if (index === 0) {
    this.insertAtHead(value);
    } else if (index === this.size) {
    this.insertAtTail(value);
    } else {
    this.insertNonEndNodeAtIndex(value, index);
    }
    }

    // Adds a new node with the given value to the start of the linked list
    public insertAtHead(value: T) {
    const newNode = new DoublyLinkedListNode(value);
    if (this.isEmpty()) {
    this.head = newNode;
    this.tail = newNode;
    this.size++;
    }
    else {
    newNode.next = this.head;
    newNode.prev = undefined;

    this.head!.prev = newNode;

    this.head = newNode;
    this.size++;
    }
    }

    // Adds a new node at the end of the linked list
    public insertAtTail(value: T) {
    const newNode = new DoublyLinkedListNode(value);
    if (this.isEmpty()) {
    this.head = newNode;
    this.tail = newNode;
    this.size++;
    return;
    }
    else {
    newNode.next = undefined;
    newNode.prev = this.tail;

    this.tail!.next = newNode;

    this.tail = newNode;
    this.size++;
    }
    }

    ////////////////////////
    // Removing functions //
    ////////////////////////

    // A helper function to remove a given node from the linked list
    private removeNode(node: DoublyLinkedListNode<T>) {
    if (node.prev) {
    if (node.next) {
    node.prev.next = node.next;
    } else {
    this.tail = node.prev;
    node.prev.next = undefined;
    }
    } else {
    if (node.next) {
    this.head = node.next;
    node.next.prev = undefined;
    } else {
    this.head = undefined;
    this.tail = undefined;
    }
    }
    }

    // Removes the node of the linked list at the provided index
    public remove(index: number) {
    if (index < 0 || this.size < index) {
    throw new RangeError("Index out of range.");
    }

    if (index > this.size / 2) {
    let i = (this.size - 1) - index;
    let tmp = this.tail!;
    while (i > 0) {
    tmp = tmp.prev!;
    i--;
    }
    this.removeNode(tmp);
    }
    else {
    let tmp = this.head!;
    for (let i = 0; i < index; i++) {
    tmp = tmp.next!;
    }
    this.removeNode(tmp);
    }
    }

    // Removes the first node in the linked list
    public removeHead() {
    if (this.isEmpty()) {
    return;
    }
    this.size--;
    if (this.size == 0) {
    this.head = undefined;
    this.tail = undefined;
    }
    else {
    this.head = this.head!.next;
    this.head!.prev = undefined;
    }
    }

    // Removes the last node in the linked list
    public removeTail() {
    if (this.isEmpty()) {
    return;
    }
    this.size--;
    if (this.size == 0) {
    this.head = undefined;
    this.tail = undefined;
    }
    else {
    this.tail = this.tail!.prev;
    this.tail!.next = undefined;
    }
    }

    // Removes the first node with the given value
    public removeByValue(value: T) {
    if (this.isEmpty()) {
    return;
    }
    let tmp = this.head;
    while (tmp != undefined) {
    if (tmp.value === value) {
    this.removeNode(tmp);
    return;
    }
    tmp = tmp.next;
    }
    }
    }