Thread: How to use linked lists / sentinel

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    18

    Question How to use linked lists / sentinel

    Hello, so I am trying to understand what a sentinel is. I got this assignment (under the LIST section) Lists and Vectors

    I do not understand how sentinels work so I am unable to complete the functions... If someone could help me out, thanks

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,577
    The way I read it, a sentinel is a list element that only exists to link to other elements. That way, you avoid NULL root and double pointers.
    Devoted my life to programming...

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    3,472
    I never heard of sentinel being used to name this. I have heard of an empty or fake first node being used by old C link lists.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,745
    It's just
    Code:
    void list_init(struct list *list) {
        list->next = NULL;
        list->data = 0;  // it really doesn't matter!
    }
    
    ...
    
    int main ( ) {
        struct list mylist;
        list_init(&mylist);
    }
    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.

  5. #5
    Registered User
    Join Date
    Nov 2018
    Posts
    18
    I tried to write the second function
    Code:
    int list_is_empty(struct list *list)
    {
        if (list -> next == NULL)
        {
            return 1;
        }
    
    
        return 0;
    }
    However I don't understand for the following functions how I am supposed to write them. How to return the length of the list, excluding the sentinel ? it is not clear to me how I can treat this Thank you for you answers

    Hmm I think I have understood that *list = &sentinel (at the bottom of the LIST paragraph), Is this correct ? Therefore, in each function when we have *list as argument, it is the sentinel's address. Is this correct ?
    Last edited by centrecmercial; 5 Days Ago at 04:10 AM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,147
    Just use a loop to count until you reach a null pointer.
    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

  7. #7
    Registered User
    Join Date
    Nov 2018
    Posts
    18
    I tried to write the third function
    Code:
        size_t list_len(struct list *list){
        size_t i = 0;
    	while (list -> next != NULL)
    		{
    			i += 1;
    		}
    	return i;
    }
    Does this look correct ?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,147
    No, as you do not change list->next, so if it is the case that list->next != NULL, then you will have an infinite loop.
    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

  9. #9
    Registered User
    Join Date
    Nov 2018
    Posts
    18
    Oh yeah right. I need to get list -> next to increment
    Could I do list = list -> next ?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,147
    Does it make sense to you?
    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

  11. #11
    Registered User
    Join Date
    Nov 2018
    Posts
    18
    list->next = list-> next ?? I need to increment the pointer but how ?

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,147
    I didn't say if you're right or wrong. I asked if that made sense to you

    Put it another way: what does list = list->next mean?
    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

  13. #13
    Registered User
    Join Date
    Nov 2018
    Posts
    18
    for me list = list -> next is wrong because "list" has 2 attributes: data and next so we are not changing anything
    how could we make the pointer move on to the next item ? Is it possible ?

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,147
    Quote Originally Posted by centrecmercial
    for me list = list -> next is wrong because "list" has 2 attributes: data and next so we are not changing anything
    Ah ok. We have come to the crux of the matter. I didn't want to tell you yes or no because you need to understand what you're doing, not merely guess at what might work until by chance you get it right and someone tells you that it is correct, even though you have no idea why it is correct.

    list is a pointer. It either points to an object of type struct list, or it could be a null pointer of type struct list. If it points to an object of type struct list, that object could either be the sentinel, or it could be an actual element of the linked list. Despite the name, a struct list object that is an actual element of the linked list is a node in the linked list, not the linked list itself.

    Now, a struct list object has both a pointer to the next struct list object, and the member named data that stores the data of the node. So if you want to traverse the linked list, you need to keep accessing the member named next of the current element so as to get the pointer to the next element. That is what list->next is doing. But then because you need to store it somewhere, and you no longer need list since you have already counted it, you can write list = list->next.
    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

  15. #15
    Registered User
    Join Date
    Nov 2018
    Posts
    18
    hmmmmmmmmmm I see
    So basically list -> next is just accessing the next object in the list. It can be NULL or be existing and have a data attached to it
    So list = list -> next is just storing the pointer of the NEXT element in the list !
    And I can put this in the while loop ? yay

    If this is correct let me try the next function (I like the way you explain because you don't give me the result I have to understand it )

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  3. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 02:49 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM
  5. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 09:45 PM

Tags for this Thread