FANDOM


PseudocodeEdit

Linear linked list with sentinel nodes at both ends:

Node structureEdit

structure Node(of ItemType)
    property Value as ItemType get; set;
    property Next as ref Node(of ItemType) get; set;
    
    new(item as ItemType)
        allocate new Node with Value = item, Next = Null
    
    new()
        allocate new Node with Next = Null

    finalize()
        deallocate currentObject

Basic methods and class declarationEdit

class LinkedList(of ItemType)
    hidden Head as ref Node(of ItemType)
    hideen SenTail as ref Node(of ItemType)  // the sentinel node
    hidden xCount as integer
    
    new()
        val TailNode = new Node(of ItemType)()
        Head = TailNode
        lCount = 0
    
    // Adds a new item at the beginning of the list
    InsertBeginning(item as ItemType)
        a = new Node(item)
        a.Next = Head
        Head = ref a
        xCount++

    // Adds a new item at the end of the list
    Add(item as ItemType)
        a = new Node()
        (val senTail).Next = ref a  // point the sentinel to a
        (val senTail).Value = item  // assign the item value to the sentinel's value
        senTail = ref a             // a is now the sentinel node
        xCount++
    
    // Inserts a new item after the item with the index specified
    Insert(index as integer, item as ItemType)
        if index < 0 or index >= lCount then
            throw Index out of range exception
             exit Insert
        a = new Node(item)
        cur = Head
        for i as integer = 0 to index - 1
            cur = (val cur).Next
        a.Next = (val cur).Next
        (val cur).Next = ref a
        xCount++
    
    // Removes the item at the specified index
    RemoveAt(index as integer)
        if index < 0 or index >= lCount then
            throw Index out of range exception
            exit RemoveAt
        cur = Head
        if index = 0 then
            Head = (val Head).Next
            finalize cur
        else
            for i as integer = 0 to index - 1
                cur = (val cur).Next
            cDel = (val cur).Next
            (val cur).Next = (val cDel).Next
            finalize cDel
        xCount--
    
    // Removes the first item from the list
    RemoveFirst()
        if xCount = 0 then exit RemoveFirst
        cur = Head
        Head = (val Head).Next
        finalize cur
    
    // Removes all items from the list
    Clear()
        for i as integer = 0 to lCount - 1
            RemoveFirst()

    property Item(index as integer) as ItemType
        common
            if index < 0 or index >= lCount then
                throw Index out of range exception
            cur = Head
            for i as integer = 0 to index - 1
                cur = (val cur).Next
        get
            return (val cur).Value
        set
            (val cur).Value = value
    
    property Count() as integer
        return xCount
    
    // Removes the first item in the list equal to the specified item
    Remove(item as ItemType) as boolean
        cur = Head
        if (val cur).Value = item then  // special case: remove first item
            Head = (val Head).Next
            finalize cur
            xCount--
            return true
        cBefore = cur
        cur = (val cur).Next        
        do while cur <> SenTail
            if cur = item then
                cBefore.Next = cur.Next
                finalize cur
                xCount--
                return true
            cBefore = cur
            cur = (val cur).Next
        return false

IterationEdit

...
    class Iterator
        hidden xHead as ref Node(of ItemType)
        hidden xSenTail as ref Node(of ItemType)
        hidden cur as ref Node(of ItemType)
        assembly new(Head as ref Node(of ItemType), SenTail as ref Node(of ItemType))
            xHead = Head
            cur = null
        
        MoveNext() as boolean
            if cur = Null then
                cur = xHead
            else
                cur = (val cur).Next
            return cur <> xSenTail
        
        property Current
            get
                return (val cur).Value
        
        Reset()
            cur = Null

    GetIterator() as Iterator
        return new Iterator(Head, SenTail)

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.