UMBC CMSC 313 -- Linked List Previous | Next

Linked Lists

Linked lists are are an improvement over arrays and structures. Each element (or node) can be of a different data type. The size is not known in advance, because you can create the nodes dynamically. The disadvantage is to linked lists is there is no random access. You must access the elements sequentially. You can have singly-linked lists, doubly-linked lists, and circular linked lists.

Each node is a structure and must contain one pointer (for singly-linked lists) that will hold the location of the next item in the chain. A pointer is simply a 32-bit value, so it is defined as RESD. Doubly-linked lists will contain a second pointer for the previous item. Some linked lists will simply have another pointer that points to data, while other lists have the data in the node.

It is necessary to have a pointer that points to the first node. However, until the first node is created, we will set it to NULL. That way, we can test the head pointer and if it is NULL, we will set it, otherwise, ignore it.

When you create a node, there is no next, so set the pointer to NULL. That will be our marker for the end of the list. That means you must set the previous node to point to the new node. (Can't do that when there is only one node, so skip that step then.)

When using the linked list, like printing it out, get the address of the beginning node, print its value, and get the next pointer. If it is not null, continue this step, otherwise stop.

Code

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
struc   linklist
	next:	resd	1
	nr:     resd    1
endstruc

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	
%define NULL            0
%define LLSIZE          8
section .data
limit   dd              5
msg     db              'Node contains %d', 10, 0
section .bss
head    resd            1
newItem resd            1

section .text
    global main
    extern printf
    extern malloc

main:
        mov     dword [ head ], NULL        ; start with an empty list
        mov     dword [ newItem ], NULL

        mov     ecx, [ limit ]

makeNode:
        push    ecx
        mov     eax, LLSIZE
        push    eax
        call    malloc                      ; create a node
        add     esp, 4
        pop     ecx
        cmp     dword [ head ], NULL
        jne     notFirst
        mov     [ head ], eax               ; Keep track of where the list starts
       
notFirst:
        mov     ebx, eax                    ; put the address into an index register
        mov     [ ebx ], dword NULL         ; this is the end of the list, so mark it.
        mov     [ ebx + nr ], ecx           ; this is our data
        
        cmp     dword [ newItem ], NULL
        je      notFirst2
        mov     edi, dword [ newItem ]
        mov     dword [ edi + next ], ebx

notFirst2:
        mov     dword [ newItem ], ebx

        loop    makeNode                    ; make next node, if not done yet.

        mov     ecx, dword [ limit ]
        mov	ebx,dword [ head ]
printNode:
        push    ecx
        mov     dword [ newItem ], ebx      
        push    dword [ ebx + nr ]
        push    msg
        call    printf
        add     esp, 8
        mov     ebx, dword [ ebx ]
        pop     ecx
        loop    printNode

done:
        mov     ebx,0   ;successful termination of program
        mov     eax,1   ;system call number (sys_exit)
        int     0x80    ;call kernel

Output

 [~/courses/umbc/CMSC313/spring05/lectures/Lect10/linklist]$ linklist
Node contains 5
Node contains 4
Node contains 3
Node contains 2
Node contains 1

Previous | Next

©2005, Gary L. Burt