Operations on linked lists

Initialise

    procedure initialise 
      (L    : out link) is
    begin
        L := null;
    end;

Add at start

    new_list := new node'(DATA,null);
    new_list.next := list;
    list := new_list;


    list := new node'(DATA, list);


    procedure prepend 
       (DATA : in datatype ;
       	head : in out link) is
    begin
        head := new node'(DATA, head);
    end;

Traverse a list

use a loop:

• access variable points to each node in turn
• initially set to head of the list
• finish when access variable is null

    P := head;
    while P /= null loop
        ... do something with this node
        P := P.next;
    end loop;

code like this is very common in real programs

Print the list

procedure print_list (head : in link) is
    p : link;
begin
    P := head;
    while P /= null loop
        put (P.data); new_line;
        P := P.next;
    end loop;
end;

An alternative implementation uses recursion:

procedure print_list (head : in link) is
begin
    if head /= null then
        put (head.data); new_line;
        print_list (head.next);
    end if;
end;

Append to list

procedure append
   (data : in datatype;
    head : in out link)
is
    p1, p2 : link;
begin

    if head = null then
        -- list is currently empty
        -- new element becomes the entire list

        head := new node'(data,null);

    else

        -- first we need to find the end of the list
        p1 := head;
        while p1 /= null loop
            p2 := p1;
            p1 := p1.next;
        end loop;

        -- p2 now points to the last element in the list
        -- add new element after p2

        p2.next := new node'(data,null);

    end if;
end append;