這一節(jié)，我們來(lái)介紹單鏈表這種數(shù)據(jù)結(jié)構(gòu)泡态。

簡(jiǎn)介

單鏈表是一種邏輯上連續(xù)，而在內(nèi)存存儲(chǔ)位置不連續(xù)的線性結(jié)構(gòu)迂卢。使用單鏈表某弦，在插入和刪除已知節(jié)點(diǎn)時(shí)桐汤，可以以 O(1) 的時(shí)間復(fù)雜度完成。

單鏈表由一個(gè)個(gè)節(jié)點(diǎn)組成刀崖，每個(gè)節(jié)點(diǎn)包含當(dāng)前元素惊科，以及下一個(gè)節(jié)點(diǎn)的位置信息。就和網(wǎng)頁(yè)上的連接類似亮钦，一個(gè)頁(yè)面不僅有當(dāng)前信息馆截，還包含下一個(gè)網(wǎng)頁(yè)的連接信息。通過(guò)指針或者引用蜂莉，我們就可以像瀏覽網(wǎng)頁(yè)那樣蜡娶，過(guò)渡到下一個(gè)節(jié)點(diǎn)。

Nim 語(yǔ)言簡(jiǎn)介

我們使用 Nim 語(yǔ)言實(shí)現(xiàn)系列數(shù)據(jù)結(jié)構(gòu)映穗。Nim 語(yǔ)言是一種高效而優(yōu)雅的系統(tǒng)級(jí)編程語(yǔ)言窖张，具體介紹可以查看 Nim 語(yǔ)言官網(wǎng)。

https://nim-lang.org/
Nim 中文社區(qū)
https://nim-cn.com/

單鏈表的基本結(jié)構(gòu)

首先創(chuàng)建單個(gè)節(jié)點(diǎn)蚁滋，每個(gè)節(jié)點(diǎn)保存當(dāng)前信息宿接，以及下一個(gè)節(jié)點(diǎn)的位置信息。在 Nim語(yǔ)言中 ref 相當(dāng)于指針或者引用, 我們使用 type 聲明類型辕录，星號(hào)表明該函數(shù)可以被其他模塊訪問(wèn)睦霎。T 是 Nim 中的泛型，代表這個(gè)函數(shù)可以支持任意合理的類型走诞，比如 int, float 等類型副女。object 就和面向?qū)ο笳Z(yǔ)言的類差不多，可以繼承蚣旱。

value 代表當(dāng)前元素的信息碑幅，next 指向下一個(gè)節(jié)點(diǎn)。

# 微信公眾號(hào) Nim 編程
type
  SinglyNodeObj*[T] = object
    value*: T
    next*: ref SinglyNodeObj[T]
  SinglyNode*[T] = ref SinglyNodeObj[T]

下面讓我們定義一個(gè)單鏈表塞绿，單鏈表有兩個(gè)屬性沟涨，node 表示單鏈表保存的節(jié)點(diǎn)信息，而 lastNode 則表示指向單鏈表的尾部异吻。定義一個(gè) lastNode 屬性拷窜，可以讓我們以 O(1) 的時(shí)間復(fù)雜度在單鏈表尾部插入節(jié)點(diǎn)。

type
  SinglyList*[T] = ref object
    node*: SinglyNode[T]
    lastNode*: SinglyNode[T]

定義函數(shù)

我們剛才定義了單鏈表的底層數(shù)據(jù)表示涧黄，接下來(lái)讓我們定義操作這些數(shù)據(jù)的函數(shù)篮昧。

首先我們希望創(chuàng)建一個(gè)空的節(jié)點(diǎn)，因?yàn)?result 是 ref 類型笋妥，所以我們需要先給它分配內(nèi)存懊昨，只需 new 一下就行了。Nim 會(huì)自動(dòng)初始化春宣，假設(shè) elem 是 int 類型酵颁，value 就被初始化為 0嫉你，而 next 則被初始化為 nil。

顯然創(chuàng)建一個(gè)空節(jié)點(diǎn)躏惋，我們只需給 result 的 value 屬性賦值即可幽污。

proc newSinglyNode*[T](elem: T): SinglyNode[T] = 
  new(result)
  result.value = elem

下一步，我們需要?jiǎng)?chuàng)建一個(gè)單鏈表簿姨，類似的分配變量距误。我們首先創(chuàng)建一個(gè)首節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)有些不同扁位。在邏輯上准潭，我們不考慮該節(jié)點(diǎn)的 value 屬性，只保存下一個(gè)節(jié)點(diǎn)的信息域仇，和 lastNode 類似刑然，起到哨兵作用。之后暇务，我們讓 lastNode 指向頭部節(jié)點(diǎn)泼掠。到此為止，一個(gè)空的單鏈表就創(chuàng)建完成了垦细。

proc newSinglyList*[T](): SinglyList[T] = 
  new(result)
  result.node = SinglyNode[T](next:nil)
  result.lastNode = result.node

接下來(lái)择镇，我們看頭部插入節(jié)點(diǎn)。我們新建節(jié)點(diǎn) node蝠检，讓 node 節(jié)點(diǎn)的 next 屬性指向第一個(gè)節(jié)點(diǎn)沐鼠，接著再讓頭部節(jié)點(diǎn)的 next 屬性指向新建節(jié)點(diǎn)挚瘟。

proc prepend*[T](list: SinglyList[T], elem: T) = 
  var 
    p = list.node
    node = newSinglyNode(elem=elem)
  node.next = p.next
  p.next = node

然后叹谁，我們?cè)谖膊坎迦牍?jié)點(diǎn)，也比較容易乘盖。新建節(jié)點(diǎn) node焰檩，讓尾部節(jié)點(diǎn)的 next 屬性指向 node，接著讓 lastNode 節(jié)點(diǎn)指向 node订框。

proc insert*[T](list: SinglyList[T], elem: T) =
  var 
    p = list.lastNode
    node = newSinglyNode(elem=elem)
  p.next = node
  list.lastNode = p.next

在單鏈表插入指定節(jié)點(diǎn)析苫。首先我們查找指定元素對(duì)應(yīng)的個(gè)節(jié)點(diǎn)，接著在該節(jié)點(diǎn)的后面插入新節(jié)點(diǎn)穿扳。

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

刪除單鏈表出現(xiàn)的第一個(gè)指定元素衩侥。

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

打印節(jié)點(diǎn)信息。

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"

迭代節(jié)點(diǎn)元素矛物。

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    

示例

when isMainModule:
  let a = newSinglyList[int]()
  a.insert(12)
  a.insert(8)
  a.insert(17)
  a.insert(12)
  a.insert(8)
  a.prepend(9)
  a.insert(17)
  let t1 = a.find(17)
  a.insert(t1, 99)
  a.prepend(87)
  a.delete(8)
  a.delete(12)
  echo a
# output 87->9->17->99->12->8->17->tail

歡迎關(guān)注# 微信公眾號(hào) Nim 編程, Nim 中文社區(qū)官網(wǎng) https://nim-cn.com/ 茫死。