Re: How: Remove end of Linked List w/ tail pointer?

[mheaney@ni.net (Matthew Heaney)]

In article <65s8gp$pdc@bgtnsc03.worldnet.att.net>, byrner
<byrner@db.erau.edu> wrote:

>Does anybody know of a way to make the TAIL pointer point to the previous
node in the linked list 
>structure defined below without starting at the HEAD and performing a loop
to search through the entire list?  
>Essentially, what I need to do is remove the last node from the list, but
before I do this, I will have to 
>update the TAIL pointer so it points to the node which will be the tail of
the list after I remove the last 
>node (the next to last node)  Is this even possible without searching the
entire list?  I am using Ada95.

The problem is you're using too low level an abstraction.

A list has a pointer to the head of the list; it doesn't have a pointer to
the tail.  If you want that, you need some higher level abstraction,
implemented in terms of a list, that maintains the tail pointer.  This is
how unbounded queues are implemented, ie

private

   type Queue is
      record
         Front, Back : Node_Access;  -- head and tail of list
         Length         : Natural := 0;
      end record;

There's nothing special you need to do to your list to get a pointer to the
tail, just maintain a separate object to store that value.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271