Linked lists are a basic data structure used in programs for many different purposes. There are many kinds of linked lists, with variations on the basic idea intended to address performance and functionality issues. The example package shown in this subsection provides a few operations on the simplest possible form of linked lists.

The links in a linked list are formed from a very simple data structured called a pair. A pair is essentially a container with space for exactly two elements. Pairs can be modeled by fixed length records with two slots. When used to implement linked lists, the first slot holds the data for the list entry, and the second slot stores a pointer to the next pair in the list.

The LinkedList package implements an abstract data definition for the pair data structure, and adds some higher level operations on pairs to effect the list abstraction. A linked list is effectively represented by its first pair.

The pair abstract data structure is very simple. It consists of a constructor, pair, and two accessors called head and tail that satisfy the algebraic specification

for each pair p. In addition, there is a distinguished pair nil, satisfying this algebraic relation, that is unequal to any other pair, and satisfies $\mathrm{head}\left(\mathrm{nil}\right)=\mathrm{nil}$, $\mathrm{tail}\left(\mathrm{nil}\right)=\mathrm{nil}$.

Note that linked lists are quite different from the Maple built-in list structures, which are really immutable arrays. Linked lists are best suited for applications in which you want to incrementally build up the list from its members.

Note: Lisp programmers will recognize the pair, head, and tail operations as the more traditional operations known as "cons", "car" and "cdr".

The LinkedList package is implemented as a module containing the primitive operations on pairs, and higher level operations that implement the list abstraction.

macro( _PAIR = `` ): # for nice printing

LinkedList := module()
    description "routines for simple linked lists";
    export
        nil,
        nullp,
        pair,
        head,
        tail,
        list,
        length,
        member,
        reverse,
        append,
        map;
    local
        setup,
        cleanup,
        map1,
        reverse1,
        _PAIR;
    option
        package,
        load = setup,
    unload = cleanup;

    setup := proc()
        global  `type/Pair`, `type/LinkedList`;
        `type/Pair` := '{ _PAIR( anything, anything ),
                          identical( nil ) }';
        `type/LinkedList` := proc( expr )
            if expr = nil then
                true;
            elif type( expr, Pair ) then
                type( tail( expr ), 'LinkedList' );
            else
                false;
            end if;
        end proc;
        userinfo( 1, 'LinkedList',
           "new types `Pair' and `LinkedList' defined" );
        NULL;
    end proc;

    cleanup := proc()
        global  `type/Pair`, `type/LinkedList`;
        userinfo( 1, 'LinkedList',
            "cleaning up global types" );
        `type/Pair` := evaln( `type/Pair` );
        `type/LinkedList` := evaln( `type/LinkedList` );
        NULL;
    end proc;

    pair := ( a, b )
         -> setattribute( '_PAIR'( a, b ), 'inert' );
    head := ( c::Pair )
         -> `if`( c = nil, nil, op( 1, c ) );
    tail := ( c::Pair )
         -> `if`( c = nil, nil, op( 2, c ) );
    nullp := ( pair )
          -> evalb( pair = nil );

    list := proc()
        local   a, L;
        L := nil;
        for a in args do
            L := pair( a, L );
        end do;
    end proc;

    length := proc( lst )
        if nullp( lst ) then
            0;
        else
            1 + length( tail( lst ) );
        end if;
    end proc;

    member := proc( item, lst )
        if nullp( lst ) then
            false;
        elif item = head( lst ) then
            true;
        else
            thisproc( item, tail( lst ) );
        end if;
    end proc;

    map := proc( p, lst )
        if nullp( lst ) then
            nil;
        else
            pair( p( head( lst ) ),
                thisproc( p, tail( lst ) ) );
        end if;
    end proc;

    append := proc( lst1, lst2 )
        if nullp( lst1 ) then
            lst2;
        else
            pair( head( lst1 ),
                thisproc( tail( lst1 ), lst2 ) );
        end if;
    end proc;

    reverse1 := proc( sofar, todo )
        if nullp( todo ) then
            sofar;
        else
            thisproc( pair( head( todo ), sofar ),
                tail( todo ) );
        end if;
    end proc;

    reverse := lst -> reverse1( nil, lst );

    setup();

end module:

Normally, a package definition like this would be entered into a Maple source file using a text editor, or in a worksheet using the Maple graphical user interface. In either case, the definition would then be followed by a call to the savelib procedure using the name of the module as its sole argument:  savelib( 'LinkedList' ).

Evaluating the savelib call saves the module to the first repository found in the global variable libname, or the repository named with the global variable savelibname, if it is defined. (At least one of these must be defined.)

