开始之前
数组是一种非常简单的存储数据序列的数据结构,本次分享如何实现和使用链表这种动态的数据结构，它可以随意的从中添加或移除项，它还会按需进行扩容。
本次分享内容主要包括：
链表数据结构
实现LinkedList类
链表数据结构
要存储多个元素，数组可能是最常用的数据结构。这种数据结构非常方便，提供了一个便利的[]
语法来访问其元素。然而，这种数据结构有一缺点：数组大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素(尽管JavaScript中有Array类方法帮我们做这些事情，但底层的情况同样如此)。
链表存储有序的元素集合，但是不同于数组，链表中的元素在内存中并不是连续放置的。每个元素有一个存储元素本身的节点和指向下一个元素的引用组成。
相对于传统数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需额外注意。在数组中，我们可以直接访问任何位置的任何元素，而想要访问链表中的一个元素，则需要从起点(表头)开始迭代链表直到找到所需的元素。
现实生活中火车就是理解链表很好的例子。一列火车是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢，改变它的位置、添加或移除它。下图演示了一列火车。每节车厢就是链表的元素，车厢间的连接就是指针。
链表的实现
理解链表是什么之后，现在就开始实现我们的数据结构。以下是LinkedList
类的“骨架”。
import { defaultEquals, IEqualsFunction } from "../utils";import {Node} from './linked-list-models';export default class LinkedList<T>{protected count = 0;protected head:Node<T> | undefined;constructor(protected equalsFn:IEqualsFunction<T>=defaultEquals){this.equalsFn = defaultEquals;}}
对于LinkedList
数据结构，我们从声明count
属性开始，它用来存储链表元素数量值。
我们要实现一个名为indexOf的方法，它使我们能够在链表中，找到一个特定的元素。要比较链表中的元素是否相等，我们需要使用一个内部调用的函数，名为euqalsFn
。使用linkedList
类的开发者可以自行传入用于比较两个javascript
对象或值是否相等的自定义函数。如果没有传入这个自定义函数，我们提供一个默认的defaultEquals
函数，作为默认的相等性比较函数。定义如下。
export function defaultEquals<T>(a:T,b:T):boolean{return a === b;}
由于该数据结构是动态的，我们还需要将第一个元素的引用保存下来。我们可以用一个叫做head
元素保存引用。
要表示链表中的第一个元素以及其他元素，我们需要一个助手类，叫做Node
。Node
类表示我们想要添加到链表中的项。它包含一个element
属性，该属性表示要加入链表元素的值；以及一个next
属性，该属性是指向链表中下一个元素的指针。代码如下。
export class Node<T> {constructor(public element: T, public next?: Node<T>) {}}
然后就是LinkedList
类的方法。在实现这些方法之前，我们先来看看它们的职责。
push(element)
：向链表尾部添加一个新元素。
insert(element,position)
:向链表的特定位置插入一个新元素。
getElementAt(index)
: 返回链表中特定位置的元素。如果链表中不存在这样的元素则返回undefined。
remove(element)
: 从链表中移除一个元素。
indexOf(element)
:返回元素在链表中的索引。如果链表中没有该元素则返回-1。
removeAt(position)
: 从链表的特定位置移除一个元素。
isEmpty()
：如果链表中不包含任何元素就返回true，否则返回false。
size()
：返回链表包含的元素个数，与数组length属性类似。
完整实现如下。
import { defaultEquals, IEqualsFunction } from "../utils";import {Node} from './linked-list-models';export default class LinkedList<T>{protected count = 0;protected head:Node<T> | undefined;constructor(protected equalsFn:IEqualsFunction<T>=defaultEquals){this.equalsFn = defaultEquals;}/*** 添加一个元素* @param element <T>*/push(element:T){const node = new Node(element);let current;if(this.head === null){this.head = node;}else{current = this.head;while(current.next !== null){current = current.next;}current.next = node}this.count++;}/*** 返回链表特定位置的元素* @param index number 索引值*/getElementAt(index:number){if(index >= 0 && index <= this.count){let node = this.head;for(let i=0; i<index && node != null; i++){node = node.next;}return node;}return undefined;}/*** 向链表的特定位置插入一个新元素* @param element 元素值* @param index 索引值*/insert(element:T,index:number){if(index >= 0 && index <= this.count){const node = new Node(element);if(index === 0){const current = this.head;node.next = current;this.head = node;}else{const previous = this.getElementAt(index - 1);node.next = previous.next;previous.next = node;}this.count++;return true;}return false;}/*** 从链表的特定位置移除一个元素* @param index 索引值*/removeAt(index:number){if(index>=0 && index < this.count){let current = this.head;if(index===0){this.head = current?.next;}else{const previous = this.getElementAt(index - 1);current = previous?.next;previous.next = current.next;}}}/*** 从链表中移除一个元素* @param element 元素*/remove(element:T){const index = this.indexOf(element);return this.removeAt(index);}/*** 返回元素在链表中的索引* @param element 元素*/indexOf(element:T){let current = this.head;for (let i=0;i<this.size()&¤t!=null;i++) {if(this.equalsFn(element,current.element)){return i;}current = current.next}return -1;}isEmpty(){return this.size() === 0;}size(){return this.count;}getHead(){return this.count;}clear(){this.head = undefined;this.count = 0;}toString() {if (this.head == null) {return '';}let objString = `${this.head.element}`;let current = this.head.next;for (let i = 1; i < this.size() && current != null; i++) {objString = `${objString},${current.element}`;current = current.next;}return objString;}}
小结
本次分享介绍了链表这种数据结构。链表相对数组最重要的优点就是无需移动链表元素，就能轻松的添加和移除元素。因此当你需要添加和移除很多元素的时候，最好的选择就是使用链表，而非数组。然后介绍了linkedList
类以及如何实现它。
链表还有很多变体，如：双向链表、循环链表和有序链表，在下一次分享它们的实现方式。
