Linked Lists

NoNonFreeSoftwr · Sep 24th 2014

Re: Linked Lists

There does not appear to be an easy way to include parameters when creating an object

Code

Option Explicit


Sub test


dim c as cNode


Set c = new cNode(somestring, someobject) ' Not possible?


stop


endsub

Display More

I discovered during some reading that you can use something called a Factory pattern to do this

Instead of

Code

set c = new cNode(somestring,someobject) the factory pattern to me at least suggest taking this approach


set c = somefunctionname(somestring,someobject)

In that same project, have a module that includes the public fuction. The job of this function is to do all the steps of setting the object as new and initializing the property values.

Function CreatecNode(byval somestring as String, byref someobject as cNode) as cnode

Code

dim CreatecNode as cNode


set CreatecNode = New cNode


CreatecNode.cData = "This is a string"


Set CreatecNode.cNext = Nothing  ' Nothing counts as an object since I don't have another object to point to at the moment


End Function

Display More

**iwrk4dedpr** · Sep 24th 2014

Re: Linked Lists

Yeah I think that being able to set initial values like that is a part of the polymorphism of oop.

In other languages like c++ you can create multiple initializing routines with passed parameters which you specify when you create the new object.

NoNonFreeSoftwr · Sep 24th 2014

Re: Linked Lists

I just saw it mentioned on some page but am not sure if I am using the concept correctly. I think I created my first linked list based on the image below if I formatted correctly. If not, the list is a node with the value of A with a next pointing to the node on the right and so on. Once the list is created it sets it to the variable sList.

[ATTACH=CONFIG]62411[/ATTACH]

I notice that my image is again way too small. Any idea why that is happening?

Subroutine -

Code

Option Explicit


Sub cTest()


Dim Factory As cFactory
Dim ArrStrList(1 To 3) As String
Dim sList As cnode


Set Factory = New cFactory
Set sList = New cnode


ArrStrList(1) = "A"
ArrStrList(2) = "B"
ArrStrList(3) = "C"


Set sList = Factory.CreateList(ArrStrList)


Stop


End Sub

Display More

Class - cNode

Code

Option Explicit


Private pdata As String
Private pnext As cnode




Property Let cdata(value As String)
    pdata = value
End Property


Property Get cdata() As String
    cdata = pdata
End Property
Property Set cnext(value As cnode)
    Set pnext = value
End Property


Property Get cnext() As cnode
   Set cnext = pnext
End Property

Display More

Class - cFactory

Code

Option Explicit


Function CreateList(ByRef StringIn() As String) As cnode


Dim i As Long
Dim cList As cnode
Dim CurrentNode As cnode


Set cList = New cnode
Set CurrentNode = New cnode


For i = UBound(StringIn) To LBound(StringIn) Step -1


    CurrentNode.cdata = StringIn(i)
    Set CurrentNode.cnext = cList
    Set cList = CurrentNode
    Set CurrentNode = New cnode


Next i


Set CreateList = cList




End Function

Display More

Again I dont know if this follows factory pattern correctly or if it is even useful here or not.

NoNonFreeSoftwr · Oct 7th 2014

Re: Linked Lists

The lastest notes

NoNonFreeSoftwr · Oct 7th 2014

Re: Linked Lists

The image did not attach. Trying out MediaGoblin, a Free Software decentralized alternative to Youtube, Flicker, Souncloud etc. This would be my first time uploading a photo at this site and putting a link here.
https://b2aeaa58a57a200320db-8…/1113/LinkedLIstNotes.jpg

NoNonFreeSoftwr · Oct 7th 2014

Re: Linked Lists

Awesome it worked

NoNonFreeSoftwr · Oct 8th 2014

Re: Linked Lists

More notes.

[ATTACH=CONFIG]62595[/ATTACH]

NoNonFreeSoftwr · Oct 8th 2014

Re: Linked Lists

More notes. Click thumnail to view larger image

[ATTACH=CONFIG]62595[/ATTACH]

NoNonFreeSoftwr · Oct 17th 2014

Re: Linked Lists

I had the first method of sList, sInsertFront, all written and diagrammed out. sInsertFront inserts a node into the front of an existing linked list. I tested it out for 10,100,1000 sInsertFront operations via a loop and it worked great. When I tried it for 1,000,000, excel crashed and I lost all my work. I will redo it next week and post.

NoNonFreeSoftwr · Oct 24th 2014

Re: Linked Lists

I had some time to work on the Linked List project. Code below. I was stuck on the concept of encapsulation for quiet awhile. I would make the sList class and then try to pass an sListNode Object to one of the sList's methods as a parameter. That seemed to defeat the purpose of encapsulation, finally I figured out that I did not need to pass an sListNode Object as a parameter, but only the "cargo" of that obect and just let the sList class handling creating the sListNode Objects as needed. I still have more methods to write for this class but I think I should not have to much trouble from this point.

