轨道
/
Tcl
Tcl
/
练习
/
链表
链表

链表

中等

简介

你正在参与一个项目,为繁忙的铁路网开发一套列车调度系统。

有人请你为调度系统中的列车路线开发一个原型。每条路线由一串火车站组成,某趟列车会依次停靠这些车站。

说明

你的团队决定用双向链表来表示时刻表中的每条火车路线。 火车路线沿途的每个车站都由链表中的一个节点表示。

你不需要操心各个车站的到达和出发时间。 每个车站只用一个数字表示就好。

路线可以延长,在路线的开头或末尾增加车站。 也可以从路线的开头或末尾移除车站来缩短。

有时某个车站会关闭,这时即使它不在路线的开头或末尾,也需要把它从路线中移除。

路线的大小不是以火车行驶的距离来衡量,而是以它停靠的车站数量来衡量。

Note

链表是计算机科学中的一种基础数据结构,常用来实现其他数据结构。 顾名思义,它是一串链接在一起的节点。 它是一串“节点”,其中每个节点都链接到它的一个或多个相邻节点。 在单向链表中,每个节点只链接到它后面的那个节点。 在双向链表中,每个节点既链接到它前面的节点,也链接到它后面的节点。

如果你想深入了解链表,可以看看这篇文章,它用漂亮的图示做了讲解。

实现说明

你将实现一个双向链表。

实现一个 Node,用它保存一个值,以及指向下一个节点和上一个节点的指针。

然后实现一个 LinkedList,它保存对第一个和最后一个节点的引用,并提供类似数组的接口来添加和删除元素:

  • push(在尾部插入值);
  • pop(从尾部移除值);
  • shift(从头部移除值);
  • unshift(在头部插入值);
  • delete(移除第一个匹配的节点)。

为了让实现保持简单,测试不会覆盖错误情况。具体来说:不会对空链表调用 pop 或 shift。


来源

经典的计算机科学主题
通过 GitHub 编辑 链接将在新窗口或新标签页中打开
Tcl Exercism

准备好开始 链表 了吗?

注册 Exercism,借助 135 个练习 和真人导师指导,学习并掌握 Tcl,全部免费。