?
Solved

circular doubly linked list

Posted on 2003-03-17
18
Medium Priority
?
2,886 Views
Last Modified: 2010-08-05
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
Comment
Question by:usmanbuxi
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 4
  • 3
  • +3
18 Comments
 
LVL 9

Expert Comment

by:Joeisanerd
ID: 8156767
node *curr;
node *prev;
curr = front;

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

Very simple once you see the code.
0
 
LVL 22

Accepted Solution

by:
ambience earned 400 total points
ID: 8156872
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
 
LVL 9

Expert Comment

by:Joeisanerd
ID: 8157091
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
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.

 
LVL 30

Expert Comment

by:Mayank S
ID: 8157366
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
 
LVL 12

Expert Comment

by:Salte
ID: 8157994
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
 

Expert Comment

by:thejeter00
ID: 8160493
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
 
LVL 9

Expert Comment

by:Joeisanerd
ID: 8161621
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
 
LVL 9

Expert Comment

by:Joeisanerd
ID: 8161741
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
 
LVL 9

Expert Comment

by:Joeisanerd
ID: 8161856
Node *curr;
Node *prev;
curr = Front;

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

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

Expert Comment

by:Salte
ID: 8165356
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
 
LVL 30

Expert Comment

by:Mayank S
ID: 8165408
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
 
LVL 22

Expert Comment

by:ambience
ID: 8171598
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
 
LVL 22

Expert Comment

by:ambience
ID: 8171599
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
 
LVL 9

Expert Comment

by:Joeisanerd
ID: 8174109
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
 
LVL 9

Expert Comment

by:tinchos
ID: 9502379
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
 
LVL 30

Expert Comment

by:Mayank S
ID: 9505720
Please award some points to Alf (Salte) too for the valueable suggestions.
0
 
LVL 9

Expert Comment

by:tinchos
ID: 9505786
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
 
LVL 30

Expert Comment

by:Mayank S
ID: 9506268
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.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question