前言
TypeScript 是 JavaScript 的超集，在 JavaScript 的基础上增加了强类型、接口、类和模块等特性。相比 JavaScript，TypeScript 支持静态类型检查，可以帮助我们在编写代码时提前捕获错误，提高代码的可读性和可维护性。在 TypeScript 中，我们可以使用面向对象编程的思想来实现各种数据结构，包括数组、链表、栈、队列、堆、二叉树等。本文将介绍 TypeScript 中常用的几种数据结构的实现方式与性能对比。
数组
数组是最常用的数据结构之一，它可以存储一组数据，并提供基本的增删改查操作。在 TypeScript 中，数组的定义和使用方法与 JavaScript 基本相同，只是我们可以使用泛型来限定数组中元素的类型。下面是一个示例代码：
-- -------------------- ---- ------- -- ---- ------ ----- --- ---- -------- - --- -- --- -- ---- ------ ----- --- ------- ------------- - --------- --------- -- ------ ------ - -- -- ------ ---------- -- --------- ------------ -- ---- ------------------ -- - ------------------ ---
数组在内存中以连续的方式存储，可以快速访问数组的任意位置，但是在使用 push 和 pop 等操作时，可能需要移动大量元素，导致性能下降。如果需要对数组进行频繁的添加和删除操作，建议使用链表代替数组。
链表
链表是另一种常用的数据结构，它由一系列的节点组成，每个节点包含了数据和下一个节点的地址。在 TypeScript 中我们可以使用类来定义节点和链表，并实现基本的增删改查操作。下面是一个示例代码：
-- -------------------- ---- -------
-- -------
----- ----------------- -
------ ----- --
------ ----- ----------------- - -----
----------------- -- ----- ----------------- - ---- - ----- -
--------- - -----
--------- - -----
-
-
-- -------
----- ------------- -
------- ----- ----------------- - -----
------- ----- ----------------- - -----
------------- -
--------- - -----
--------- - -----
-
-- -----------
------ --------- --- ---- -
----- ---- - --- ------------------------
-- ---------- --- ----- -
--------- - -----
--------- - -----
- ---- -
--------------- - -----
--------- - -----
-
-
-- -----------
------ ------------ -- ------ -------- ---- -
-- ------ - -- -
----- --- ------------ --- -- ------ -----------
-
----- ---- - --- ------------------------
--- ----- ----------------- - ---- - -----
--- -------- ----------------- - ---- - ----------
--- ---- - - -- ------- --- ---- -- - - ------ ---- -
---- - --------
------- - -------------
-
-- ----- --- ----- -
--------- - -----
- ---- -
--------- - -----
-
--------- - --------
-- -------- --- ----- -
--------- - -----
-
-
-- -----------
------ ------------- -------- - - --------- -
-- ------ - -- -
----- --- ------------ --- -- ------ -----------
-
--- ----- ----------------- - ---- - -----
--- -------- ----------------- - ---- - ----------
--- ---- - - -- ------- --- ---- -- - - ------ ---- -
---- - --------
------- - -------------
-
-- -------- --- ----- -
------ ----------
-
-- ----- --- ----- -
--------- - -------------
- ---- -
--------- - -------------
-
-- ------------- --- ----- -
--------- - -----
-
------ -------------
-
-- ----------
------ ---------- -------- - - --------- -
-- ------ - -- -
----- --- ------------ --- -- ------ -----------
-
--- -------- ----------------- - ---- - ----------
--- ---- - - -- ------- --- ---- -- - - ------ ---- -
------- - -------------
-
------ --------------
-
-- --------
------ ---------- ------- -
------ --------- --- -----
-
-- ------
------ --------- ------ -
--- ------ - --
--- -------- ----------------- - ---- - ----------
----- -------- --- ----- -
---------
------- - -------------
-
------ -------
-
-- --------
------ ---------- --- -
----- --- - ---
--- -------- ----------------- - ---- - ----------
----- -------- --- ----- -
-----------------------
------- - -------------
-
------ ----
-
-
-- ----
----- ---- - --- ---------------------
------------
------------
-------------- ---
---------------
----------------------------链表在内存中不是连续存储的，每个节点只存储了下一个节点的地址，因此在添加和删除节点时，不需要移动其他节点，可以快速完成操作。但是在访问链表中的任意位置时，需要从头节点开始遍历，时间复杂度为 O(n)，因此链表适用于需要频繁添加和删除节点，但不需要随机访问元素的场景。如果需要随机访问元素，建议使用数组。
栈
栈是一种后进先出的数据结构，即最后放入的元素最先弹出。在 TypeScript 中我们可以使用数组或链表来实现栈，栈的基本操作包括 push、pop、peek 和 isEmpty。下面是一个使用数组实现栈的示例代码：
-- -------------------- ---- -------
----- -------- -
------- ------ ----
------------- -
---------- - ---
-
-- --
------ ---------- --- ---- -
----------------------
-
-- --
------ ------ - - --------- -
------ -----------------
-
-- ------
------ ------- - - --------- -
------ ---------------------------- - ---
-
-- -------
------ ---------- ------- -
------ ----------------- --- --
-
-
-- ---
----- ----- - --- ----------------
--------------
--------------
--------------
-------------------------- -- -- -
------------------------- -- -- -
------------------------- -- -- -
----------------------------- -- -- -----在使用数组实现栈时，由于数组的长度可能会发生变化，导致内存空间的重新分配和数据的搬移，因此在添加和删除元素时，复杂度为 O(1) 和 O(n)。在使用链表实现栈时，由于链表的添加和删除操作时间复杂度均为 O(1)，因此链表实现的栈更加效率高。
队列
队列是一种先进先出的数据结构，即最先放入的元素最先弹出。在 TypeScript 中我们可以使用数组或链表来实现队列，队列的基本操作包括 enqueue、dequeue、peek 和 isEmpty。下面是一个使用数组实现队列的示例代码：
-- -------------------- ---- -------
----- -------- -
------- ------ ----
------------- -
---------- - ---
-
-- --
------ ------------- --- ---- -
----------------------
-
-- --
------ ---------- - - --------- -
------ -------------------
-
-- ------
------ ------- - - --------- -
------ --------------
-
-- --------
------ ---------- ------- -
------ ----------------- --- --
-
-
-- ----
----- ----- - --- ----------------
-----------------
-----------------
-----------------
-------------------------- -- -- -
----------------------------- -- -- -
----------------------------- -- -- -
----------------------------- -- -- -----在使用数组实现队列时，由于数组的长度可能会发生变化，导致内存空间的重新分配和数据的搬移，因此在添加和删除元素时，复杂度为 O(1) 和 O(n)。在使用链表实现队列时，由于链表的添加和删除操作时间复杂度均为 O(1)，因此链表实现的队列更加效率高。
堆
堆是一种特殊的树形数据结构，它满足以下两个条件：
- 堆是一个完全二叉树；
- 堆中每个节点的值都大于或等于（或小于或等于）其子节点的值。
在 TypeScript 中，我们可以使用数组来表示堆，并通过数组下标计算节点之间的关系。堆主要有两种类型：最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。下面是一个使用数组实现最大堆的示例代码：
-- -------------------- ---- -------
----- ---------- -
------- ------ --- - ---
-- -----------
------- -------------- --- ------ -
------ -------------------------
-
-- ---------
------- -------------- -------- - - --------- -
------ ------------------
-
-- ----------
------- --------------- --- - - --------- -
----- ----- - --------------------
----- ----------- - ----------------- - -- - ---
------ --------------------------
-
-- -----------
------- ------------- --- - - --------- -
----- ----- - --------------------
----- --------- - - - ----- - --
------ ------------------------
-
-- -----------
------- -------------- --- - - --------- -
----- ----- - --------------------
----- ---------- - - - ----- - --
------ -------------------------
-
-- ----
------- ------------ --- ---- -
--- ------- - -----
--- ------ - ---------------------
----- ------- --- --------- -- ------ - -------- -
----- ----------- - ----------------------
----------------------- - --------
---------------------------------- - -------
------- - -------
------ - ------------------------
-
-
-- ----
------- -------------- --- ---- -
--- ------- - -----
--- ---- - ----------------------
--- ----- - -----------------------
----- -
----- --- --------- -- ---- - -------- --
------ --- --------- -- ----- - --------
- -
-- ------ --- --------- -- ---- - ------ -
----- --------- - --------------------
---------------------------------- - -----
--------------------- - --------
------- - -----
- ---- -
----- ---------- - ---------------------
---------------------------------- - ------
---------------------- - --------
------- - ------
-
---- - ----------------------
----- - -----------------------
-
-
-- --------
------ ------------ --- ---- -
----------------------
------------------
-
-- ------
------ ---------- - - --------- -
-- ------------------ --- -- -
------ ----------
-
----- ---- - --------------
----- ---- - ------------------
-- ------------------ - -- -
------------- - -----
--------------------
-
------ -----
-
-- ------
------ ------- - - --------- -
------ ----------------- - - - ------------- - ----------
-
-- -------
------ ---------- ------- -
------ ----------------- --- --
-
-
-- -----
----- ---- - --- ------------------
---------------
---------------
---------------
------------------------- -- -- -
---------------------------- -- -- -
---------------------------- -- -- -
---------------------------- -- -- -----在使用数组实现堆时，由于数组的长度可能会发生变化，导致内存空间的重新分配和数据的搬移，因此在添加和删除元素时，复杂度为 O(log n) 和 O(log n)。在使用链表实现堆时，由于链表的添加和删除操作时间复杂度均为 O(1)，因此链表实现的堆更加效率高。但是由于堆的操作主要是基于数组下标的计算，而链表是没有下标的，因此链表实现的堆需要额外的空间来存储节点之间的关系。
来源：JavaScript中文网 ，转载请注明来源 https://www.javascriptcn.com/post/67c1e02b314edc2684aba067
