I'm trying to create a function that removes the tail of a linked list. I have both a head and tail pointer, so my question is, when I'm trying to remove from the tail, do I still need to traverse the list to remove the node at the tail?
CodePudding user response：
Assuming that your list is a singly linked list, you still need to traverse it, because the second to last element becomes the new tail and it should be updated. So, storing the list's tail, is not a great idea.
Instead, if you have a doubly linked list, you can freed the tail and update it, following the "back link".
CodePudding user response：
As part of removing the node, you need the node preceding the node to remove for two reasons:
tailneeds to be updated to point to it.- Its
nextfield needs to be set toNULL.
Before:
head Node Node Node tail
------ ------- ------- ------- ------
| ------->| -----...-->| ------->| NULL |<------- |
------ | | | | | | ------
| | | | | |
------- ------- -------
After:
head Node Node tail
------ ------- ------- ------
| ------->| -----...-->| NULL |<--------------------- |
------ | | | | ------
| | | |
------- -------
To find this node in a singly-linked list requires traversing the list.
To find this node in a doubly-linked list doesn't require traversing the list.
Before:
head Node Node Node tail
------ ------- ------- ------- ------
| ------->| -----...-->| ------->| NULL |<------- |
------ | NULL |<-...------ |<------- | ------
| | | | | |
------- ------- -------
After:
head Node Node tail
------ ------- ------- ------
| ------->| -----...-->| NULL |<-------------------- |
------ | NULL |<-...------ | ------
| | | |
------- -------