123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206
import { DoublyLinkedList } from "./DoublyLinkedList.ts";
// deno-lint-ignore no-explicit-anyinterface MyLinkedList<T = any> {    get(index: number): T | number;
    addAtHead(val: T): void;
    addAtTail(val: T): void;
    addAtIndex(index: number, val: T): void;
    deleteAtIndex(index: number): void;    length(): number;    clear(): void;    deleteAtHead(): void;    deleteAtTail(): void;}// deno-lint-ignore no-explicit-anyfunction MyLinkedList<T = any>(): MyLinkedList<T> {    let size = 0;    //头尾固定的伪节点    const head: DoublyLinkedList<T> = DoublyLinkedList();    const tail: DoublyLinkedList<T> = DoublyLinkedList();    head.next = tail;    tail.prev = head;
    function get(index: number): T | number {        if (size === 0) return -1;        if (index < 0 || index >= size) {            return -1;        }        if (index == 0) {            if (head.next) {                const val = head.next.val;                if (typeof val !== "undefined") {                    return val;                }            }        }        if (index === size - 1) {            if (tail.prev) {                const val = tail.prev.val;                if (typeof val !== "undefined") {                    return val;                }            }        }        if (index + 1 < size - index) {            let curr = head;            for (let i = 0; i < index + 1; i++) {                if (curr.next) {                    curr = curr.next;                }            }            const val = curr.val;            if (typeof val !== "undefined") {                return val;            }        } else {            let curr = tail;            for (let i = 0; i < size - index; i++) {                if (curr.prev) {                    curr = curr.prev;                }            }            const val = curr.val;            if (typeof val !== "undefined") {                return val;            }        }        return -1;    }
    function addAtHead(val: T): void {        const succ = head.next;        const pred = head;        const toAdd = DoublyLinkedList(val);        pred.next = toAdd;        succ && (succ.prev = toAdd);        toAdd.prev = pred;        toAdd.next = succ;        size++;    }
    function addAtTail(val: T): void {        const succ = tail;        const pred = tail.prev;        const toAdd = DoublyLinkedList(val);        toAdd.next = succ;        succ.prev = toAdd;        toAdd.prev = pred;        size++;        pred && (pred.next = toAdd);    }
    function addAtIndex(index: number, val: T): void {        if (index > size) {            return;        }        if (index < 0) {            addAtHead(val);            return;        }        if (index === size) {            addAtTail(val);            return;        }        let succ = tail;        let pred = head;
        if (index < size - index) {            pred = head;            for (let i = 0; i < index; i++) {                pred.next && (pred = pred.next);            }            pred.next && (succ = pred.next);        } else {            succ = tail;            for (let i = 0; i < size - index; i++) {                succ.prev && (succ = succ.prev);            }            succ.prev && (pred = succ.prev);        }        size++;        const toAdd = DoublyLinkedList(val);        toAdd.prev = pred;        toAdd.next = succ;        pred.next = toAdd;        succ.prev = toAdd;    }    function deleteAtHead(): void {        if (size) {            const pred = head;            const succ = head.next?.next ?? tail;            pred.next = succ;            succ.prev = pred;            size--;        }    }    function deleteAtTail(): void {        if (size) {            const pred = tail.prev?.prev ?? head;            const succ = tail;            pred.next = succ;            succ.prev = pred;            size--;        }    }    function deleteAtIndex(index: number): void {        if (index < 0 || index >= size) {            return;        }        if (index == 0) {            // size--;            deleteAtHead();            return;        }        if (index === size - 1) {            // size--;            deleteAtTail();            return;        }        let pred = head;        let succ = tail;
        if (index < size - index) {            pred = head;            for (let i = 0; i < index; i++) {                pred.next && (pred = pred.next);            }            pred.next?.next && (succ = pred.next.next);        } else {            succ = tail;            for (let i = 0; i < size - index - 1; i++) {                succ.prev && (succ = succ.prev);            }            succ.prev?.prev && (pred = succ.prev.prev);        }        size--;        pred.next = succ;        succ.prev = pred;    }    function length(): number {        return size;    }    function clear(): void {        size = 0;        head.next = tail;        tail.prev = head;    }
    return {        deleteAtTail,        deleteAtHead,        get,        addAtHead,        addAtTail,        addAtIndex,        deleteAtIndex,        length,        clear,    };}export default MyLinkedList;