How do I delete a node from the middle of a linked list. The linked list is
neither a stack or  a queue i.e. node can be removed from anywhere.

Thank you, for your attention.

shailku...@aol.com

A double linked list is easiest since the node itself contains
pointers to the nodes on either side.  If I am the mode to be
removed then by setting Left's right to my right and Right's
left to my left effectively removes me from the list.  If I have
no further use, all that remains is to dispose, or otherwise
release me from the heap.

A single linked list is a little harder.  Here you must walk a
temp pointer through the list until you find the node that links
to the node that is to be removed.  To remove the node, set the
temp node's link to that link's link (either temp^.Link :=
Temp^.Link^.Link, or Temp^.Link := NodeToDelete^.Link).  Don't
forget to dispose of the node after its been removed from the
list.

If you design your single linked list so that the link is the
first field in the record you can set the temp pointer to the
address of the list's head pointer and need not have to treat
the first node in the list as a special case.

each element in the linked list should have two parts:

data   - the data you're storing
link   - the pointer to the next item in the list

..so in order to delete an item, you scan through until you find the item
you're after (storing the position of the *previous* item)...  when you
find the item you want, read in the link value from the *current* item
(as a seperate variable).

then, to remove the item from the list, change the 'link' pointer in the
*previous* item to the value of 'link' in the *current* item (which you
are removing).... so the link now skips across the current item...

an eg. will probably help more here..

item    1       2       3       4       5       6       7

data    x       c       b       n       m       l       p      
link    -1      6       2       7       4       5       1

(the -1 indicates the end of the list, 'start' points to 2)...

so, the above list is arrange into alphabetical order (b,c,l,m,n,p,x)
..so remove 'n' you would change the pointer to it (item 5, which points
to 4), to the value stored in 'link' (which is 7 in this case)... so now
item 5 points to 7... e.g.

item    1       2       3       4       5       6       7

data    x       c       b       n       m       l       p      
link    -1      6       2               7       5       1

..and so, n is removed from the list.... if you want to release the space
you will have to add it onto the end of a seperate linked-list which
stores free spaces.... (for adding!)...

hope this is of some help,

martin fitzpatrick

--
Email: poohsti...@pmail.net
ICQ#: 11077801
AOL/CServeIM: Flupert

when you use a double-linked list,
you have to change also the PREV-pointer of the element behind,
setting it to the one in front.

If need the memory later in your program,
you shouldnt forget freeing your deleted pointer
with DisPose.

hth,
Martin

--
E-Mail: Spi...@t-online.de
ICQ   : 16102775

Then:
  p^.next := q^.next;  (* point "around" the deleted node *)
  dispose(q);

Of course, if you had other pointers to the deleted node elsewhere in
the program, you need to handle them appropriately; either set them to
nil or reassign them to poin to some other node.

Procedure Delete(p:pnode);
var nxt:pnode;
begin
  nxt:=p^.next;
  {dispose any sub-structures of p here }
  p^:=nxt^;
  dispose(nxt);
End;  

This, however, does not work for the last node as nxt would be nil.

Of course if one needs to do such deleting then maybe some other
structure like double linked list would be better.