链表

说明

实现一个双向链表。

和数组一样，链表也是一种简单的线性数据结构。 很多常见的数据类型都可以用链表来实现，比如队列、栈和关联数组。

链表是一组被称为节点的数据元素。 在单向链表中，每个节点保存一个值，以及一条指向下一个节点的链接。 在双向链表中，每个节点还额外保存一条指向前一个节点的链接。

你要编写一个双向链表的实现。 先实现一个 Node，用它保存一个值，以及指向下一个节点和前一个节点的指针。 然后实现一个 List，让它保存对第一个节点和最后一个节点的引用，并提供类似数组的接口来添加和删除元素：

• push（在末尾插入值）；
• pop（删除末尾的值）；
• shift（删除开头的值）。
• unshift（在开头插入值）；

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

想了解更多，请阅读维基百科上的链表。