Important: Always ensure that the standard Maple library is write-protected to avoid saving expressions in it. If you accidentally save something to the standard Maple library, you may need to restore the original from the media on which you obtained the Maple software.

The package exports are listed as the exports of the module. A few local variables are used to implement the package. The local procedures map1 and reverse1 are part of the package implementation that is not available to users of the package. They are visible only within the module definition. This allows the package author to make improvements to the package without disturbing any code that uses it. If the local procedures reverse1 and map1 were exported (thus, available to users), it would be difficult for the author to replace these routines without breaking existing code that relies upon them.

The package includes two special (local) procedures, setup and cleanup. These are executed, respectively, when the module is first read from a repository, and when the package is either garbage collected or when Maple is about to exit.

The package exports can always be accessed by using the long form of their names.

p := LinkedList:-pair( a, b );

$p≔\left(a\,b\right)$

For consistency with the older table-based package implementations, an indexed notation can also be used.

p := LinkedList[ 'pair' ]( a, b );

$p≔\left(a\,b\right)$

This form requires that the index (in this case, the symbol pair) be protected from evaluation. Indexed notation does not extend to packages with nested subpackages.

To access the package exports interactively, use the with command.

with( LinkedList );

$\left[\mathrm{append}\,\mathrm{head}\,\mathrm{length}\,\mathrm{list}\,\mathrm{map}\,\mathrm{member}\,\mathrm{nil}\,\mathrm{nullp}\,\mathrm{pair}\,\mathrm{reverse}\,\mathrm{tail}\right]$

Note that, since some of the package exports shadow global procedures with the same name, the with command issues warnings. These warnings are normal. They remind you that these names now refer to expressions different from the expressions to which they referred previously. Once the exports of the package LinkedList have been bound, you can call them as you would global Maple routines with those names. Note that you can still access the global version of member, for example, by using the syntax :-member.

use LinkedList in
   member( a, p );
   :-member( a, [ a, b, c, d ] );
end use;

$\mathrm{true}$

$\mathrm{true}$

This is one of the principal advantages of using modules and binding, rather than assignment, to implement packages.

Lists are either built incrementally using the pair export of the package, or by calling the list export.

L := nil:

for i from 1 to 10 do
    L := pair( i, L );
end do;

$L≔\left(1\,\mathrm{nil}\right)$

$L≔\left(2\,\left(1\,\mathrm{nil}\right)\right)$

$L≔\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)$

$L≔\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)$

$L≔\left(5\,\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)$

$L≔\left(6\,\left(5\,\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)\right)$

$L≔\left(7\,\left(6\,\left(5\,\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)\right)\right)$

$L≔\left(8\,\left(7\,\left(6\,\left(5\,\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)\right)\right)\right)$

$L≔\left(9\,\left(8\,\left(7\,\left(6\,\left(5\,\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)\right)\right)\right)\right)$

$L≔\left(10\,\left(9\,\left(8\,\left(7\,\left(6\,\left(5\,\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)\right)\right)\right)\right)\right)$

length( L );

$10$

member( 3, L );

$\mathrm{true}$

member( 100, L );

$\mathrm{false}$

reverse( L );

$\left(1\,\left(2\,\left(3\,\left(4\,\left(5\,\left(6\,\left(7\,\left(8\,\left(9\,\left(10\,\mathrm{nil}\right)\right)\right)\right)\right)\right)\right)\right)\right)\right)$

sqL := map( x -> x^2, L );

$\mathrm{sqL}≔\left(100\,\left(81\,\left(64\,\left(49\,\left(36\,\left(25\,\left(16\,\left(9\,\left(4\,\left(1\,\mathrm{nil}\right)\right)\right)\right)\right)\right)\right)\right)\right)\right)$

member( 100, sqL );

$\mathrm{true}$

L2 := list( a, b, c, d );

$\mathrm{L2}≔\left(d\,\left(c\,\left(b\,\left(a\,\mathrm{nil}\right)\right)\right)\right)$

map( sin, L2 );

$\left(\sin \left(d\right)\,\left(\sin \left(c\right)\,\left(\sin \left(b\right)\,\left(\sin \left(a\right)\,\mathrm{nil}\right)\right)\right)\right)$

L3 := eval( L2, { a = 1, b = 2, c = 3, d = 4 } );

$\mathrm{L3}≔\left(4\,\left(3\,\left(2\,\left(1\,\mathrm{nil}\right)\right)\right)\right)$

map( evalf[ 10 ], L3 );

$\left(4.\,\left(3.\,\left(2.\,\left(1.\,\mathrm{nil}\right)\right)\right)\right)$