given a node how can I find previous node in a singly linked list

Question

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.

Connective

Code would be appreciated here also to answer the question. – Faintheart

So I see, you wanna know the number of the girl whom you gave your number😂😂 – Draggle

Answer 1

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. You could try to rearrange everything so you have the predecessor passed in as a parameter in the first place.

You could scan the entire heap looking for a record that looks like a predecessor node with a pointer to your node. (Not a serious suggestion.)

Uninstructed

Why are you saying "you can't"?? What's wrong with iterating from the start of the list searching for a node that has 'next' equal to 'current'. If no match is found return NULL or something similar?? – Gusto

"You can't" means "it is not mathematically possible". There is a missing piece of information that can not be recreated. The question (I think) makes it obvious that they don't even have access to the head of the list; so there's no known starting point from which to iterate the way you suggest. – Uninstructed

@Uninstructed , yes there is no root node. – Connective

To follow up on that, if you do have access to the head of the list, then you are able to follow my suggestion to "rearrange everything so you have the predecessor passed in". – Uninstructed

Right, then, I'm sorry helloMaga, but the answer to your question is that that can't be done. – Uninstructed

@hemflit: I find it very hard to believe that someone has a (non-bogus) linked-list container that doesn't allow access to the list head. What would the point of such a container be?? You would only be able to push items onto the list, but never be able to iterate over them... – Gusto

Darren, they are not using some library container. They are not even working on the level of containers in this question, but rather on the level of a raw data structure, processing pointers in list nodes directly, in effect coding up the "container" from scratch. They are talking about a point in execution where not the whole list is accessible, but only a single node and everything that can be found from that node. Otherwise the question would be "given a list", not "given the current node". – Uninstructed

Answer 2

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

Hogfish

This should be the accepted answer. Everyone else seems to forget that the head is NOT accessible, only a node is given. However, one thing to note here, this solution will not work if the given node is the Tail of the singly-linked list. – Diffract

This is approach works – Beaut

Answer 3

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

But if you need to do this, perhaps you oughtn't be using a singly linked list in the first place.

Boniface

Answer 4

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

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

Serle

Answer 5

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

Hope this helps.

Gusto

Answer 6

Keep two-pointer(curr, prev) initially both will point to head of the list.

do a loop on the list until you either reach at the end of the list or at the required node.

for each iteration move curr node to the next of it but before moving to next store its pointer in prev pointer.

    prev = curr; // first store current node in prev
    curr = curr->next // move current to next

at the end of loop prev node will contain previous node.

getPrev(head, key) {    
    Node* curr = head;
    Node* prev = head;
    while(curr !=null && curr->data==key){
        prev = curr;
        curr = curr->next
    }
    return prev
}

Example:

list = 1->5->10->4->3

We want prev node of 4 So key = 4 and head point at 1 here

initially:

• temp will point to 1
• prev will point to 1

iteration 1:

• First, assign prev=temp (prev point to 1)
• move temp; temp->next (temp point to 5)

iteration 2:

• First, assign prev=temp (prev point to 5)
• move temp; temp->next (temp point to 10)

iteration 3:

• First, assign prev=temp (prev point to 10)
• move temp; temp->next (temp point to 4)

iteration 4:

• temp->data == key so it will return out of loop.
• return prev node

Mccafferty

Thank you for this code snippet, which might provide some limited short-term help. A proper explanation would greatly improve its long-term value by showing why this is a good solution to the problem, and would make it more useful to future readers with other, similar questions. Please edit your answer to add some explanation, including the assumptions you've made. – Thomasthomasa

Answer 7

This is some kind of hack which I found out while solving the problem(Delete every even node in a 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 prev you assign the current and then move the current to next thereby prev contains the previous node. Hope this helps...

Denise

Answer 8

You can do it like this.. you can replace the value of current node by value of next node.. and in the next of 2nd last node you can put null. its like delete a element from a string. here is code

void deleteNode(ListNode* node) {
    ListNode *pre=node;
   while(node->next) 
    {
        node->val=node->next->val;
        pre=node;
        node=node->next;
    }
    pre->next=NULL;

}

Guss

Answer 9

Use a nodeAt() method and pass the head,size and the 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.

Blindly

Answer 10

Here is a small trick with linear search: just pass in the node or its position whose previous node you are searching 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;
    }

Rancher

Answer 11

We can traverse through the LinkedList using slow and fast pointers. Let's say

fast pointer fast = fast.next.next

slow pointer slow = slow.next

Slow pointer will be always a previous of the fast pointer, and so we can able to find it.

Lurleen

Answer 12

It can possible to deleteNode if only given node not root or head. How ?

It can achieve by reversing value in node

4-> 2 -> 1 -> 9 given 2 as node to remove. as above other can't access previous node which is correct because singly linked list we don't store predecessor. What can do is swap value of next of give node to given node and change link to next of next of give node

nextNode = node.next  // assigning given node next to new pointer
node.val = nextNode.val // replacing value of given node to nextNode value 
node.next = nextNode.next // changing link of given node to next to next node. 

I tried this approach and its working fine.

Beaut

Answer 13

I don't know if this will help but you can index the your list and every next is the index + 1 and every previous is index - 1

Tabber

Answer 14

assuming you are using forward singly linked list your code should look like

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

Hack

if(node.content == whatINeed) { doSomething(previous.content); }. – Hack