你正在参与一个项目,为繁忙的铁路网开发一套列车调度系统。
有人请你为调度系统中的列车路线开发一个原型。每条路线由一串火车站组成,某趟列车会依次停靠这些车站。
你的团队决定用双向链表来表示时刻表中的每条火车路线。 火车路线沿途的每个车站都由链表中的一个节点表示。
你不需要操心各个车站的到达和出发时间。 每个车站只用一个数字表示就好。
路线可以延长,在路线的开头或末尾增加车站。 也可以从路线的开头或末尾移除车站来缩短。
有时某个车站会关闭,这时即使它不在路线的开头或末尾,也需要把它从路线中移除。
路线的大小不是以火车行驶的距离来衡量,而是以它停靠的车站数量来衡量。
链表是计算机科学中的一种基础数据结构,常用来实现其他数据结构。 顾名思义,它是一串链接在一起的节点。 它是一串“节点”,其中每个节点都链接到它的一个或多个相邻节点。 在单向链表中,每个节点只链接到它后面的那个节点。 在双向链表中,每个节点既链接到它前面的节点,也链接到它后面的节点。
如果你想深入了解链表,可以看看这篇文章,它用漂亮的图示做了讲解。
你将实现一个双向链表。
实现一个 Node,用它保存一个值,以及指向下一个节点和上一个节点的指针。
然后实现一个 LinkedList,它保存对第一个和最后一个节点的引用,并提供类似数组的接口来添加和删除元素:
push(在尾部插入值);pop(从尾部移除值);shift(从头部移除值);unshift(在头部插入值);delete(移除第一个匹配的节点)。为了让实现保持简单,测试不会覆盖错误情况。具体来说:不会对空链表调用 pop 或 shift。