The sList class. All the methods that work with sListNode Objects are in this class. 3 have been written so far.

Code

Option Explicit




'The sList class is created to address at least 2 scenarios with attempting methods directly in the sListNode class
'1. If two variables, x and y  point to the same SListNode (linked list), then operations will change sListNode for one variable but not the other
'Set x = New sListNode("Soap",x) ==> A new sListNode is created. The item is set to "Soap". The Next is set to point to the old value of x. Finally x is assigned to this n ew list
'x and y are now two different linked lists
'2. How would you represent an empty list?  If an empty list is represented by Nothing (null in Java), you will get a run time error by calling a sListNode method on x.
'The solution to these two problems in Java (and maybe VBA) is a separate sList class (as opposed to the sListNode class).  The job of the sList class is to maintain the
'head of the list in a separate data structure. The Head is similar to a sListNode, except that instead of the item (field?), it has a Size field.  Instead of a Next field
'it has a field called Head.






'When initialized by for example set q=New sList, pSize will be 0 and pHead will be Nothing. The New keyword causes an object to be created from sList. As drawn
'that object is simply drawn schematically as square or rectangle to represent a "blank" object.  Private pSize and Private pHead below create a property each of that object. After
'Those two statements, there now an object that is no longer "blank", it actually now has two properties by default pSize is set to 0 and pHead is set to Nothing.
'These properties are created whenever the sList is initialized or created for the first time.  The methods below (either Sub subname() or Function FunctionName() are
'Not called when the object is initialized for the first time.  They are only called explicitly,  sListObject.SomeMethod
'This sList object is NOT part of the linked list
'The head property of an sList always points to a Linked List, even for an empty linked list. Null or Nothing is an empty linked list.


Private pSize As Long
Private pHead As sListNode










'This sList class encapsulates the sListNode class and prevents the user
'from being able to directly access its properties or methods
'as well as solves the two problems mentioned in #1 and #2 above.


'Method sInsertFront will insert an sListNode object at the front of the linked list that pHead points to
'These methods should be sketched out on paper.  Note that for any object, it must be pointed to in order to "exist".  If during the process
'of rearranging pointers, a linked list even momentarily is not "pointed to", it will be lost and garbage collected. So the order
'in which pointers are rearranged is important


'Note that sInsertFront does not take in an sListNode as a variable, although it could.  An sList Object is designed to encapsulate an sListNode Object
'the user should not need or be able to to directly work with sListNode's properties or methods in their code.
'Only the "cargo" of an sListNode is sent as a parameter.  An sList Object will take care of creating all sListNode Object(s) and
'putting the parameter "cargo" in the item property of an sListNode Object.  For now, it is assumed that the pData property (Cargo) of an sListNode Object
'is always a string. Later it may be possible to chagne it to type Variant or Object.






Sub sInsertFront(ByRef sListNodeCargo As String)
'It is possible to have the parameter to an sListNode object, but that defeats the purpose of encapsulation, I think.
'The user should not be directly working with an sListNode's properties or methods. Once these Classes are finished, the
'user should not need to work directly with Nodes at all.


    Dim aNewNode As sListNode
    
    Set aNewNode = New sListNode
    
    aNewNode.sSetData = sListNodeCargo
       
    If pSize = 0 Then
    
            Set pHead = aNewNode
        
        Else
        
            Set aNewNode.sSetNext = pHead
            Set pHead = aNewNode
          
    End If
    
    pSize = pSize + 1
    
End Sub
Function sGetLastNode() As sListNode
'Gets the last sListNode Object in the linked list pointed to by this instance of the sList Object's pHead property
'Noted that me.pHead does not seem to work, not sure why. Using pHead instead of me.pHead seems to work.


    Set sGetLastNode = pHead
    
    Do While Not sGetLastNode.sGetNext Is Nothing
    
        Set sGetLastNode = sGetLastNode.sGetNext
    
    Loop


End Function


Function sLength() As Long
'Returns the number of sListNode objects that are in the linked list that this instance of the sList Object's pHead property points to
    sLength = pSize
End Function

Display More

The sListNode Class

Code

Option Explicit


Private pdata As String
Private pnext As sListNode




Property Let sSetData(value As String)
    pdata = value
End Property


Property Get sGetData() As String
    sGetData = pdata
End Property
Property Set sSetNext(value As sListNode)
    Set pnext = value
End Property


Property Get sGetNext() As sListNode
   Set sGetNext = pnext
End Property

Display More

The code below just tests some of the methods of the sList class

Code

Sub test3333()


Dim i As Long
Dim j As Long


Dim h As sListNode


Dim q As sList
Dim String1 As String




Set q = New sList


For i = 1 To 4


    q.sInsertFront (CStr(i))


Next i


Set h = q.sGetLastNode


