Menu
Given the current node, how can I find its previous node in a Singly Linked List. Thanks. Logic will do , code is appreciated. We all know given a root node one can do a sequential traverse , I want to know if there is a smarter way that avoids sequential access overhead. (assume there is no access to root node) Thanks.
661
You can't. Singly-linked lists by definition only link each node to its successor, not predecessor. There is no information about the predecessor; not even information about whether it exists at all (your node could be the head of the list). You could use a doubly-linked list.
The idea is to traverse the linked list following the below approach: If the list is empty or contains less than 2 elements, return false. Otherwise, check if the current node is the second last node of the linked list or not. That is, if (current_node->next-next == NULL ) then the current node is the second last node.
But if you need to maintain a pointer to the node previous to the current node in your search, a simple way is to check if node->NEXT is the node you're looking for. Then node is your prev , node->NEXT is your current , and node->NEXT->NEXT is your next .
The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.
If you want to delete the current node, you can do that without finding previous node as well.
Python Code:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
@ Delete Node in a Linked List
55
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
