3
\$\begingroup\$

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.

There's two things I'd like to know about this code:

  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"

\$\endgroup\$
  • \$\begingroup\$ Is there a particular reason for disuse the (generic) LinkedList<T> Class? \$\endgroup\$ – JosefZ May 23 at 16:11
  • \$\begingroup\$ @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. \$\endgroup\$ – KGlasier May 23 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.