这一节，我们来介绍单链表这种数据结构。
单链表是一种逻辑上连续，而在内存存储位置不连续的线性结构。使用单链表，在插入和删除已知节点时，可以以 O(1) 的时间复杂度完成。
单链表由一个个节点组成，每个节点包含当前元素，以及下一个节点的位置信息。就和网页上的连接类似，一个页面不仅有当前信息，还包含下一个网页的连接信息。通过指针或者引用，我们就可以像浏览网页那样，过渡到下一个节点。
我们使用 Nim 语言实现系列数据结构。Nim 语言是一种高效而优雅的系统级编程语言，具体介绍可以查看 Nim 语言官网。
https://nim-lang.org/
https://nim-cn.com/
首先创建单个节点，每个节点保存当前信息，以及下一个节点的位置信息。在 Nim语言中 ref 相当于指针或者引用, 我们使用 type 声明类型，星号表明该函数可以被其他模块访问。T 是 Nim 中的泛型，代表这个函数可以支持任意合理的类型，比如 int, float 等类型。object 就和面向对象语言的类差不多，可以继承。
value 代表当前元素的信息，next 指向下一个节点。
# 微信公众号 Nim 编程 type SinglyNodeObj*[T] = object value*: T next*: ref SinglyNodeObj[T] SinglyNode*[T] = ref SinglyNodeObj[T]下面让我们定义一个单链表，单链表有两个属性，node 表示单链表保存的节点信息，而 lastNode 则表示指向单链表的尾部。定义一个 lastNode 属性，可以让我们以 O(1) 的时间复杂度在单链表尾部插入节点。
type SinglyList*[T] = ref object node*: SinglyNode[T] lastNode*: SinglyNode[T]我们刚才定义了单链表的底层数据表示，接下来让我们定义操作这些数据的函数。
首先我们希望创建一个空的节点，因为 result 是 ref 类型，所以我们需要先给它分配内存，只需 new 一下就行了。Nim 会自动初始化，假设 elem 是 int 类型，value 就被初始化为 0，而 next 则被初始化为 nil。
显然创建一个空节点，我们只需给 result 的 value 属性赋值即可。
proc newSinglyNode*[T](elem: T): SinglyNode[T] = new(result) result.value = elem下一步，我们需要创建一个单链表，类似的分配变量。我们首先创建一个首节点，这个节点和后续节点有些不同。在逻辑上，我们不考虑该节点的 value 属性，只保存下一个节点的信息，和 lastNode 类似，起到哨兵作用。之后，我们让 lastNode 指向头部节点。到此为止，一个空的单链表就创建完成了。
proc newSinglyList*[T](): SinglyList[T] = new(result) result.node = SinglyNode[T](next:nil) result.lastNode = result.node接下来，我们看头部插入节点。我们新建节点 node，让 node 节点的 next 属性指向第一个节点，接着再让头部节点的 next 属性指向新建节点。
proc prepend*[T](list: SinglyList[T], elem: T) = var p = list.node node = newSinglyNode(elem=elem) node.next = p.next p.next = node然后，我们在尾部插入节点，也比较容易。新建节点 node，让尾部节点的 next 属性指向 node，接着让 lastNode 节点指向 node。
proc insert*[T](list: SinglyList[T], elem: T) = var p = list.lastNode node = newSinglyNode(elem=elem) p.next = node list.lastNode = p.next在单链表插入指定节点。首先我们查找指定元素对应的个节点，接着在该节点的后面插入新节点。
proc find*[T](list: SinglyList[T], elem: T): SinglyNode[T] = result = list.node while (result != nil) and (result.value != elem): result = result.next proc insert*[T](list: SinglyList[T], pos: SinglyNode[T], elem: T) = if pos.isLast: list.insert(elem) var p = new SinglyNode[T] p.value = elem p.next = pos.next pos.next = p删除单链表出现的第一个指定元素。
proc delete*[T](list: SinglyList[T], elem: T) = var p = findPrevious[T](list, elem) if p == nil: return if p.next.isLast: list.lastNode = p p.next = nil if not p.isLast: p.next = p.next.next打印节点信息。
proc `$`[T](list: SinglyList[T]): string = while list.isEmpty: return "empty" var p = list.node.next while p != nil: result &= $p.value & "->" p = p.next result &= "tail"迭代节点元素。
iterator items*[T](list: SinglyList[T]): T = var p = list.node.next while p.next != nil: yield p.value p = p.next iterator pairs*[T](list: SinglyList[T]): tuple[idx: int, value: T] = var p = list.node.next idx = 0 while p.next != nil: yield (idx, p.value) p = p.next欢迎关注# 微信公众号 Nim 编程, Nim 中文官网 https://nim-cn.com/ 。
