Linked List Functions

[etow]

Hi

How do you create a linked list, add to linked list, traverse a linked list and delete from linked list?

Thanks

[MichaelW]

http://www.masm32.com/board/index.php?topic=6248.0

[etow]

Hi

I can not get the code to work yet but I have another implementation of doubly linked list below:

Code Select Expand


;The MASM32 Runtime Library include file.
;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    include \masm32\include\masm32rt.inc
;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Listpointer = ^ ListNode

Window Struct
current DD Listpointer
trailing DD Listpointer
Window EndS

ListNode Struct
      entry DD listentry
      nextNode DD Listpointer
      previousNode DD Listpointer
ListNode EndS

ListType Struct
head DD Listpointer
ListType EndS

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

.Code

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    Call Main
    inkey "Press any key to exit..."
    exit
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

CreateList Proc L:ListType
    Mov L.head, NULL
Ret
CreateList EndP
;--------------------------------------------------------------
OnList Proc w:Window, L:ListType
    .If (w != NULL)
       Mov Eax, TRUE
    .ElseIf (w == NULL)
       Mov Eax, FALSE
    .EndIf
Ret
OnList EndP
;---------------------------------------------------------------
InsertNodeAfter Proc current:Listpointer, newNode:ListPointer, L:ListType
.If ((current == NULL) || (newNode == NULL))
print chr$("Error: Attempt to make an incorrect insertion after a node.", 13, 10)
.Else
Mov newNode^.nextNode, current^.nextNode
        Mov current^.nextNode, newNode
.EndIf
Ret
InsertNodeAfter EndP
;-------------------------------------------------------------------
InsertAfter Proc w:Window, x:listentry, L:ListType
   Local newNode:Listpointer
   Local onListResult:BOOLEAN

   Invoke OnList, w, L
   Mov onListResult, Eax

   new (newNode)
   Mov newNode^.entry, x
   .If (L.head == NULL)
      Mov L.head, newNode
      Mov w, newNode
      Mov newNode^.nextNode, NULL
   .ElseIf (onListResult == FALSE)
      print chr$("Error: Attempt to insert after a node not in the list.")
   .ElseIf
      Invoke InsertNodeAfter, w, newNode, L
   .EndIf
Ret
InsertAfter EndP
;----------------------------------------------------------------
InsertNodeBefore Proc current:Listpointer, newNode:ListPointer, L:ListType
Local previous:Listpointer

.If (current == NULL) || (newNode == NULL)
   print chr$("Error: Attempt to insert a nonexistent node before a node.", 13, 10)
    .ElseIf
    Mov previous, current^.previousNode
    Mov current^.previousNode, newNode
    .If previous == NULL
    Mov L.head, newNode
    .ElseIf
    Mov previous^.nextNode, newNode
    .EndIf
    Mov newNode^.nextNode, current
    Mov newNode^.previousNode, previous
    .EndIf
Ret
InsertNodeBefore EndP
;---------------------------------------------------------------
TraverseList Proc L:ListType
    Local current:Window
    Mov current, L.head
    .While current != NULL
       ; visit current^.entry
       Mov current, current^.nextNode
    .EndW
Ret
TraverseList EndP
;----------------------------------------------------------------
Main Proc
   Local Number:DWord
   Local WantContinue:DWord

   Mov WantContinue, 0   ; initialize WantContinue to zero

  .While ((WantContinue >= 0) && (WantContinue < -1))
  ; while WantContinue is greater than or equal to 0 And
  ; WantContinue is less than -1 do

    Mov WantContinue, sval(input("Enter -1 to quit program : "))
    Invoke ClearScreen ; clears the screen
  .EndW
    print chr$(13, 10)
    Ret
Main EndP
End start


[etow]

Hi code that I posted in previous post is a mixture of some assembly and pascal code.

I am not sure how to translate it completely to assembly yet.

I need help.

Thanks

[etow]

Hi

Below is the code to delete from a doubly linked list:

Code Select Expand


DeleteList Proc w:Window, L:ListType
Local onListResult:BOOLEAN

Invoke OnList, w, L
    Mov onListResult, Eax

.If (onListResult == FALSE)
       print chr$("Error: Attempt to delete a node not on list.", 13, 10)
    .ElseIf
      .If (w.current == L.head)
         Mov w.current, w.current ^.nextNode
         Mov L.head, w.current
         Mov trailing, NULL
      .ElseIf
      Mov w.current, w.current ^.nextNode
      dispose (w.trailing ^.nextNode)
      Mov w.trailing ^.nextNode, w.current
      .EndIf
    .EndIf

Ret
DeleteList EndP


The code above is a mixture of assembly and pascal code

[etow]

Hi

I need help to correct my code in the previous posts above to make my code work in MASM32 assembly language.

