Deleting a name in a linked list without a last node pointer

[RedArmy]

Alright, so basically, let's say I cant have a pointer to the last node in my linked list, but I still want to be able to remove a student based on a name entered by the user.

Code: here

Student_list is the head of my list, and the rest (curr, prev, next) is pretty obvious. My 2 questions are:

1. What would I replace the two instances of 'last' with in the last part of the function (lines 8 and 9)
2. What would be the best way to cycle through my list to check to see if the name exists, and if not, how to tell the user?

Im guessing for question #2 it would be something like this:

while((curr->name)!=input )
{prev=curr;
curr=curr->next;}

but then how would I notify the user if the name entered does not exist? All my feeble brain could come up with was something like this:

if((curr->next)==NULL&&(curr->name)!=input
cout<<"stuff"

It's relatively easy stuff, but I get easily confused. Any help is appreciated like always, thanks!

 

[mundane]

What do you mean by "cant have a pointer to the last node in my linked list"?
a) Node at the end
b) Your assignment stipulates you can only iterate using a single pointer (curr), and not the two pointer method (curr and prev)
For notification, you can set a boolean flag if the value is found, and check it outside of the iteration loop.

 

[Markbnj]

Alright, so basically, let's say I cant have a pointer to the last node in my linked list, but I still want to be able to remove a student based on a name entered by the user.

It's irrelevant whether you have a pointer to the tail of the list when it comes to searching.

To remove a student from any kind of linked list by name, assuming no index or other external map like a hash table, requires walking the list from head to tail until you find the node containing the name to be removed, or reach the end of the list. If you find the node, you remove it by assigning the value of its "next" reference to the "next" reference of its parent, and then freeing the node from memory, or doing whatever else you need to do with it. If you reach the end of the list you return null or set a flag or do whatever to inform the caller of the failure.

A doubly linked list just makes walking the list in either direction possible, and makes certain kinds of insertions and deletions easier to do without walking the whole list. For example, a LIFO queue (a stack) works fine on a singly-linked list with no tail pointer, because inserts/deletes always happen at the head. A FIFO queue requires insertions at the head, and deletions at the tail, so these ops will be much faster using a doubly linked list and a tail pointer.

Inserts/deletes in the middle of the list have subtler requirements. If you are inserting after a target node then a singly linked list is fine. If you need to insert before a target node a doubly linked list is helpful, but not mandatory (generally you can make the data structure simpler and smaller, but the code that operates on it more complicated, or vice versa).

 

[RedArmy]

Originally posted by: mundane
What do you mean by "cant have a pointer to the last node in my linked list"?
a) Node at the end
b) Your assignment stipulates you can only iterate using a single pointer (curr), and not the two pointer method (curr and prev)
For notification, you can set a boolean flag if the value is found, and check it outside of the iteration loop.

I mean I can't have a pointer that is pointing to the last node in my list of students, like how I have student_list pointing at the head of my list. I can still use prev and curr, as I have implemented them already in many other parts of the program.

Originally posted by: Markbnj

Alright, so basically, let's say I cant have a pointer to the last node in my linked list, but I still want to be able to remove a student based on a name entered by the user.

It's irrelevant whether you have a pointer to the tail of the list when it comes to searching.

Yeah, I know that I don't need a pointer to the tail of the list but I'm having a hard time finding an example based on the way that I'm doing it to really help me see how it's done. I understand the methodology behind it all and how it all works but it was always based on having a pointer to the tail.

 

[Markbnj]

Yeah, I know that I don't need a pointer to the tail of the list but I'm having a hard time finding an example based on the way that I'm doing it to really help me see how it's done. I understand the methodology behind it all and how it all works but it was always based on having a pointer to the tail.

I guess where I'm having a problem is that you seem to be saying that the method of deleting the node is influenced by whether or not you have a tail pointer. That's true only if you remove from the end of the list. I assume you don't, since you mention searching for a name.

So let's assume you know how to start at the head of the list and walk the "next" pointers from one node to the next. A function to find a name in the list and remove the node might look like this in pseudocode...

node FindNodeByName(name)
begin
  current = head
  parent = null
  while current != null
    if current.name == name
      if parent == null head = current.next
      else parent.next = current.next
      break
    end if
    parent = current
    current = current.next
  end while
  return current
end