• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2892
  • Last Modified:

circular doubly linked list

i need to know how to delete a circular doubly linked list..
ex:

while(front !=0){
node *kil;
kil = front;
;
;// the code here
;
;
;
kil->nrxt = 0;
delete kil;
}
// help pls ...
0
usmanbuxi
Asked:
usmanbuxi
  • 6
  • 4
  • 3
  • +3
1 Solution
 
JoeisanerdCommented:
node *curr;
node *prev;
curr = front;

while( curr!=NULL )
{
  prev = curr;
  curr = curr->next;
  delete prev;
}

Very simple once you see the code.
0
 
ambienceCommented:
well another simple way might be to set the next pointer for the prev node to 0 and then delete the list as if a non-circular one.


curr->prev->next = 0;
while(curr)
{
    p = curr;
    curr = curr->next;
    delete p;
}


0
 
JoeisanerdCommented:
ambience,

That is one extra step that doesn't need to be taken. If you start from one point of a circle and delete a section one by one you will eventually delete the whole thing. When deleting the list you don't need to deal with both directions just one, either the head or tail of the list.

So you can delete from the top to bottom or from bottom to top.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
Mayank SAssociate Director - Product EngineeringCommented:
Since its a circular doubly linked list, let's say that 'ptr' is pointing to the node to be deleted. Let's also assume that 'prev' is the pointer-memeber which points to the previous node and 'next' is the member which points to the next node.

ptr -> prev -> next = ptr -> next ;
ptr -> next -> prev = ptr -> prev ;
delete ptr ;

Mayank.
0
 
SalteCommented:
This will delete the whole list.

struct elem {
   elem * next;
   elem * prev;
   T item;
};

T can be any type, it's the type of list elements or pointer to them.

elem * list;

The list is circular so no node has next == 0. so the first solution here offered by joeisanerd won't work.

This solution removes all elements of the list.

elem * p = list -> next;
while (p != list) {
   elem * q = p;
   p = p -> next;
   delete q;
}
This deletes all elements except 'list'.
delete list;

The main problem with this code is if list is empty, then the list pointer is 0 and so list -> next won't work, so you must test explicitely for an empty list. If the list has a list head this is avoided, in this case you also don't want to remove the head (probably) and so you do not do the final 'delete list' but instead do: list -> next = list -> prev = list; do clean up the list.

Another solution is to simply do what ambience suggested.

list -> prev -> next = 0;

and then delete the list as if it was a regular non-circular one. In this case the next pointer WILL be 0 and a test for NULL or 0 will end the loop.

Alf
0
 
thejeter00Commented:
node *curr;
node *prev;
curr = front;

while( curr!=NULL )
{
 prev = curr;
 curr = curr->next;
 delete prev;
}

//This code wont work because the list is in a circle
try this:
 +search until you find the node you wish to delete
 +node->back = node->front
 +delete node
0
 
JoeisanerdCommented:
If you try the code on a doubly linked list it will work. If you deallocate the memory for a node then when you come back around the list it will point to null! It doesn't matter if it is double-linked list or single-linked list it will do the job.

thejeter00,
  He asked if how to delete the entire list, not one element. I am sure he knows how to delete one element, otherwise he would ask.
0
 
JoeisanerdCommented:
Ok the minor error on my part is that in delete the Back pointer of the list should be set to NULL just before the while loop, then it will delete everything properly.
0
 
JoeisanerdCommented:
Node *curr;
Node *prev;
curr = Front;

if( Back!= NULL )
    Back->next = NULL;

while( curr!=NULL )
{
       prev = curr;
       curr = curr->next;
       delete prev;
}
0
 
SalteCommented:
joeisanerd,

you're wrong.

struct node {
  node * next;
};

node * p = new node;
p -> next = new node;
node * q = p -> next;
delete q; // p -> next will NOT be 0, it will point to invalid memory.

If you instead did:
delete p -> next;

will neither set p -> next to 0.

If you did:

delete p -> next;
p -> next = 0;

it will set p -> next to 0.

Learn the language before you try to teach.

Alf
0
 
Mayank SAssociate Director - Product EngineeringCommented:
Hold on a sec.... do you wish to delete an entire circular doubly linked list? I thought you just wished to know about deleting individual nodes.

Anyways, if you wanna delete an entire circular doubly linked list:

// assuming that there is no header-node

Let's say 'start' points to the first node. 'ptr' and 'temp' are also pointers of the structure-type.

for ( ptr = start -> next ; ptr -> next != start ; ptr = ptr -> next )
  ; // end for

// 'ptr' points to the last node

while ( ptr != start )
{
  temp = ptr -> prev ;
  ptr -> prev -> next = ptr -> next ;
  ptr -> next -> prev = ptr -> prev ;
  delete ptr ;
  ptr = temp ;

} // end while

delete ptr ;
start = NULL ;


I guess that should do it.

Mayank.
0
 
ambienceCommented:
To Joisanerd:
how is

>> if( Back!= NULL )  Back->next = NULL;

different from curr->prev->next = 0; except ofcourse the check. I guess to see the point now !

0
 
ambienceCommented:
To Joisanerd:
how is

>> if( Back!= NULL )  Back->next = NULL;

different from curr->prev->next = 0; except ofcourse the check. I guess you see the point now !

0
 
JoeisanerdCommented:
Duh, you are looking at a Node that may or may not exist. If it doesn't exist then you will get a memory access violation! That's what there is a check.

It probably would help to see his link list class because there are few ways to make and maintain the list.

Is usmanbuxi every going to respond to us?
0
 
tinchosCommented:
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:

Answered by: ambience

Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos
EE Cleanup Volunteer

0
 
Mayank SAssociate Director - Product EngineeringCommented:
Please award some points to Alf (Salte) too for the valueable suggestions.
0
 
tinchosCommented:
You're right mayankeagle, but the fact that ambience's answer was fully complete and was the first one made me recommend that his answer was the one to be accepted.

However I recognize Alf's valuable suggestions.
0
 
Mayank SAssociate Director - Product EngineeringCommented:
Ok.... whatever you wish, tinchos.

Cheers!
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 6
  • 4
  • 3
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now