Thread: Circular Lists

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    Circular Lists

    I'd like to figure out the best way to implement a circular list ( assume I'm developing a "generic" circluar list ). I have a few questions:

    1. Is it possible to implement the STL <list> to make it function as a circular list?

    2. If I create my own template circular list should I:

    a. Use a "sentinel" node that head->prev and tail->next point to or,

    b. Have head->prev and tail->next point to each other?

    For my second question, my intuition tells me to implement a sentinel node.

    I'd really like to be able to use the STL <list> though, as that should involve significantly less coding.

    Thoughts?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    how about building a decorator class around std::list which takes over the task of connecting first and last element?

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Maybe I'm misunderstanding what you mean, but you might have trouble coming up with a sentinel value that's valid, when you don't know what the data type is. Also, I'm not sure that using a sentinel node is going to help much; it feels to me that it won't make things any easier, just allow you to forget to check whether the list is empty.

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    For my second question, my intuition tells me to implement a sentinel node.
    If you are creating a sentinal node to end the list at then I cant really see much difference between a circular list and a non circular one.

    I never made a circular list myself, but as a possible break clause maybe you could store the start adress then test if it comes round again, in which can you have gone one full loop.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    how about building a decorator class around std::list which takes over the task of connecting first and last element?
    Yes, I think that sounds good. Custom iterators would also have to be implemented, methinks.

    EDIT:
    There may be a catch though: what does begin() and end() mean for a non-intrusive circular doubly linked list?
    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
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    There may be a catch though: what does begin() and end() mean for a non-intrusive circular doubly linked list?
    That's what led me to the sentinel node idea. My idea is that you simply have an "empty" node that qualifies as both beginning and end.

    So when the list is created initially, you have a node who's prev and next pointers are NULL.

    So what exactly does a "decorator" class encompass? Does it simply take a <list> as it's only argument and go from there?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by dudeomanodude View Post
    So when the list is created initially, you have a node who's prev and next pointers are NULL.
    Can't do that in a circular list. prev and next would have to point to itself.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    My idea is that you simply have an "empty" node that qualifies as both beginning and end.
    Well, you could just return the beginning of the std::list, but the end would have to be one past the end of the std::list... which would be the beginning of the std::list. That would not make it very useful for use with the standard generic algorithms.

    So what exactly does a "decorator" class encompass? Does it simply take a <list> as it's only argument and go from there?
    You could do that. You could also just implement a class template using composition with a std::list<T> as a member.
    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
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Ya know, I'm wondering if it's not just better to write circular functionality into functions as needed.

    Something like this:
    Code:
    someType use_as_circular( std::list<someType>& m_list ){
    
        int a_random_number = get_a_rand( 0, 10 );
        std::list<someType>::iterator it = m_list.begin();
    
        if( !m_list.empty() ){
    
            for( int i = 0; i < a_random_number; i++ ){
    
                ++it;
    
                if( it = m_list.end() ){
    
                    it = m_list.begin();
                }
            }
        }
    
        return *it;
    }
    Sorry, I know that goes against what I said earlier about finding a "generic" solution.
    Last edited by dudeomanodude; 03-04-2008 at 11:58 AM.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by laserlight View Post
    EDIT:
    There may be a catch though: what does begin() and end() mean for a non-intrusive circular doubly linked list?
    That's where the sentinel comes in. Its position is arbitrary. The sentinel itself is end(). The node immediately following the sentinel is begin().

    To maintain circularity, it must be valid to increment the end() iterator. This would take you back to begin() again.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by brewbuck View Post
    That's where the sentinel comes in. Its position is arbitrary. The sentinel itself is end(). The node immediately following the sentinel is begin().

    To maintain circularity, it must be valid to increment the end() iterator. This would take you back to begin() again.
    Ah, now I understand. It seems to me that if a std::list<T> is used, the end() of that linked list can be the sentinel. The custom iterators would have to detect this condition and then perform the loop back to begin().
    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

  12. #12
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    So what does the custom iterator class look like?

    Do I completely drop the STL list's iterators and build my own? This doesn't sound too bad though, as I can easily write my own begin() and end() functions for my custom iterator.

    Hmmmm.... me likes!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    So what does the custom iterator class look like?
    I decided to give it a stab, and here's my incomplete attempt:
    Code:
    #include <iostream>
    #include <list>
    #include <iterator>
    
    template<typename T>
    class circular_list_iterator : public std::iterator<std::forward_iterator_tag, T>
    {
    public:
        circular_list_iterator(std::list<T>& container)
            : container(container), iter(container.begin()) {}
    
        circular_list_iterator(std::list<T>& container, typename std::list<T>::iterator iter)
            : container(container), iter(iter) {}
    
        circular_list_iterator& operator++()
        {
            if (iter != container.end())
            {
                ++iter;
            }
            else
            {
                iter = container.begin();
            }
            return *this;
        }
    
        T operator*()
        {
            return *iter;
        }
    
        bool operator!=(circular_list_iterator rhs) const
        {
            return iter != rhs.iter;
        }
    private:
        std::list<T>& container;
        typename std::list<T>::iterator iter;
    };
    
    template<typename T>
    circular_list_iterator<T> circular_list_end(std::list<T>& container)
    {
        return circular_list_iterator<T>(container, container.end());
    }
    
    int main()
    {
        std::list<int> numbers;
        numbers.push_back(2);
        numbers.push_back(3);
        numbers.push_back(5);
        numbers.push_back(7);
        numbers.push_back(11);
    
        circular_list_iterator<int> i(numbers);
        for (; i != circular_list_end(numbers); ++i)
        {
            std::cout << *i << ' ';
        }
        std::cout << '\n';
    
        ++i; // Loop back to the front.
        for (circular_list_iterator<int> j(i); j != circular_list_end(numbers); ++j)
        {
            std::cout << *j << ' ';
        }
        std::cout << '\n';
    }
    I hope it is on the right track...
    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

  14. #14
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Oh that's really cool! I wouldn't have thought to ONLY implement the iterator, my feeble minded-attempt would have written the iterator into a class circular_list but looking over your example I guess there's really no need.

    Right on laserlight!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  15. #15
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Just a quick question, why the statement:
    Code:
    return *this;
    in the increment operator?

    Nevermind. It's totally necessary. Duh!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. circular linked lists??
    By atif in forum C Programming
    Replies: 3
    Last Post: 04-30-2002, 03:58 AM
  5. circular shift
    By n00bcodezor in forum C Programming
    Replies: 2
    Last Post: 11-20-2001, 03:51 AM