TypeScript 旅途5：泛型，实现一个双向链表

当我们设计组件的时候，我们总是希望组件能支持足够多的数据类型，甚至是将来可能会添加的数据类型或者是自定义的数据类型，这样在构建系统的时候就提供了非常灵活的功能。像C++、Java、C#一样，TypeScript的泛型就是用来提供这种灵活性的。
先来看一个不使用泛型又支持多种数据类型的函数。

function identity(arg: any): any {
    return arg;
}

虽然使用 any 关键字让我们能够接收任意类型的参数，并返回任意类型。但是我们却丢失了具体的返回类型。

再来看一个用泛型定义的函数。

function identity<T>(a: T): T {
    return a;
}

这里的 <T>表示这是一个泛型函数， T 是一个 类型参数 ，它表示的是一种在运行时确定的类型。现在我们可以确定这个函数接收的参数类型和返回值的参数类型是同一种了。

如何使用这个泛型方法呢？

let output = identity<string>("myString"); 
let output = identity("myString");

我们会经常用第二种调用方法，因为编译器的类型推导会帮我们推导出来 T 的类型。

那么一个泛型函数的函数类型是什么呢？

function identity<T>(a: T): T {
    return a;
}
let fun: <T>(a: T)=> T = identity;

泛型函数的类型与非泛型函数的类型没什么不同，只是有一个 类型参数 在最前面，像函数声明一样。

泛型接口与泛型类

interface IList<T> {
    add(a: T);//添加元素
}

class Item<T> {
    private _name: string;
    private _value: T;
}

泛型类与泛型接口跟非泛型类和非泛型接口定义一样，只是名字末尾跟了一个 类型参数 ，T 被当作了一种确定的类型。

接下来看一个泛型的具体例子。实现一个双向的链表。双向链表就像是一个环一样，每个元素既有一个指向前一个元素的引用（prev），又有一个指向下一个元素的引用（next）。默认添加一个头元素一个尾元素，当没有给列表添加元素时，这个列表就只有这一个头元素，一个尾元素。

初始化列表头尾元素
当我们添加一个元素后，要修改头、尾元素的引用。
添加一个新元素，修改头尾引用
我们可以发现，不管我们添加多少元素，或是移除全部元素，头的prev引用和尾的next引用都是相互引用的，并且自始至终都不会修改。
现在该修改新添加的元素的prev和next引用了（初始化的时候我们给 prev 和 next 默认赋值为null）。
修改新元素的prev和next引用
再添加一个元素后是什么样呢？
添加第二个元素后
这里为了图片清晰些，没有把头的next引用和尾的prev引用用箭头标出来。
明白了原理后，我们就来使用泛型实现这个双向链表。
首先定义泛型接口，明确这个列表有哪些功能。

interface IList<T> {
    add(a: T);//添加元素
    insert(item: T, a: T);//插入元素
    remove(a: T);//移除元素
    header(): T;//返回头元素
    tail(): T;//返回尾元素
    find(a: T): T;//查找元素
    reverse_find(a: T): T;//反向查找元素
    size(): number;//返回列表元素个数
    empty(): boolean;//是否空列表
    clear(): void;//清空列表
}

现在定义一个包装列表中元素的泛型类型。

class Item<T> {
    private _name: string;
    private _value: T;//值
    private _prev: Item<T>;//指向的上一个元素
    private _next: Item<T>;//指向的下一个元素
    constructor(value: T) {
        this._name = value + '';
        this._value = value;
        this._prev = null;
        this._next = null;
    }
    set name(name: string) {
        this._name = name;
    }
    get name(): string {
        return this._name;
    }
    set value(value: T) {
        this._value = value;
    }
    get value(): T {
        return this._value;
    }
    set prev(item: Item<T>) {
        this._prev = item;
    }
    get prev(): Item<T> {
        return this._prev;
    }
    set next(item: Item<T>) {
        this._next = item;
    }
    get next(): Item<T> {
        return this._next;
    }
}

这个包装类型的_name属性只是为了打印的时候比较清晰，实际使用的时候没有任何用处。

用泛型类实现链表。

class DobuleList<T> implements IList<T> {
    private _count: number = 0;//记录元素个数
    private _header: Item<T>;//头元素
    private _tail: Item<T>;//尾元素
    constructor() {
        this._header = new Item<T>(null);
        this._header.name = 'header';
        this._tail = new Item<T>(null);
        this._tail.name = 'tail';
        this._header.prev = this._header.next = this._tail;
        this._tail.next = this._tail.prev = this._header;
    }
    add(a: T) {
        let item = new Item<T>(a);
        item.prev = this._tail.prev;
        item.next = this._tail;
        this._tail.prev = item;
        item.prev.next = item;
        this._count++;
    }

    insert(item: T, a: T) {
        if (this.empty()) {
            return;
        }
        let indexItem = this._header.next;
        while(indexItem !== this._tail) {
            if (indexItem.value == item) {
                let valueItem = new Item<T>(a);
                valueItem.prev = indexItem;
                valueItem.next = indexItem.next;
                indexItem.next.prev = valueItem;
                indexItem.next = valueItem;
                this._count++;
                break;
            }
            indexItem = indexItem.next;
        }
    }