Stop




End Sub

Display More

NoNonFreeSoftwr · Oct 24th 2014

Re: Linked Lists

The diagram for the sInsertFront method of the sList class

https://goblinrefuge.com/media…list-method-sinsertfront/

**iwrk4dedpr** · Oct 24th 2014

Re: Linked Lists

You state something about "garbage" being collected.

I'm not an expert on the "VBA" and I'm pretty sure that .net employs a garbage collector ( memory cleaner ) but vba does not. The memory that loses the pointer to just sits there and is never returned to the portion of the memory HEAP that the instance runs in. ( Hence you will get memory leakage if this happens ) at least I believe it will.

When you did your test for 1,000,000 nodes you might have ran out of memory that was allocated for your instance. I don't see a error handling around your "Set aNewNode = New sListNode" maybe if you do error checking when the "NEW" event fails you can cleanly abort execution without it crashing ...

NoNonFreeSoftwr · Oct 25th 2014

Re: Linked Lists

Thanks for pointing that out. I have a lot of GB's of RAM in this machine, I wonder how much memory could a million nodes take, or how much memory is typically allocated to an instance of Excel? I got the garbage collection reason from the video CS 61B on youtube, but that was for Java. For me the important thing was that you lose access to the rest of the linked list. How could error handling be set up for sInsertFront? I do not usually include error handling in my code.

Also I see from the code that I was still having trouble with the concept of encapsulation when I posted it. The method sGetLastNode returns an sListNode which I now realize is not a good thing. I think it would have been helpful to clearly understand what the goal of the encapsulation was in the first place for this case - to prevent the user from having the ability to access any nodes at all in any way. As far as the user is concerned, they just want a list and some methods to manipulate the list. I think the method is supposed to be called sGetLastItem, not sGetLastNode, and it is supposed to return the "cargo" of the last sListNode, not the node itself.

NoNonFreeSoftwr · Nov 6th 2014

Re: Linked Lists

Here is the code that I have so far, minus commenting. There are 7 methods listed below

sInsertFront	Fast
sInsertBack	Slow
sGetLastItem	Slow
sGetFirstItem	Fast
sGetNth	Slow
sLength	Fast
sPrintList	Slow

sInsertFront seems to crash Excel if more than about 4000 nodes are inserted. If you have a for next loop with variable i, that keeps using sInsertFront, how would you trap the i when excel crashes?

Sometimes I will get "Out of Stack Space" error before the crash. What are the limits of the Stack Space? If Instead of one sList node with say 30,000 nodes, would 10 sList nodes of 3000 nodes each prevent the stack space error?

Other than that the code seems to work ok. I actually used it in a different program and was suprised how well it worked, it was useful.

Thanks

sListNodeClass

Code

Option Explicit


Private pdata As String
Private pnext As sListNode




Property Let sSetData(value As String)
    pdata = value
End Property


Property Get sGetData() As String
    sGetData = pdata
End Property
Property Set sSetNext(value As sListNode)
    Set pnext = value
End Property


Property Get sGetNext() As sListNode
   Set sGetNext = pnext
End Property

Display More

sList Class

Code

Option Explicit




Private pSize As Long
Private pHead As sListNode






Sub sInsertFront(ByRef sListNodeCargo As String)


    Dim aNewNode As sListNode
    
    Set aNewNode = New sListNode
    
    aNewNode.sSetData = sListNodeCargo
       
    If pSize = 0 Then
    
            Set pHead = aNewNode
        
        Else
        
            Set aNewNode.sSetNext = pHead
            Set pHead = aNewNode
          
    End If
    
    pSize = pSize + 1
    
End Sub


Sub sInsertBack(ByRef sListNodeCargo As String)




    Dim aNewNode As sListNode
    Dim FindLastNode As sListNode
    
    Set aNewNode = New sListNode
    
    aNewNode.sSetData = sListNodeCargo
       
    If pSize = 0 Then
    
            Set pHead = aNewNode
        
        Else
            
            Set FindLastNode = pHead
        
            Do While Not FindLastNode.sGetNext Is Nothing
    
                Set FindLastNode = FindLastNode.sGetNext
    
            Loop
            


            
            Set FindLastNode.sSetNext = aNewNode
            
          
    End If
    
    pSize = pSize + 1
    
End Sub




Function sGetLastItem() As String


    Dim sGetLastNode As sListNode
    
    Set sGetLastNode = pHead
    
    Do While Not sGetLastNode.sGetNext Is Nothing
    
        Set sGetLastNode = sGetLastNode.sGetNext
    
    Loop
    
    sGetLastItem = sGetLastNode.sGetData


End Function


Function sGetFirstItem() As String


sGetFirstItem = pHead.sGetData


End Function


Function sGetNth(ByRef NthItem As Long) As String




Dim tNode As sListNode
Set tNode = pHead




