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

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

[byrner]

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.


type LISTNODE;
type LIST is access LISTNODE;
type LISTNODE is record
  TIME: NATURAL;
  NEXT: LIST;
end record;

type LISTPOINTER is record
  DATA: NATURAL;
  HEAD: LIST;
  TAIL: LIST;
  SIZE: NATURAL; --number of nodes in linked list
end record;

NOTE: I am not actually going to delete the last node; I want to move it from the end of one linked list to the 
end of a second one.  I plan to make the second list point to the end of the first list, and then remove the 
link from the first list to that last node.  I do not want to search through the whole list because this 
operation will be performed with up to 8 lists until they are all as close as possible to being the same 
length.  The entire procedure above will then be repeated up to 6000 times, so it would take a while to search 
through the list to find the next to last node in the list each time.

     Any ideas of how this can be done?  Any help would be greatly appreciated!  Thank you.


byrner@db.erau.edu

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

[Fergus Henderson]

byrner <byrner@db.erau.edu> writes:

> 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?

Well, you could always try using doubly-linked lists.

[P.S.  This is more of an algorithms question than an Ada question,
so I have redirected followups to comp.programming.]

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

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

[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