JavaScript 双向链表实现与互联网机顶盒实战应用

双向链表节点类实现

以下是具体的实战代码实现部分。

首先是 linkedlistnode.js 文件中定义的节点类。

 
/* 
该部分代码定义了链表节点的基本结构。
*/ 
Dare.LinkedListNode 构造函数定义如下：
初始化数据域为 null。
初始化前驱指针为 null。
初始化后驱指针为 null。
}; 
调用 Dare.extend 方法使节点类继承自 Dare 基类。
定义获取节点数据的方法 getValue：
直接返回当前节点的数据域 data。
}; 
定义设置节点数据的方法 setValue：
将传入的对象 obj 赋值给当前节点的数据域 data。
}; 
定义获取前驱节点的方法 getPrev：
返回当前节点的前驱指针 prev。
}; 
定义设置前驱节点的方法 setPrev：
将传入的 node 赋值给当前节点的前驱指针 prev。
}; 
定义获取后驱节点的方法 getNext：
注意：此处代码逻辑返回的是 prev 而非 next，可能存在实现偏差。
}; 
定义设置后驱节点的方法 setNext：
注意：此处代码逻辑将 node 赋值给了 prev 而非 next，可能存在实现偏差。
}; 

双向链表类核心功能

接下来是 linkedlist.js 文件中定义的链表类。

 
/* 
该部分代码定义了双向链表的整体结构。
*/ 
Dare.LinkedList 构造函数定义如下：
初始化头指针 head 为 null。
初始化当前遍历指针 current 为 null。
初始化尾指针 tail 为 null。
初始化链表长度 length 为 0。
}; 
调用 Dare.extend 方法使链表类继承自 Dare 基类。
/* 
实现尾插法添加节点的功能 appendNode。
*/ 
appendNode 方法接收一个 node 参数：
如果链表实例为 null，则直接返回。
如果传入的节点 node 为 null，则直接返回。
获取当前链表的尾节点 tail。
判断尾节点 tail 是否为 null：
若为 null，说明链表为空，将新节点同时设为 head 和 tail。
} 
若不为 null，执行以下链接操作：
将原尾节点的 next 指针指向新节点 node。
将新节点 node 的 prev 指针指向原尾节点 tail。
更新链表的尾指针 tail 为新节点 node。
} 
链表长度 length 自增 1。
}; 
/* 
实现删除节点的功能 moveNode。
*/ 
moveNode 方法接收一个 node 参数：
如果链表实例为 null，则直接返回。
如果传入的节点 node 为 null，则直接返回。
处理中间节点的情况：
获取待删除节点的前驱节点 prev。
如果前驱节点 prev 不为 null：
将前驱节点的 next 指针指向待删除节点的后继节点。
} 
判断待删除节点的后继节点 node.next 是否为 null：
若不为 null，将后继节点的 prev 指针指向前驱节点 prev。
} 
处理头节点的情况：
判断待删除节点 node 是否等于头指针 head：
若相等，将头指针 head 更新为待删除节点的后继节点。
} 
处理尾节点的情况：
判断待删除节点 node 是否等于尾指针 tail：
若前驱节点 prev 不为 null：
将尾指针 tail 更新为前驱节点 prev。
} 
否则（说明链表只有一个节点）：
将头指针 head 和尾指针 tail 均设为 null。
} 
} 
清空待删除节点的前驱和后继指针。
链表长度 length 自减 1。
完成节点删除操作。
}; 
/* 
实现构造节点数据的方法 constructNode。
*/ 
constructNode 方法接收 node 和 obj 参数：
如果 node 或 obj 为 null，则直接返回。
将 obj 赋值给 node 的 data 属性。
返回构造好的 node 节点。
}; 
/* 
实现获取节点数据的方法 getNodeData。
*/ 
getNodeData 方法接收一个 node 参数：
如果 node 为 null，则直接返回。
返回 node 节点的 data 数据。
}; 
/* 
实现从头开始遍历的方法 start。
*/ 
start 方法：
如果链表实例为 null，则直接返回。
将当前指针 current 指向头节点 head，并返回 current。
}; 
/* 
实现从尾开始遍历的方法 end。
*/ 
end 方法：
如果链表实例为 null，则直接返回。
将当前指针 current 指向尾节点 tail，并返回 current。
}; 
/* 
实现获取下一个节点的方法 nextNode。
*/ 
nextNode 方法：
如果链表实例为 null，则直接返回。
如果当前指针 current 为 null，则返回。
保存当前节点 node 为 current。
将当前指针 current 更新为其后继节点 next。
返回保存的原始节点 node。
}; 
/* 
实现获取上一个节点的方法 prevNode。
*/ 
prevNode 方法：
如果链表实例为 null，则直接返回。
如果当前指针 current 为 null，则返回。
保存当前节点 node 为 current。
将当前指针 current 更新为其前驱节点 prev。
返回保存的原始节点 node。
}; 
/* 
实现判断链表是否为空的方法 isempty。
*/ 
isempty 方法：
如果链表实例为 null，返回 true。
如果头指针 head 为 null：
返回 true。
} 
否则：
返回 false。
} 
}; 
/* 
实现获取链表长度的方法 getLength。
*/ 
getLength 方法：
如果链表实例为 null，直接返回。
返回链表的 length 属性值。
}; 
/* 
实现清空链表的方法 clearList。
*/ 
clearList 方法：
注意：此处代码直接操作 head.next，若 head 为 null 可能报错。
将头指针 head 设为 null。
}; 
/* 
实现判断链表是否包含特定节点的方法 containsNode。
*/ 
containsNode 方法接收一个 obj 参数：
如果链表实例为 null，返回 false。
初始化遍历节点 node 为 list.head。
如果 node 为 null，返回 false。
循环遍历链表，直到 node 为 null：
如果 node 的 data 等于 obj：
返回 true。
} 
将 node 更新为其后继节点 next。
} 
}; 