sGetNth = sGetNthHelper(NthItem, tNode)


End Function


Private Function sGetNthHelper(ByRef Nth As Long, ByRef TempNode As sListNode) As String


If Nth < 1 Or Nth > pSize Then
    Stop
End If


If Nth = 1 Then
    sGetNthHelper = TempNode.sGetData
    Exit Function
End If


Set TempNode = TempNode.sGetNext
sGetNthHelper = sGetNthHelper(Nth - 1, TempNode)


End Function






Function sLength() As Long


    sLength = pSize
    
End Function


Function sPrintList()
Dim i As Long
Dim String1 As String
Dim StringOld As String
Dim TempNode As sListNode


Set TempNode = pHead


For i = pSize To 1 Step -1




    String1 = " " & sGetNth(i) & " " & StringOld
    StringOld = String1
    
Next i


MsgBox String1


End Function

Display More

NoNonFreeSoftwr · Nov 6th 2014

Re: Linked Lists

I forgot to mention, the method sGetNth was a difficult one for me to write. I tried to do the recursive solution that seems to be commonly taught. I could not find a way to do it unless I had a private helper function in order for the recursion to work. Any ideas suggestions to improve the code for any of the methods is appreciated. Also I know I a missing at least 2 common methods which I think are sInsertAfter and sInsertBefore. Any others?

NoNonFreeSoftwr · Nov 6th 2014

Re: Linked Lists

[FONT=&quot]It looks like it only crashes only if an individual sList Object contains more than about 2500 nodes. I was able to create a total of 25,000,000 sListNode objects contained in 10,000 sList Objects without excel crashing. I would guess that most data structures that use singly linked lists do not put thousands of data points within one sList object.[/FONT]

Code

Sub test3333()


   
  Dim qArr() As sList
  Dim i As Long
  Dim j As Long
  Dim k As Long
   
  k = 10000
   
  ReDim qArr(1 To k)
   
  For i = 1 To k
   
      Set qArr(i) = New sList
      
      For j = 1 To 2500
          
          qArr(i).sInsertFront (CStr(j))
      
      Next j
      
  Next i
   
  Stop
   
  End Sub

Display More

NoNonFreeSoftwr · Nov 6th 2014

Re: Linked Lists

Not sure what happened with the code above, here is the test code

Code

Sub test3333()


Dim qArr() As sList
Dim i As Long
Dim j As Long
Dim k As Long


k = 10000


ReDim qArr(1 To k)


For i = 1 To k


    Set qArr(i) = New sList
    
    For j = 1 To 2500
        
        qArr(i).sInsertFront (CStr(j))
    
    Next j
    
Next i


Stop


End Sub

Display More

NoNonFreeSoftwr · Dec 11th 2014

Re: Linked Lists

I thought I would work on the Linked Lists project tonight and created 1 new method - sReverse. The sReverse method reverse the order of the linked list that sList points to, in other words it just reverse the order of a linked list. Not an easy method to write for some reason.

Code

Sub test()
'This sub tests the sReverse method of the sList class




Dim i As Long
Dim q As sList


Set q = New sList


For i = 1 To 100


    q.sInsertBack (i)
    
Next i


q.sPrintList
q.sReverse
q.sPrintList


End Sub

Display More

Code

Sub sReverse()


'This method reverses a singly linked list
'
'Case - Linked list has 1 or fewer nodes
'    Do nothing, exit method
'
'Case - Linked list has more than 1 node
'    1. Declare a variable called currentNode of type sListNode and point it to the same sListNode object that pHead points to
'    2. Declare a variable nextNode of type sListNode and point it to the Next field of the sListNode object that pHead points to
'    3. Declare a variable loopNode of type sListNode, point it to Nothing
'    4. While nextNode is not Nothing
'        4.1 currentNode.next = loopNode
'        4.2 loopNode = currnentNode
'        4.3 currentNode = nextNode
'        4.4 nextNode = nextNode.next
'    5. Set pHead to point to currentNode
'    6. Set the Next of the sListNode object that pHead points to to be loopNode


Dim currentNode As sListNode
Dim nextNode As sListNode
Dim loopNode As sListNode


Set currentNode = pHead
Set nextNode = pHead.sGetNext
Set loopNode = Nothing


If pSize <= 1 Then
    Exit Sub
End If




Do While Not nextNode Is Nothing


    Set currentNode.sSetNext = loopNode
    Set loopNode = currentNode
    Set currentNode = nextNode
    Set nextNode = nextNode.sGetNext


Loop


Set pHead = currentNode
Set pHead.sSetNext = loopNode




End Sub

Display More

NoNonFreeSoftwr · Dec 11th 2014

Re: Linked Lists

Link the the node diargrams for sReverse

https://goblinrefuge.com/media…linked-list-sreversejpg2/

Linked Lists

Participate now!

Share