链表——PowerShell版

链表是由一系列节点串连起来组成的，每一个节点包括数值部分和指针部分，上一节点的指针部分指向下一节点的数值部分所在的位置。

在C语言中我们有两种方式来定义链表——

1、定义结构体：来表示链表中的节点，节点中包含数值部分和指针部分。将一个节点的指针部分指向另一个节点的数值部分，这两个结构体之间就形成了一个链表。

2、不定义结构体：用一个数组来表示链表的数值部分，用另外一个数组来表示每个数值所对应的指针部分。

在PowerShell中定义一个链表更加简洁：

$linkedList = New-Object System.Collections.Generic.LinkedList[HashTable]

其中HashTable相当于我们在C语言中定义的结构体中的数值部分，而对于链表中数值进行的操作都被封装成了一系列链表对象的方法。

现在我们举一个现实生活中的例子——

考试结束，老师排好了一个成绩单（按成绩从高到低），现在来了个插班生，我们要把这个插班生的考试成绩插入到本班的成绩单中。

首先我们写一个方法，将排好的成绩单录入到一个链表中：

#Initial the students' scores.
function Initial($linkedList){
    $count = Read-Host "Type in the students' number"
    For($i=1; $i -le [int]$count; $i++){
        $tip = "This is the NO."+$i+" student"
        Write-Host $tip -ForegroundColor green
        $name = Read-Host "Type in the name"
        $score = Read-Host "Typen in the score"
        $linkedList.AddLast(@{Name=$name;Score=[int]$score}) 
    } 
}

然后我们写一个方法，将插班生的成绩插入到已排好序的成绩单链表中：

#Add student into the list by score.
function InsertStudent($linkedList)
{
    $score = Read-Host "Type in the score of the student"
    $score = [int]$score
    $currentNode = $linkedList.First
    $flag = $true
    while(($currentNode -ne $null) -and ($flag -eq $true))
    {
        if($currentNode.Value.Score -ge $score)
        {
            $currentNode = $currentNode.Next
        }else
        {
            $name = Read-Host "Type in the name of the student"
            $linkedList.AddBefore($currentNode, @{Name=$name;Score=$score})
            $flag = $false
        }
    }
}

最后我们来运行这两个方法，对成绩单链表进行初始化和插入操作，并显示插入数据后的链表：

Write-Host "---Now begin initial---" -ForegroundColor green
Initial $linkedList
Write-Host "---Now begin insert---" -ForegroundColor green
InsertStudent $linkedList 
Write-Host "---Result---" -ForegroundColor green
$linkedList

运行结果如下：

我们可以看到，我们不用再去像在C语言中一样对指针的指向进行操作，取而代之的是一系列已经封装好了的属于链表对象本身的方法和属性。比如：

链表对象的第一个节点——

$linkedList.First

某一结点的下一节点——

$node.Next

在链表的某一节点前插入一个节点——

$linkedList.AddBefore($currentNode, @{Name=$name;Score=$score})

我们可以看到，我们只需要关注节点插入的位置（目标节点）和节点对象本身的数值部分，剩下的对指针部分的操作已经封装到方法里了。我们只需要选择指定的方法就可以完成对目标节点前后的插入等操作。PowerShell和C#都是基于.NET的，所以在方法和属性上基本都是相同的，在这里附上一篇官方的关于链表的指南。