实战调用与用例演示

以下是实战调用用例代码，后续将持续更新。

 
JavaScript 脚本标签开始。
实例化一个 Dare.LinkedList 对象 linkedList。
定义 createList 函数用于创建链表：
循环变量 i 从 0 到 6（共7次）：
创建一个空对象 movie。
实例化一个 Dare.LinkedListNode 对象 linkedListNode。
设置 movie 对象的 id 为 i。
设置 movie 对象的 name 为 'movie_' + i。
将 movie 对象赋值给 linkedListNode 的 data 属性。
调用 linkedList.appendNode 将节点添加到链表。
} 
注释掉的删除节点函数调用 deleteNode。
注释掉的输出整个链表函数调用 printList。
调用 printNode 函数打印指定节点信息。
} 
定义 printList 函数用于输出整个链表：
初始化遍历节点 node 为 list.head。
如果 node 为 null，直接返回。
初始化 HTML 字符串 html 为空。
循环遍历链表，直到 node 为 null：
获取节点数据 movie。
拼接 movie.id 和 movie.name 到 html 字符串。
将 node 更新为其后继节点 next。
} 
使用 document.write 输出拼接好的 html 字符串。
} 
定义 deleteNode 函数用于删除指定节点：
初始化遍历节点 node 为 list.head。
如果 node 为 null，直接返回。
初始化计数器 i 为 0。
循环遍历链表，直到 node 为 null：
如果 i 等于 3：
调用 linkedList.moveNode 删除当前节点。
跳出循环。
} 
计数器 i 自增 1。
将 node 更新为其后继节点 next。
} 
} 
定义 printNode 函数用于打印指定节点：
初始化遍历节点 node 为 list.head。
如果 node 为 null，直接返回。
初始化计数器 i 为 0。
循环遍历链表，直到 node 为 null：
如果 i 等于 4：
调用 linkedList.getNodeData 获取节点数据 movie。
使用 document.writeln 打印 movie.id。
使用 document.writeln 打印 movie.name。
跳出循环。
} 
计数器 i 自增 1。
将 node 更新为其后继节点 next。
} 
} 
JavaScript 脚本标签结束。