Board index » delphi » Delete a node from middle of a linked list

Delete a node from middle of a linked list

Hi Everyone,

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

- Shail

 

Re:Delete a node from middle of a linked list


Quote
shailku...@aol.com (SHAILKUMAR) wrote:
>Hi Everyone,

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

It is often easier to solve a problem like this if you take a
pencil and paper, draw a few pictures or diagrams, use the
pencil as a pointer and walk yourself through the process.
Remember that the consciousness of your program is limited to
the information contained at the tip of your pencil.  ;-)

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.

    ...red

Re:Delete a node from middle of a linked list


In article <19981212022627.23197.00001...@ng-fb1.aol.com>,
shailku...@aol.com says...

Quote
> Hi Everyone,

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

you're in luck, we've just been doing these damn things at college
:o).... well... here goes...

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

Dos Game Development Site
http://www4.ncsu.edu/~jjneely/gdt.html
..learn to make (and help make) a Dos game!..

Re:Delete a node from middle of a linked list


SHAILKUMAR schrieb:
Quote

> Hi Everyone,

> 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

> - Shail

That depends on your implementation.
if you have just pointers to the next
you have to search the element in front of the element you want to
delete and set it NEXT-pointer to the element coming after the one
you delete.

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

Dupe that floppy -- Spread the wealth and copy (Joe Koss)

Re:Delete a node from middle of a linked list


Quote
SHAILKUMAR wrote:
> 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.

Let "q" be a pointer to the node you want to delete, and let "p" be a
pointer to the node "before" (pointing to) it.  So, when you start,
q^.next = p, and p^.next is either nil (i.e. q^ was the last node in the
list) or points to the next node in the list.

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.

     - Rich

Re:Delete a node from middle of a linked list


In article <36764a99.4314...@nntp.ftc-i.net>,

Quote
 <Higgi...@ftc-i.SpAmZaP.net> wrote:

>And a shortcut for a very common special case - If you want to delete the
>current node in a singly linked list in which you know (for sure!) that all the
>list items have the same record structure, store the current record pointer to
>the next record into a temporary variable, store all fields from the next record
>into the current record (copying the forward pointer last), then use the
>originally stored pointer from the temporary variable to dispose of the next
>record.  Much faster than walking a long list, but you do have to be sure all
>records structures are the same.

That is

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.

Osmo

Other Threads