    remove(a: T): T {
        if (this.empty()) {
            return;
        }
        let indexItem = this._header.next;
        while(indexItem !== this._tail) {
            if (indexItem.value == a) {
                indexItem.prev.next = indexItem.next;
                indexItem.next.prev = indexItem.prev;
                indexItem.next = null;
                indexItem.prev = null;
                let value = indexItem.value;
                indexItem.value = null;
                indexItem = null;
                this._count--;
                return value;
            }
            indexItem = indexItem.next;
        }
    }

    header(): T {
        return this._header.next.value;
    }

    tail(): T {
        return this._tail.prev.value;
    }
    
    find(a: T): T {
        if (this.empty()) {
            return;
        }
        let indexItem = this._header.next;
        while(indexItem !== this._tail) {
            if (indexItem.value == a) {
                return indexItem.value;
            }
            indexItem = indexItem.next;
        }
        return null;
    }

    reverse_find(a: T): T {
        if (this.empty()) {
            return;
        }
        let indexItem = this._tail.prev;
        while(indexItem !== this._header) {
            if (indexItem.value == a) {
                return indexItem.value;
            }
            indexItem = indexItem.prev;
        }
        return null;
    }

    size(): number {
        return this._count;
    }

    empty(): boolean {
        return this._count === 0;
    }

    clear(): void {
        let item = this._header.next;
        while(item !== this._tail) {
            item.prev = null;
            item.value = null;
            item = item.next;
            item.prev.next = null;
        }
        this._header.next = this._tail;
        this._tail.prev = this._header;
        this._count = 0;
    }

    print() {
        let item = this._header.next;
        while(item !== this._tail) {
            console.log(item);
            item = item.next;
        }
    }
}

print()方法只是为了打印调试。

测试一下我们的双向链表。

let list1 = new DobuleList<number>();
list1.add(3);
list1.add(5);
list1.insert(3, 4);
list1.insert(4, 8);
list1.print();
/*输出：
Item {_name: "3", _value: 3, _prev: Item, _next: Item}
Item {_name: "4", _value: 4, _prev: Item, _next: Item}
Item {_name: "8", _value: 8, _prev: Item, _next: Item}
Item {_name: "5", _value: 5, _prev: Item, _next: Item}
*/
list1.remove(4);
list1.print();
/*输出：
Item {_name: "3", _value: 3, _prev: Item, _next: Item}
Item {_name: "8", _value: 8, _prev: Item, _next: Item}
Item {_name: "5", _value: 5, _prev: Item, _next: Item}
*/
console.log(list1.find(4));//null
console.log(list1.reverse_find(3));//3
list1.clear();

let list2 = new DobuleList<string>();
list2.add('3');
list2.add('5');
list2.insert('3', '4');
list2.insert('4', '8');
list2.print();
/*输出：
Item {_name: "3", _value: "3", _prev: Item, _next: Item}
Item {_name: "4", _value: "4", _prev: Item, _next: Item}
Item {_name: "8", _value: "8", _prev: Item, _next: Item}
Item {_name: "5", _value: "5", _prev: Item, _next: Item}
*/
list2.remove('4');
list2.print();
/*输出：
Item {_name: "3", _value: "3", _prev: Item, _next: Item}
Item {_name: "8", _value: "8", _prev: Item, _next: Item}
Item {_name: "5", _value: "5", _prev: Item, _next: Item}
*/
list2.clear();

//用自定义类型来测试下
class Demo {
    constructor(public name: string, 
        public value: number) {
        this.name = name;
        this.value = value;
    }
    toString(): string {
        return `{name: ${this.name} value: ${this.value}}`;
    }
}
let list3 = new DobuleList<Demo>();
let demos = [new Demo('3', 3), new Demo('5', 5),
    new Demo('4', 4), new Demo('8', 8)];
list3.add(demos[0]);
list3.add(demos[1]);
list3.insert(demos[0], demos[2]);
list3.insert(demos[2], demos[3]);
list3.print();
/*输出：
Item {_name: "{name: 3 value: 3}", _value: Demo, _prev: Item, _next: Item}
Item {_name: "{name: 4 value: 4}", _value: Demo, _prev: Item, _next: Item}
Item {_name: "{name: 8 value: 8}", _value: Demo, _prev: Item, _next: Item}
Item {_name: "{name: 5 value: 5}", _value: Demo, _prev: Item, _next: Item}
*/
list3.remove(demos[2]);
list3.print();
/*输出：
Item {_name: "{name: 3 value: 3}", _value: Demo, _prev: Item, _next: Item}
Item {_name: "{name: 8 value: 8}", _value: Demo, _prev: Item, _next: Item}
Item {_name: "{name: 5 value: 5}", _value: Demo, _prev: Item, _next: Item}
*/
list3.clear();

实际上常用的数据结构堆、栈、优先队列等等都可以使用泛型来实现。