Thread: successor and predecessor in doubly linked list

  1. #1
    Registered User
    Join Date
    Feb 2021
    Posts
    17

    successor and predecessor in doubly linked list

    Hello!

    I was wondering if someone could help with implementation of successor and predecessor in doubly linked list. I have searched everywhere on the internet but have not fould anything useful.
    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. 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.
    Here is how far i've come:

    insert
    Code:
    struct node{
        int data;
        struct node *previous;
        struct node *next;
    };
    struct node *head;
    struct node *current = NULL;
    
    
    struct node* successor(struct node* head, int data){
    
    
        struct node* current = head;
        int curr = current->data;
        int temp;
    
    
        while(current != NULL)
        {
            if(curr > data && curr < max)
            {
                temp = curr;
            }
            current = current->next;
    
    
        }
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,533
    > 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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2021
    Posts
    17
    If the list is unsorted do I have to sort it in ascedning order first before I search for the successor?

  4. #4
    Registered User
    Join Date
    Feb 2021
    Posts
    17
    Any idea?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,275
    Quote 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).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Feb 2021
    Posts
    17
    OK, so how should I do it if the list is unsorted?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,275
    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.
    Last edited by laserlight; 02-22-2021 at 04:55 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Feb 2021
    Posts
    17
    I fixed it, Thank you both for the support!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly Linked List
    By Nicholas Mata in forum C Programming
    Replies: 14
    Last Post: 05-16-2013, 07:03 AM
  2. doubly linked list
    By BEN10 in forum C Programming
    Replies: 4
    Last Post: 07-21-2009, 09:32 AM
  3. doubly linked list
    By bazzano in forum C Programming
    Replies: 5
    Last Post: 04-26-2007, 03:41 AM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Doubly Linked List.. please Help!!
    By ProgrammingDlux in forum C++ Programming
    Replies: 8
    Last Post: 10-24-2004, 08:27 PM

Tags for this Thread