Given node, how can I find the previous node in a single list

Question

Given the current node, how can I find its previous node in a singly linked list. Thank you Logic will do, the code is evaluated. We all know that taking into account the root of the node, you can perform a serial traverse, I want to know if there is a more reasonable way to avoid the additional costs of accessing the network. (suppose there is no access to the root node). Thanks.

Answer 1

You can not.

Single-linked lists, by definition, only associate a node with its successor, and not with its predecessor. Information on the predecessor is missing; even information about whether it exists at all (your node may be the head of the list).

You can use a doubly linked list. You can try to change everything so that the predecessor passes as a parameter in the first place.

You can scan the entire heap looking for an entry that looks like the predecessor of a node with a pointer to your node. (Not a serious offer.)

Answer 2

Scroll through the list from the very beginning until you meet a node whose next link points to your current node.

But if you need to do this, perhaps you should not use only the linked list in the first place.

Answer 3

Assuming you're talking about a direct single list (each node has only a pointer to the "next", etc.), you will have to iterate from the beginning of the list until you find a node that has 'next' equal to your current node. Obviously, this is a slow operation O(n) .

Hope this helps.

Answer 4

Your only option for a singly linked list is a linear search, something like below (Python-like pseudocode):

 find_previous_node(list, node): current_node = list.first while(current_node.next != null): if(current_node.next == node): return current_node else: current_node = current_node.next return null 

Answer 5

Use the nodeAt () method and pass the head, size, and index of the current node.

  public static Node nodeAt(Node head,int index){ Node n=head; for(int i=0;i<index;i++,n=n.next) ; return n; } 

where n returns the node of the predecessor.

Answer 6

This is some hack I discovered while solving the problem (delete every even node in the list)

  internal void DeleteNode(int p) { DeleteNode(head, p); } private void DeleteNode(Node head, int p) { Node current = head; Node prev = null; while (current.next != null) { prev = current; current = current.next; if (current.data == p) { prev.next = current.next; } } } 

Now here, in anticipation, you assign a current, and then move the current to the next, so prev contains the previous node. Hope this helps ...

Answer 7

Here's a little linear search trick: just go to the node or its position whose previous node you are looking for:

 private MyNode findNode(int pos) { //node will have pos=pos-1 pos-- = 1; MyNode prevNode = null; int count = 0; MyNode p = first.next; // first = head node, find it however you want. //this is for circular linked list, you can use first!=last for singly linked list while (p != first) { if (count == pos) { prevNode = p; break; } p = p.next; count++; } return prevNode; } 

Answer 8

 Node* temp = head; Node* prev = head; while(temp !=null && temp->data==key){ prev = temp; temp = temp->next } 

Answer 9

Assuming you are using the direct list associated with the list, your code should look like

 while(node) { previous = node node = node.next // Do what ever you want to do with the nodes }