linear linked list node delete
-
Given an in-between(any node not at the start and end of the linked list) node within a singly linear linked list, how to delete that node, when head pointer of list is not given?
-
Given an in-between(any node not at the start and end of the linked list) node within a singly linear linked list, how to delete that node, when head pointer of list is not given?
-
If head pointer is not given then you dont have a linked list , In linked list you always keep the head pointer right ?
Think what he meant was that you are given the node to delete and not the head of the list that this node is in...which doesn't make sense. You need the head of a list to delete a node from it because you need to traverse the list find the link before the link to be deleted and then link the previous one with the one after and then free the memory for the link to be deleted... PREV -> TO BE DELETE -> NEXT Unless its a circularly linked list the head is needed. If your situation is a circular list then you can just treat the link to be deleted as the head save it and then traverse the list until u reach the one before it in the list and the do the un-linking that way.
-
Given an in-between(any node not at the start and end of the linked list) node within a singly linear linked list, how to delete that node, when head pointer of list is not given?
You don't have to delete the node, just zero it maintaining the forward link. The exact value you zero it to depends on the implementation of the list. As a special case if it's a circular list you can always start iterating and wait until you hit a node with a next pointer of the element that you want to remove. Incidentally I've noticed from your posts that you're developing an unhealthy fascination with pointers. Start using std::string, std::vector and std::list and a lot of the problems you're having will go away. Pointers and arrays in C++ are really advanced concepts. Cheers, Ash
-
You don't have to delete the node, just zero it maintaining the forward link. The exact value you zero it to depends on the implementation of the list. As a special case if it's a circular list you can always start iterating and wait until you hit a node with a next pointer of the element that you want to remove. Incidentally I've noticed from your posts that you're developing an unhealthy fascination with pointers. Start using std::string, std::vector and std::list and a lot of the problems you're having will go away. Pointers and arrays in C++ are really advanced concepts. Cheers, Ash
Aescleal wrote:
Pointers and arrays in C++ are really advanced concepts.
not really; somewhat obsolete (because of STL), but not advanced.
Watched code never compiles.
-
You don't have to delete the node, just zero it maintaining the forward link. The exact value you zero it to depends on the implementation of the list. As a special case if it's a circular list you can always start iterating and wait until you hit a node with a next pointer of the element that you want to remove. Incidentally I've noticed from your posts that you're developing an unhealthy fascination with pointers. Start using std::string, std::vector and std::list and a lot of the problems you're having will go away. Pointers and arrays in C++ are really advanced concepts. Cheers, Ash
Thanks Ash for the reply. The pointer questions you see in my posts are mostly interview questions I have been asked. Regarding the present question is also asked in interview and my reply was same as your suggestion of using a circular list or provide head to iterate. But I was told to delete the node without using head.
-
Thanks Ash for the reply. The pointer questions you see in my posts are mostly interview questions I have been asked. Regarding the present question is also asked in interview and my reply was same as your suggestion of using a circular list or provide head to iterate. But I was told to delete the node without using head.
In a single-linked list the correct answer is "No, that can't be safely done, unless it's a circular list." It might have been a trick question, as they sometimes want to see if you are confident enough to tell them they are wrong. It's like the common "Critique this code" question, where you are expected to find syntax errors, memory leaks, undefined behaviour, bad practice and so on in a printout of code.
-
Thanks Ash for the reply. The pointer questions you see in my posts are mostly interview questions I have been asked. Regarding the present question is also asked in interview and my reply was same as your suggestion of using a circular list or provide head to iterate. But I was told to delete the node without using head.
Ah, ouch. Pointer and array questions are on my list of danger sign questions. Questions on the list tell me a fair bit about the interviewer and the culture they're working in. My personal list of danger signs include... - pointers and arrays - operating system specific questions - using low level threads and synchronisation objects - asking about certain design patterns (singleton is the real danger sign that they don't understand what they're up to) This lot set the warning bells going that they're either C programmers who don't really get C++ or they've got a huge body of C that they need changing. In either case I'm going to end up frustrated maintaing stuff they've already written or find walls in the way of me being effective. You can use their questions as handles to get a hold of a good impression of the environment you're going to be working in. On the other hand there are some questions, or responses to answers, that show the interviewer and his company are going to be interesting in working for: - writing exception safe and neutral code - writing assignment operators - we've got a lump of rubbish code, how do you find your way around and clean it up? I wouldn't discount people asking danger questions though. Don't be afraid to voice your concerns though. A while back I went for an interview with a security company and I had an online C test before I went to the interview, a paper C test when I got there and then one of the two men that owned the company grilled me about programming in C (and pretty esoteric stuff - precedence, complex declarator syntax without typedefs) for an hour. About 10 minutes into the hour I pointed out to him that I was really a C++ programmer and if he wanted a C programmer I could recommend a few. He laughed and said he was after C++ programmers but he wasn't one himself and was more interested in how I worked out of my depth. After he'd finished with me I had another 2 hours of being asked about C++ and how I'd avoid all the stuff I'd been asked about in the first hour. Anyway my (rambling) point is that an interview is the company's chance to impress you as well as your chance to impress them. Cheers, Ash
-
Ah, ouch. Pointer and array questions are on my list of danger sign questions. Questions on the list tell me a fair bit about the interviewer and the culture they're working in. My personal list of danger signs include... - pointers and arrays - operating system specific questions - using low level threads and synchronisation objects - asking about certain design patterns (singleton is the real danger sign that they don't understand what they're up to) This lot set the warning bells going that they're either C programmers who don't really get C++ or they've got a huge body of C that they need changing. In either case I'm going to end up frustrated maintaing stuff they've already written or find walls in the way of me being effective. You can use their questions as handles to get a hold of a good impression of the environment you're going to be working in. On the other hand there are some questions, or responses to answers, that show the interviewer and his company are going to be interesting in working for: - writing exception safe and neutral code - writing assignment operators - we've got a lump of rubbish code, how do you find your way around and clean it up? I wouldn't discount people asking danger questions though. Don't be afraid to voice your concerns though. A while back I went for an interview with a security company and I had an online C test before I went to the interview, a paper C test when I got there and then one of the two men that owned the company grilled me about programming in C (and pretty esoteric stuff - precedence, complex declarator syntax without typedefs) for an hour. About 10 minutes into the hour I pointed out to him that I was really a C++ programmer and if he wanted a C programmer I could recommend a few. He laughed and said he was after C++ programmers but he wasn't one himself and was more interested in how I worked out of my depth. After he'd finished with me I had another 2 hours of being asked about C++ and how I'd avoid all the stuff I'd been asked about in the first hour. Anyway my (rambling) point is that an interview is the company's chance to impress you as well as your chance to impress them. Cheers, Ash
Thanks Ash and Cool caw for the replies.
-
Ah, ouch. Pointer and array questions are on my list of danger sign questions. Questions on the list tell me a fair bit about the interviewer and the culture they're working in. My personal list of danger signs include... - pointers and arrays - operating system specific questions - using low level threads and synchronisation objects - asking about certain design patterns (singleton is the real danger sign that they don't understand what they're up to) This lot set the warning bells going that they're either C programmers who don't really get C++ or they've got a huge body of C that they need changing. In either case I'm going to end up frustrated maintaing stuff they've already written or find walls in the way of me being effective. You can use their questions as handles to get a hold of a good impression of the environment you're going to be working in. On the other hand there are some questions, or responses to answers, that show the interviewer and his company are going to be interesting in working for: - writing exception safe and neutral code - writing assignment operators - we've got a lump of rubbish code, how do you find your way around and clean it up? I wouldn't discount people asking danger questions though. Don't be afraid to voice your concerns though. A while back I went for an interview with a security company and I had an online C test before I went to the interview, a paper C test when I got there and then one of the two men that owned the company grilled me about programming in C (and pretty esoteric stuff - precedence, complex declarator syntax without typedefs) for an hour. About 10 minutes into the hour I pointed out to him that I was really a C++ programmer and if he wanted a C programmer I could recommend a few. He laughed and said he was after C++ programmers but he wasn't one himself and was more interested in how I worked out of my depth. After he'd finished with me I had another 2 hours of being asked about C++ and how I'd avoid all the stuff I'd been asked about in the first hour. Anyway my (rambling) point is that an interview is the company's chance to impress you as well as your chance to impress them. Cheers, Ash
Aescleal wrote:
Pointer and array questions are on my list of danger sign questions
Well, they'd both be high on my list of questions to ask. Can you grok pointers? You don't have to be a complete C head and do them in your sleep, but if you can't handle the abstract thought needed, then there's little point in wasting any more of each others time. It's one of those "you either get it, or you don't things". In STL, you still have:
iter++;
iter->DoStuff ();which is at the least, pointer-esque. Asking about linked lists was a self contained scenario - and again demonstrates a bit of abstract thinking. As for singleton stuff? My last job wrote software dealing with real physical machines. I used a few singletons. I used it rarely, but it was essential to have the concept. I wouldn't penalise someone if they knew the idea, but not the magic word. Thread safety, exceptions, etc would also make it on my list - I hope that reassures you! Iain.
I am one of "those foreigners coming over here and stealing our jobs". Yay me!