2021SC@SDUSC山东大学软件学院软件工程应用与实践——claygl（源代码分析9）
2021SC@SDUSC
目录
8.insert(val) → {clay.core.LinkedList.Entry}
9.insertAt(idx, val) → {clay.core.LinkedList.Entry}
一.clay.core.LinkedList类概述
clay.core.LinkedList类为简单的双向链表，与数组相比，它的移除操作复杂度为 O(1)。
二.clay.core.LinkedList类的作用
clay.core.LinkedList类能够新建链表，清空链表，遍历链表，获取头尾节点，特定索引上的节点，获取对应节点的索引，插入节点，获取长度，判断为空，移除节点等操作
三.clay.core.LinkedList类源码分析
1.new LinkedList()
该函数是LinkedList类的构造函数。
无参数。
其源代码为：
var LinkedList = function () {
/**
* @type {clay.core.LinkedList.Entry}
*/
this.head = null;
/**
* @type {clay.core.LinkedList.Entry}
*/
this.tail = null;
this._length = 0;
}从源代码中可以看出，LinkedList共有三个成员变量，分别为head，类型为clay.core.LinkedList.Entry，初始值为null，表示头结点，tail，类型为clay.core.LinkedList.Entry，初始值为null，表示尾结点，length，类型为number，初始值为0，表示链表的长度。
2.clear()
该函数的作用是将链表清空。
无参数。
其源代码为：
LinkedList.prototype.clear = function () {
this.tail = this.head = null;
this._length = 0;
}从源代码中可以看出，该函数将头结点head和尾结点tail指向null，同时设置其长度为0，使链表不再指向任何结点，从而实现链表的清空。
3.forEach(cb, context)
该函数的作用是遍历链表节点，对每一节点执行某一操作
参数有cb，类型为function，表示节点执行的方法，context，表示执行的内容
其源代码为：
LinkedList.prototype.forEach = function (cb, context) {
var curr = this.head;
var idx = 0;
var haveContext = typeof(context) != 'undefined';
while (curr) {
if (haveContext) {
cb.call(context, curr.value, idx);
}
else {
cb(curr.value, idx);
}
curr = curr.next;
idx++;
}
}从源代码中可以看出，该函数初始化局部变量curr，指向其头结点，初始化idx为0，判断context是否为undefined，若是，则初始化haveContext为false，否则为true，表示是否含有内容。当curr不等于null时，对链表进行遍历，若habeContext为true，则调用cb的call方法，将context和curr的值，idx传入，否则，将curr的值和idx传入，完成后，转移到curr的下一节点，idx自增。从而对链表的每一个节点执行相应的操作，实现遍历操作。
4.getAt(idx)
该函数的作用是获取第idx个节点的值。
参数为idx，类型为number，表示取出节点的序号。
其源代码为：
LinkedList.prototype.getAt = function (idx) {
if (idx < 0) {
return;
}
var curr = this.head;
var cursor = 0;
while (curr && cursor != idx) {
curr = curr.next;
cursor++;
}
return curr.value;
}从源代码可以看出，该函数首先判断idx是否大于0，若不是，则返回，进行合法性检验。接着，取出idx的头结点head，赋值给curr，初始化cursor为0，对节点进行遍历，当取到下一个节点时，cursor++，直到cursor的值等于idx，取出当前节点，即可取出索引为idx的节点。
5.getHead()
该函数的作用是取出头结点的值。
无参数。
其源代码为：
LinkedList.prototype.getHead = function () {
if (this.head) {
return this.head.value;
}
}从源代码可以看出，该函数判断本对象的head是否存在，若存在直接返回head的值，从而取出头结点的值。
6.getTail()
该函数的作用是取出尾结点的值。
无参数。
其源代码为：
LinkedList.prototype.getTail = function () {
if (this.tail) {
return this.tail.value;
}
}从源代码可以看出，该函数判断本对象的tail是否存在，若存在直接返回tail的值，从而取出尾结点的值。
7.indexOf(value) → {number}
该函数的作用是获取对应值的节点索引。
参数为value，类型为节点的类型，表示获取索引节点对应的值，返回索引，类型为number。
其源代码为：
LinkedList.prototype.indexOf = function (value) {
var curr = this.head;
var cursor = 0;
while (curr) {
if (curr.value === value) {
return cursor;
}
curr = curr.next;
cursor++;
}
}从源代码中可以看出，该函数首先将head赋值给局部变量curr，初始化cursor为0，对链表进行遍历，取出每个节点的值与所选值比对，若是，则返回cursor，否则，转移到下一节点，cursor自增。不断进行，最终取出所选值的节点索引。
8.insert(val) → {clay.core.LinkedList.Entry}
该函数的作用是在链表的尾部插入一个新节点。
参数为val，类型为节点的值类型，表示插入新节点的值。
其源代码为：
LinkedList.prototype.insert = function (val) {
var entry = new LinkedList.Entry(val);
this.insertEntry(entry);
return entry;
}从源代码可以看出，首先新建一个链表节点，赋值val，将其赋值给局部变量entry，调用本对象的insertEntry方法，代码如下：
LinkedList.prototype.insertEntry = function (entry) {
if (!this.head) {
this.head = this.tail = entry;
}
else {
this.tail.next = entry;
entry.prev = this.tail;
this.tail = entry;
}
this._length++;
}该方法判断是否有头结点，无则设置entry为头结点和尾结点，否则，设置尾结点的下一节点指向entry，entry的前一节点指向tail，并把tail设置为entry，最后增加链表的长度，实现在链表尾部添加节点。
最终，即可完成链表尾部插入节点。
9.insertAt(idx, val) → {clay.core.LinkedList.Entry}
该函数的作用是在idx索引位置插入一个节点。
参数有idx，类型为number，表示索引的位置，val，类型为节点的值类型，表示插入节点的值。
其源代码为：
LinkedList.prototype.insertAt = function (idx, val) {
if (idx < 0) {
return;
}
var next = this.head;
var cursor = 0;
while (next && cursor != idx) {
next = next.next;
cursor++;
}
if (next) {
var entry = new LinkedList.Entry(val);
var prev = next.prev;
if (!prev) { //next is head
this.head = entry;
}
else {
prev.next = entry;
entry.prev = prev;
}
entry.next = next;
next.prev = entry;
}
else {
this.insert(val);
}
}从源代码中可以看出，首先，该函数对idx进行合法性检验，确保其大于等于0。然后，将头结点head赋值给局部变量next，初始化cursor为0。对链表进行遍历，在走到下一节点的同时，cursor自增1，知道cursor等于idx。接着，判断next是否为null，不为空，则创建一个值为val的节点，获取next的前驱赋值给prev，如果next为头结点，即无前驱，直接设置head为entry，否则前驱改为entry，entry的前驱改为prev，最后设置entry的后驱为next，next的前驱为entry，即可实现在指定位置添加节点。若链表为空，直接插入值为val的节点，从而实现特定位置添加节点。
10.insertEntry(entry)
该函数的作用是在尾部添加一个节点。
参数为entry，类型为Entry，表示节点。
其源代码为：
LinkedList.prototype.insertEntry = function (entry) {
if (!this.head) {
this.head = this.tail = entry;
}
else {
this.tail.next = entry;
entry.prev = this.tail;
this.tail = entry;
}
this._length++;
}该方法判断是否有头结点，无则设置entry为头结点和尾结点，否则，设置尾结点的下一节点指向entry，entry的前一节点指向tail，并把tail设置为entry，最后增加链表的长度，实现在链表尾部添加节点。
11.isEmpty()
该函数判断链表是否为空。
无参数。
其源代码为：
LinkedList.prototype.isEmpty = function () {
return this._length === 0;
}该函数判断本对象的length是否为0，为0则空。
12.length() → {number}
该函数获取链表的长度。
无参数。
其源代码为：
LinkedList.prototype.isEmpty = function () {
return this._length === 0;
}该函数直接返回本对象的长度length
13.remove(entry)
该函数的作用是移除entry节点。
参数为entry，表示移除的节点，类型为Entry。
其源代码为：
LinkedList.prototype.remove = function (entry) {
var prev = entry.prev;
var next = entry.next;
if (prev) {
prev.next = next;
}
else {
// Is head
this.head = next;
}
if (next) {
next.prev = prev;
}
else {
// Is tail
this.tail = prev;
}
entry.next = entry.prev = null;
this._length--;
}从源代码中可以看出，获取该节点的前驱prev，后驱next，如果前驱存在，设置前驱的后驱的next，否则设置头结点为next，如果后驱存在，设置后驱的前驱为prev，否则，尾结点为prev，设置entry的前驱和后驱为null，从而不再在链表中，链表长度减1，从而移除该节点。
14.removeAt(idx)
该函数的作用是移除特定索引上的节点。
参数为idx，类型为number，表示移除节点的索引。
其源代码为：
LinkedList.prototype.removeAt = function (idx) {
if (idx < 0) {
return;
}
var curr = this.head;
var cursor = 0;
while (curr && cursor != idx) {
curr = curr.next;
cursor++;
}
if (curr) {
this.remove(curr);
return curr.value;
}
}从函数中可以看出，首先对idx进行合法性检验，将头结点赋值给局部变量curr，初始化cursor为0。对链表进行遍历，每次到达下一节点时，cursor++，知道cursor等于idx，然后，调用remove方法移除当前节点curr即可完成相关操作，最后返回移除节点的值。