7.3 Linked Lists

Suppose that we wish to maintain a list of records sorted according to the value of an information field in the records. We may wish to insert a new record at the appropriate point in the list or to delete some record from the list. What data structure should we use? Stacks and queues are inappropriate because they allow records to be inserted or deleted only at the ends of the list. To insert a new record into the middle of a linear array requires a slow, awkward relocation of all records between the insertion point and the end of the array.

An appropriate solution to this problem is the linked list, which, at some cost in memory space, permits lists to be constructed and modified easily. In a linked list, each record contains a link field which holds the address of the next record in the list. The sequencing from one record of the list to the next thus involves accessing the link field of each record, rather than stepping along in linear address space. In this fashion, insertions and deletions of records involve merely resetting of links. Because records may now be located anywhere in the memory space allocated for storage, linked lists are appropriate whenever dynamic storage allocation is needed. Linked lists are not needed for storage of static data (e.g., tables of constants) nor in cases where data arrives in orderly fashion (e.g., data buffers).

To illustrate, consider the list of names given below: Alice is at offset a, Bobby is at b, Cindy is at c, and David is at d. Each cell now has two fields: info and link:

The link field in the last record, David, has a special value `00' to mark the end of the list. We draw this list with an arrow from each link field to the record whose address is stored in this link.

To delete the record Bobby, simply change the link field in the record Alice: (the space used for Bobby is actually saved in another list; see below)

The list now has only three records:

To insert a new record Danny at address g between Cindy and David, merely set the link of Cindy to the address of Danny and the link of Danny to the address of David:

On the PC each link field holds a one-word offset in the Data Segment. Thus if the information fields occupy b bytes, then the length of each record is b+2 bytes. Assume that the link field is located b bytes from the beginning of the record; let us define the constant LINK:

LINK    equ     b

Suppose BX holds the offset of (the first byte of) a record in a linked list. Then [BX+LINK] specifies the link field of this record. To change BX to point to the next record in the list:

        mov     bx, [bx+LINK]

To insert a record whose offset is in SI immediately following the record whose offset is in BX, we do the following:

        mov     ax, [bx+LINK]   ; Copy link
        mov     [bx+LINK], si
        mov     [si+LINK], ax

Before:

After:

When a record is deleted from a linked list, it is prudent to recover the memory allocated to the record, rather than simply disconnecting all links to it. We can organize a linked list of unused records, called the Free Storage List (FSL). To allocate space for a new record, we take a record from the FSL, set up the information fields, and link the new record into the data structure. Let the word variable FSLPtr hold the offset of the record at the head of the FSL. Deletions and insertions on the FSL always occur at its head; since the FSL has the LIFO property, it is really a stack.

Suppose we wish to delete a record R from a linked list. Assume that BX contains the offset of the record immediately preceding R in the list. To delete R, we unlink it from the list and link it onto the head of the FSL:

        mov     si, [bx+LINK]   ; SI = offset of R
        mov     ax, [si+LINK]   ; Delete R from list
        mov     [bx+LINK], ax
        mov     dx, [FSLPtr]    ; Insert R onto FSL
        mov     [FSLPtr], si    ;   as the new head record
        mov     [si+LINK], dx

To allocate space for a new record, we simply unlink the head record of the FSL:

        mov     bx, [FSLPtr]    ; BX = offset of new record
        mov     ax, [bx+LINK]   ; Update FSLPTR
        mov     [FSLPtr], ax

The use of linked lists arose early (1962) in the development of artificial intelligence research. The linked list is a fundamental data structure of the LISP language, which is heavily used for artificial intelligence programming. Many variations on the idea of linked cells have been subsequently introduced. For example, a doubly linked list has both forward and backward links to facilitate searching in the list. The binary trees discussed below also use more than one link per record.