Remove an item from the list

The question was asked: 6 years 7 months ago   views: 6

The function should remove the element structure (unidirectional linear list) ID. Element ID the structure indicated by lid, with keypad to enter the ID of the deleted item id. first - the reference to the first element of the list.
If item with this ID does not exist, the function should return false. The function I've written returns false always, and if the list consists of one item, scolding me for stupid dirty words. What is the reason for her behavior?

bool delel1 (lin* first, int id) {
 lin *cur; 
 pus bool=false;
do {
 if (cur->lid==id) {
 pus=true; break;
} while (cur==NULL);
if (pus==false) cout << "Element exists\n";
else {
 lin* p=cur->next;
 delete cur;
 if (cur==0) {first=0; cur=first;}
return (pus);
Asked: 05-12-2012 в 11:00:16
@Maris Mistral, If you are given a comprehensive answer, mark it as correct (click the check mark next to the selected answer). - 05-12-2012 в 17:51:10

Answers   3


Note on condition :

while (cur==NULL);

I think there should be "!="
Ie, if You don't pass the function the empty list, in the current embodiment, the loop is not executed even once.

Answered: 05-12-2012 в 11:21:29

@Maris Mistral, @margosh exactly point You to one of the errors (typo?).

And yet, if first == NULL , then if (cur->lid==id) all crash down.

Usually I write approximately so

for (pus = false, cur = first; cur; cur = cur->next) {
 if (cur->lid == id) ...

And yet, if You want to change first in the calling program, then it either should be passed by reference, or pass it address. Personally, I prefer pass by reference, not to use it, because in the calling program directly referring to call it is not clear whether the argument to change.

Specifically this fragment I would write this

delel1 (lin **pfirst, int id)
 lin *cur = *pfirst, // element to remove
 *p = NULL; // the element before cur
 while (cur && cur->lid != id) {
 p = cur;
 cur = cur->next;
 if (cur) { // found
 if (p) // and before him there are items in the list
 p->next = cur->next;
 else // he was the first, update the pointer to the list
 *pfirst = cur->next; // if cur was the only one, the list will be empty
 delete cur;
 return true;
 if (*pfirst)
 cout << "Element" << id << "not found\n";
 cout << "List is empty\n";
 return false;

Frankly, not tested, checked only compilation

typedef struct elem {
 struct elem *next;
 int lid;
} lin;

with this announcement lin and

main ()
 lin *first = NULL;


Answered: 05-12-2012 в 12:42:01

IMHO, so pantova. If you understand magic skill is increased by 100.

uint8_t remove_elem(elem ** in, uint32_t id) {

 elem * prev, * first = *in;

 while((prev = first) && (first->lid != id) && ((first = first->next) != NULL)); //magic

 if(!first) return 0;//Can be in 2 cases: 1) we slipped NULL; 2) the element is not stupid.

 if(prev == first) //Found element - he was the first.
 *in = first->next; //move the first element
 else //It is not the first.
 prev->next = first->next; //Throw out the one that is found

 return 1;

Nothing seems to be messed up. About the code from the question of the author - too much of any unnecessary and confusing record. It is necessary to write easier - then easier to understand, is no stranger to writing (p == NULL) etc. in General it is necessary not to be lazy and sit an hour or two on the code to well quite get the task.

Answered: 05-12-2012 в 14:41:52
You have in your first while loop the value of prev is uninitialized. How increased my skill? :-P - 05-12-2012 в 15:57:15
@VladD, skill fell (ibid comment - magic). Initialization is the first assignment, checks its result, if assigned NULL, then the while loop is not executed. @o2n3e, do not say anything, beautiful. Magic is bullshit, but combine with the previous the first is I liked it. - 05-12-2012 в 16:53:48
@avp: and really confused = with == :-) - 05-12-2012 в 17:02:03
But in this bid. If the gash pulec 100500*100500 elements of a list and not using malloc, and id replace affectum, the deletion of the element will fly. Whether the people are not used to the current amd64 virtual addresses can be овер10бит more than he can physically addressing the frame. And what is actually on amd64 managery the pile of random pieces do not need. Toli is left over from last 32битной x86 architecture. In General, it pichalno, stupid, mortal compatibility. - 05-12-2012 в 17:44:21
@o2n3e, are You serious? And if all so will start, swap on a server is enough? And about pageout thought, the OS does not know that the modified pages are no longer needed. Although, maybe I don't understand. You probably want to reuse the similar structures from the pool to purl them on the free list and give-back? - 05-12-2012 в 17:52:41