Thanks

[Tedd]

First question: do you understand how to perform those operations on a linked-list by hand? Once you understand it you should find it much easier to do in asm - the only 'complicated' things are the memory allocation and fiddling the pointers.
(Is that your pascal code, or did you find it somewhere? You might find it easier to start over, rather than trying to convert that code.)

[etow]

Hi Ted,

Yes I know how to do linked list by hand.  The code is mostly Pascal that I got from my college text book.

[Tedd]

Okay, then I would start from scratch :P You can refer back to that code and add any of its 'features' once you get something working :wink
Start with a simple node of {value:DWORD,pNext:DWORD} and then write a function - "append(Lst,val)" (where 'Lst' is a pointer to the list you're appending to, and 'val' is the value to append.) This will allocate a new node, set its value, and add the pointer to the end of the list. Once you've got that you can do a "remove" function. And then from there extend to allow insertion, etc. Then add 'pPrev' pointers if you want :wink

[hutch--]

Just to be a barbarian, would it not be easier with the amount of code in the Pascal example to just build a tree ? It would have to be faster than a linked list.

[etow]

Hi Tedd,

When I mean I know how to do the linked list by hand, I am referring to tracing the linked list by hand not so much as implementing it.  I need some help.

Thanks.

[Tedd]

Then you better read up on how a linked list works - once you understand it, you can get coding :P

But, I've started you off (attachment) :wink
I've left the interesting parts for you :bdg When you finish those functions, you can try adding 'pPrev' pointers in, and maintain them.
(If you then keep track of the last item, as well as the first, you can append quickly, and there's a nice shortcut for finding an item at an index past halfway.)

Note: you'll have to use a debugger if you want to see anything happening.


[attachment deleted by admin]

[etow]

Hi Tedd,

In your code in the zip file,

What does this line do, the compiler complains about this line:
"   mov eax,val  "
Does the line above need to be corrected before it can run without errors

Is this the correct code below to print each item in the linked list?

Code Select Expand


LstTraverse Proc Lst:DWord
    Push Ebx
    Mov Ebx, Lst
    Assume Ebx:Ptr NODE

Process:
    print ([Ebx].value)    ; print print the item of the list
    Mov Eax, [Ebx].pNext
    Mov Ebx, Eax
    Test Eax, Eax
    Jnz Process            ; if it is not NULL then continue to process the list

Ret
LstTraverse EndP


Please reply back soon.

Thanks

[Tedd]

Something tells me you haven't really read through the code and understood it - do that first!! (Not just what it does, but how and why it does it.)


"mov eax,val" will get the parameter 'val' into eax - if there is a parameter 'val' for the given function, otherwise it's not needed (and doesn't make sense), but that's what you get for blindly copying and pasting code ::)

If you "push ebx" at the start of a function, you should remember to "pop ebx" at the end :P (Also "assume ebx:nothing" to avoid error messages.)

Otherwise, your "traverse" doesn't look too bad :wink

[etow]

Hi Tedd,

Do you know any good debuggers I could use to trace the pointers because I am having trouble setting the links to the previous pointer of the node as well as writing the Insert procedure?

By the way, how do you set the pointer to always point to the head of the list?

My insert procedure for the linked list is below, can you check if I am on the right track?

Thanks

Code Select Expand


;insert an item into the given list, at a given 'index'
LstInsert Proc Lst:DWord, valu:DWord, i:DWord
    ;* count through the nodes, until you get to node 'i' (first node is node 0)
    ;* create a new node, set its value
    ;* insert the node -- copy node i's pNext into this new node's, then set i's pNext to this node
    Local counter:DWord
    Local current:DWord

    Push Ebx
    Mov Ebx, Lst
    Assume Ebx:Ptr NODE

    Push Edx
    Mov Edx, current
    Assume Edx:Ptr NODE

    Mov counter, 0
    Mov Ecx, i

Process:
    .If (counter == Ecx)
       Jmp done
    .ElseIf
      Mov Eax, [Ebx].pNext       ; get ptr to next
      Mov Ebx, Eax
      Inc counter
      Mov Edi, [Edx].pNext
      Test Eax, Eax
      Jnz Process
    .EndIf

done:
    ;(ebx is now the last item/node)
    ;(so create a new node and append it)
    Invoke GlobalAlloc, GMEM_FIXED, SizeOf NODE      ;new node
    Mov [Ebx].pNext, Edx                            ;add it to the end
    mov ebx,eax
    Mov [Ebx].pNext, Edx                          ;this is the new end of the list
    Mov Eax, valu
    mov [ebx].value,eax                             ;set its value

    assume ebx:nothing
    Pop Ebx
    Assume Edx:Nothing
    Pop Edx
    Ret

LstInsert EndP