A linked list is a data structure that has a beginning, and an end. The only way through the structure is to go to the "next step", like stepping stones. This linked list works the same way, but in ascending order.

1. Are there any efficiencies I can make?
2. What methods could I use to make the sorting more generalized (like inputting a scriptblock as a parameter for sorting)
<#
.SYNOPSIS
Basic sorted Linked List implementation for practice and understanding
.DESCRIPTION
A list of objects linked together by pointing to the previous or next nodes. The list is lead by and
preceeded by nil nodes (Nodes with a value of $null) and are currently sorted in ascending order. .TODO Add customizable sorting preference to the Linked List #> class Node { <# .SYNOPSIS Basic Node class that holds the previous and next items in a the linked list .DESCRIPTION The Node class is used to represent items in a Linked List. Each Node has a Previous and Next node. These Nodes can be$null or have any PSObject inside them. On creation, each Node creates a seperate
'Nil' node, which has no Nodes next to them, and a value of $null. #> [Node]$previous
[PSObject]$data [Node]$next

Node() {}

Node($value) {$this.data     = $value$this.previous = [Node]::new()
$this.next = [Node]::new() } [String] ToString(){ return "$($this.data)" } } class linkedList { <# .SYNOPSIS Linked List class that sorts PSObjects in Ascending order. .DESCRIPTION The Linked List class starts with two Nill Nodes. As more Nodes are added, they're inserted in ascending order, depending on their return type. Integars will be ordered from -inf to inf, and Strings will be alphabetically. Items that equate will not be added. Inserting a 5 into a list that already has a 5 in it, will not be added. Alternatively, adding a "Z" when "z" is already added will also not work. Item is not replaced, just is not entered. .EXAMPLE$list = [linkedList]::new()
$list.insert(5)$list.insert(2)
$list.insert(11)$list.insert(12)
$list.insert(1)$list.toString()

>> nil -> 1 -> 2 -> 5 -> 11 -> 12 -> nil

.EXAMPLE
$list = [linkedList]::new()$list.insert('Z')
$list.insert('c')$list.insert('z')
$list.insert('a')$list.insert('C')
$list.insert('J')$list.insert('r')
$list.insert('Q')$list.toString()

>> nil -> a -> c -> J -> Q -> r -> Z -> nil
#>
[Node]$head linkedList() {$this.head = [Node]::new($null) } hidden [Node] searchItem ([PSObject]$o, [switch]$add=$false) {
<#
.SYNOPSIS
Looks for the PSObject specified by $o .DESCRIPTION Searches for the item specified in$o within the list. If the item is in the list, it's
returned. If the item is not in the list, the last valid node is returned.
If the item is not in the list and $add is$true, then the node that would otherwise be
before the searched item is returned. This allows the Insert function to add the node in
the proper location.
#>
[Node]$currNode =$this.head
[Node]$prevNode =$null

# Return the Head if it's the first item in the list.
if( $this.head.get_next() -eq$null ){
return $this.head } while ($currNode -and $currNode.get_next()){$currData = $currNode.get_data() # return the node if it's found if ($currData -eq $o) { return$currNode
}

# Return previous node if the current node is larger than the item being evaluated
if ($currData -gt$o -and $add) { return$prevNode
}
# Return the last non-nil node in the list if we hit the end
if (!$currNode.get_next() -and$add){
return $currNode }$prevNode = $currNode$currNode = $currNode.get_next() } return$prevNode
}

[PSObject] search ([PSObject]$obj){ <# .SYNOPSIS Returns the value of the node being searched for .DESCRIPTION Searches for the item specified in$o within the list. If the item is in the list, it's
returned. If the item is not in the list, $null is returned. #>$returnObj = $this.searchItem($obj, $false) if($obj -eq $returnObj.get_data()){ return$returnObj.get_data()
}
return $null } insert ($o) {
<#
.SYNOPSIS
Inserts the PSObject requeste
.DESCRIPTION
Searches for the item specified in $o within the list. If the item is in the list, it's returned. If the item is not in the list,$null is returned.
#>
$currNode =$this.searchItem($o,$true);

$nNode = [Node]::new($o)

# Do not insert a repeated item
if($currNode.get_data() -eq$o){
return
}

# Insert new item after the "next lowest" object data
elseif( $o -gt$currNode.get_data() ){
$this.swap($currNode, $nNode,$currNode.next)
}

}

hidden swap($prev,$new, $next){ <# .SYNOPSIS Sets the Next and Previous nodes for new nodes. .DESCRIPTION Set the Next and Previous nodes in the$new Node. Correct the Next and Previous pointers
for the Prev and Next nodes, respecitvely.
#>
$new.set_previous($prev)
$new.set_next($next)

$prev.set_next($new)
$next.set_previous($new)

}

[String] ToString(){
$s = "nil"$curr = $this.head while($curr.get_next()) {
$s += "$($curr.get_data()) -> "$curr = $curr.get_next() } return ($s + ("nil",$curr.get_data())[!!$curr.get_data()])
}
}


Sample:


$numOfObjects = 10$list = [linkedList]::new()
1..$numOfObjects | % {$item = -join (( 0x41..0x5A) + ( 0x61..0x7A) | Get-Random -Count $numOfObjects | % {[char]$_})
$list.insert($item)

}

\$list.ToString() -replace " -> ","n"


• Is there a particular reason for disuse the (generic) LinkedList<T>` Class? – JosefZ May 23 '19 at 16:11
• @JosefZ I’m mostly doing it for understanding/practice with the concept. It’s not something thats going to be used practically, otherwise I would use it. – KGlasier May 23 '19 at 16:19