Thread: successor and predecessor in doubly linked list

> for example L = [3, 2, 7, 5, 8]
> if I wanna find successor for 3 it has to be bigger than 3 but smaller than other numbers which is 5.
The question is only meaningful if the list is sorted.

If L = [2, 3, 5, 7, 8] then

Code:

while ( curr && curr->data <= 3 ) {
    curr = curr->next;
}
// if curr is null, you reached the end of the list.
// otherwise, curr is pointing at the 5, which is the next lowest value that's also greater than 3

Originally Posted by Shahiddd

My idea behind this is I look for a number which is larger than users input number but it is smaller than all other numbers.

It sounds pretty straightforward since you already have an idea: what you're doing is finding the least number greater than the given number, so a linear search of the entire linked list should do the job. The catch is that you aren't searching for an exact match, but rather you're searching for the least number that is greater than the given number.

If the linked list is already sorted, then it would of course be easier as Salem described, but if it is unsorted, sorting it first is unnecessary since you'll still need to do a linear search to find the point after the given number (but you can terminate the search immediately).

I already told you: do a linear search of the entire linked list.

If you find this too difficult, try another problem first: find the smallest number in the linked list.

EDIT:
I'd also suggest renaming successor to something like successor_by_value. Normally the term "successor" as used in a linked list would simply refer to the next node, which is another reason why Salem talked about sorting, given what you're trying to find.