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?

how about building a decorator class around std::list which takes over the task of connecting first and last element?

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.

Quote:

---

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.

Quote:

---

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:

---

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?

Quote:

---

Originally Posted by dudeomanodude

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.

Quote:

---

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.

Quote:

---

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.

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.

Quote:

---

Originally Posted by laserlight

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.

Quote:

---

Originally Posted by brewbuck

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().

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!

Quote:

---

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...

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!

Just a quick question, why the statement:

Code:

---

return *this;

---

in the increment operator?

Nevermind. It's totally necessary. Duh!

A number of minor nits, like the container being not assignable because it has a reference member. Otherwise solid. No reason not to make it bidirectional, though.

However, I object to making the end iterator a part of the cycle. It's error-prone and defeats most use cases of a circular list.

Quote:

---

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.

---

Actually, I suggested that "feeble minded-attempt" to you :o
I was just lazy to do forwarding so I decided to extend the std::list interface instead :p

By the way, there's a bug even with my incomplete implementation: operator* should return a T& not a T.

Also, since std::list is a doubly linked list, circular_list_iterator probably should be a bidirectional iterator instead of a forward iterator, so change the iterator tag and implement the various operators :)

Quote:

---

Originally Posted by CornedBee

However, I object to making the end iterator a part of the cycle. It's error-prone and defeats most use cases of a circular list.

---

So you just drop the function circular_list_end(), because there's simply no explicit need to know what's the end of the list for the user?

Did I get that right?

Quote:

---

Originally Posted by CornedBee

However, I object to making the end iterator a part of the cycle. It's error-prone and defeats most use cases of a circular list.

---

I can imagine a few cases where it could help. In a single thread, the sentinel is not necessary, because you can always tell when you've done a full cycle by checking to see if you come back to the same spot.

But in multithreaded code, you might have one thread cycling through the list while another thread is manipulating it. If the manipulating thread happens to delete the element the cycling thread began at, the cycling thread will get stuck in an infinite loop, thinking it has never come full circle. In that case, you can check for the sentinel to know that you've come to the end.

Quote:

---

Actually, I suggested that "feeble minded-attempt" to you

---

ha ha. Yes, you're right and I'm sorry. I certainly didn't even consider iterators until I was told.

Quote:

---

Originally Posted by dudeomanodude

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?

---

Why woudlyou want to, just make a regular double linked list. Don't rely on teh STL to do everythign for you, especially nto somethign this simple.

Quote:

---

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,

---

This is called the head node or master link.

Quote:

---

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

---

This can be done, but somewhere you need to have a pointer to at least one link in the list. This is usually done with a head node (master link) being a static object. Since you may want the list to contain zero items, the use of a master link eliminates the problem with having an extra variable to coutn the number of memebrs in the link so you dont use a NULL pointer when there are zero.

Quote:

---

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?

---

using the STL for such a simple thing may not actually involve less coding.

Quote:

---

Originally Posted by abachler

Why woudlyou want to, just make a regular double linked list. Don't rely on teh STL to do everythign for you, especially nto somethign this simple.

---

Sure, why write 10 lines of code when you can write 100 lines? And all the effort by the STL designers to ensure the correctness of the data structure is completely valueless. Better to reimplement it yourself, poorly, with dozens of bugs. Programming is all about pointless struggle right?

</sarcasm>

Quote:

---

Why woudlyou want to, just make a regular double linked list. Don't rely on teh STL to do everythign for you, especially nto somethign this simple.

---

Well, look at how many lines of code it took laserlight to do this. Also, the STL is there for us to rely on as C++ programmers. I won't even start to list the number of reasons why you should use the STL...

Quote:

---

Originally Posted by brewbuck

I can imagine a few cases where it could help. In a single thread, the sentinel is not necessary, because you can always tell when you've done a full cycle by checking to see if you come back to the same spot.

But in multithreaded code, you might have one thread cycling through the list while another thread is manipulating it. If the manipulating thread happens to delete the element the cycling thread began at, the cycling thread will get stuck in an infinite loop, thinking it has never come full circle. In that case, you can check for the sentinel to know that you've come to the end.

---

I would make circular_list_begin function - so you always know when you get to the begining of the list, and avoid returning iterator of the end as CornedBee suggested...

When it comes time to decide whether or not to write your own linked-list I now use this as my guide:

Stroustrups's opinion when to hand-code your own list

Quote:

---

Well, look at how many lines of code it took laserlight to do this.

---

Eh, my example is incomplete.

Incidentally, CornedBee has a point. If you want the iterator to be assignable, you probably should store a pointer to the container (but you will not need to manage memory, thankfully). The interface need not be changed, but the implementation will need to be changed.

EDIT:

Quote:

---

I would make circular_list_begin function - so you always know when you get to the begining of the list, and avoid returning iterator of the end as CornedBee suggested...

---

Why would the circular_list_iterator constructors not suffice?

Quote:

---

Eh, my example is incomplete.

---

Even so, it's going to be significantly less code than implementing my own doubly-linked circular list template.

Quote:

---

Originally Posted by dudeomanodude

So you just drop the function circular_list_end(), because there's simply no explicit need to know what's the end of the list for the user?

---

In a circular list, start == end. To fully traverse the list, you do

Code:

---

typedef circular_iterator<std::list<int>::iterator> cilit;
for(cilit start = circular_begin(lst), it = start; it != start; ++it) {
}

---

where lst is a std::list<int> and circular_begin is

Code:

---

template <typename Container>
circular_iterator<typename Container::iterator>
circular_begin(Container &cnt)
{
  return circular_iterator<typename Container::iterator>(
    cnt.begin(), cnt.begin(), cnt.end());
}

template <typename Container>
circular_iterator<typename Container::const_iterator>
circular_begin(const Container &cnt)
{
  return circular_iterator<typename Container::const_iterator>(
    cnt.begin(), cnt.begin(), cnt.end());
}

---

and circular_iterator is

Code:

---

template <class Iterator>
class circular_iterator :
  public boost::iterator_adaptor<
    circular_iterator<Iterator>,
    Iterator
  >
{
  typedef circular_iterator::iterator_adaptor_ base_type;
  struct enabler {};
public:
  circular_iterator(Iterator pos, Iterator start, Iterator stop)
    : base_type(pos), m_begin(start), m_end(stop)
  {}

  template <typename OtherIter>
  circular_iterator(const circular_iterator<OtherIter> &o,
      typename boost::enable_if<
        boost::is_convertible<OtherIter, Iterator>, enabler
      >::type = enabler()
  )
    : base_type(o.base()), m_begin(o.m_begin), m_end(o.m_end)
  {
  }

private:
  friend class boost::iterator_core_access;

  Iterator &mine() { return this->base_reference(); }
  const Iterator &mine() const { return this->base_reference(); }

  Iterator m_begin, m_end;

  void increment() {
    ++mine();
    if(mine() == m_end) {
      mine() = m_begin;
    }
  }

  void decrement() {
    if(mine() == m_begin) {
      mine() = m_end;
    }
    --mine();
  }

  void advance(typename base_type::difference_type n)
  {
    // Tricky.
    typedef base_type::difference_type diff_t;
    diff_t size = m_end - m_begin;
    n &#37;= size;
    if(n < 0) {
      diff_t rem = m_end - mine();
      if(rem <= n) {
        n -= rem;
        mine() = m_begin;
      }
      mine() += n;
    } else {
      diff_t rem = mine() - m_begin;
      if(rem < -n) {
        n += rem;
        mine() = m_end;
      }
      mine() += n;
    }
  }

  template <
    class OtherDerived, class OtherIterator, class V, class C, class R, class D
  >
  typename base_type::difference_type distance_to(
    const boost::iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D>& y) const
  {
    typedef base_type::difference_type diff_t;
    diff_t size = m_end - m_begin;
    diff_t firstoff = m_end - mine();
    diff_t secondoff = m_end - y;
    if(firstoff < secondoff) {
      return secondoff - firstoff;
    } else {
      return firstoff + (size - secondoff);
    }
  }
};

---

Ah, that was fun.

OK, this code is totally untested, but with the stupid errors fixed, it should work for every container that provides at least forward iterators, automatically adopting greater capabilities as they are available. In other words, you can use this as a circular iteration adapter for slist, list, deque, vector, whatever you want.

Quote:

---

Originally Posted by brewbuck

But in multithreaded code, you might have one thread cycling through the list while another thread is manipulating it. If the manipulating thread happens to delete the element the cycling thread began at, the cycling thread will get stuck in an infinite loop, thinking it has never come full circle. In that case, you can check for the sentinel to know that you've come to the end.

---

If you want to make a full circle and another thread modifies the list, you've got bigger fish to fry.

The primary use case for circular structures is a producer/consumer scheme with a typically fixed buffer size, where the consumer basically chases the producer round and round the circle.
The important thing here is that the code using the circular structure doesn't care for the "start". It's circular, it doesn't need one. The start is where the producer starts when the structure is newly created, nothing more. It could be an arbitrary position.
No, what the client code cares about is that, if it knows there's 4 free places ahead, it can perform an operation these places, without worrying about the "hole" the sentinel creates.

It's like a ring walkway with a built-in trap. "Don't step on this floorti-ARRGH!"


Hey, abachler! 86 lines and I've got a circular structure for every imaginable backing store. How's that for code efficiency?

Quote:

---

Originally Posted by CornedBee

If you want to make a full circle and another thread modifies the list, you've got bigger fish to fry.

---

So if one thread is round-robin scheduling the tasks in the ring buffer while some other thread (or possibly many threads) are constantly adding and removing tasks from the buffer... You don't think that is a realistic situation?

If done cleverly, it can even be done without locking, except in certain boundary cases. This sort of thing is very common in system code.

Quote:

---

Originally Posted by CornedBee

Hey, abachler! 86 lines and I've got a circular structure for every imaginable backing store. How's that for code efficiency?

---

86 lines and i learn jeegabytes of stuffs from it. i hardly use templates and STL and this codes are drowning me.

Quote:

---

Originally Posted by CornedBee

In a circular list, start == end. To fully traverse the list, you do

Code:

---

typedef circular_iterator<std::list<int>::iterator> cilit;
for(cilit start = circular_begin(lst), it = start; it != start; ++it) {
}

---

---

Yeah almost, except that since 'it' is first assigned 'start', and then the loop continuation 'it != start' is evaluated and found to be false, the code in the loop will never be executed.
I find that the only valid way to visit every item in a ring-list is to use both an if-statement and a do-while loop. i.e.

Code:

---

typedef circular_iterator<std::list<int>::iterator> cilit;
if (!lst.empty())
{
    cilit start = circular_begin(lst), it = start;
    do {
        cout << *it << endl;
    } while (++it != start);
}

---

You most certainly cannot use a for_each as I'm sure everybody is aware of already.

Now, as you can guess, I've definitely written one of these before!

Hmm, good point, good point, ...

Wow. I'm not very familiar with boost (they don't really teach you anything about it in school), so it's going to take a while for me to dissect CornedBee's example.

Thank you all. If I take away anything from this discussion, it's the a$$-paddling lesson in generic programming!

BTW: By the time students get to the point I'm at in college, why aren't we taught things like boost? They certainly can't make the claim that boost is non-standard since boost is likely one of the most influential forces in deciding present and future C++ standards. I don't get it...

Quote:

---

Originally Posted by brewbuck

Sure, why write 10 lines of code when you can write 100 lines? And all the effort by the STL designers to ensure the correctness of the data structure is completely valueless. Better to reimplement it yourself, poorly, with dozens of bugs. Programming is all about pointless struggle right?

</sarcasm>

---

<flippant reply>

if it takes you 100 lines fo code to implement a linked list you should go back to Visual Basic...
</flippant reply>

Once you have a LL class not only do you understand what is going on, but you can easily extend it with features specific to the application you are working on at the time. Coding is a learnign process, and its much better/easier to learn from doing than learn from reading someone elses code.

Code:

---

CLinkedLIst* pList = new CLinkedList();

pList->InsertLink(pFoo);

---

Beat that with STL

Quote:

---

Originally Posted by abachler

<flippant reply>

if it takes you 100 lines fo code to implement a linked list you should go back to Visual Basic...
</flippant reply>

---

No, it shouldn't take 100 lines to make a linked-list of whatever you're dealing with. But a template is a little more complicated, since a template should provide all the necessary functionality one would expect of whatever ADT your implementing.

I might only need to create a linked-list with three functions: push_back(), pop_front(), insert() (depending on my specific needs), but this certainly would not be the only functionality one would expect of a generic list.

And with the advent of the STL, it should take ZERO lines to IMPLEMENT a linked-list. This isn't BAD coding or a case of someone NOT knowing how to create a linked-list, it's an issue of helping C++ programmers conform to a standard and doing so in a bug-free/memory-leak-free way.

Quote:

---

if it takes you 100 lines fo code to implement a linked list you should go back to Visual Basic...

---

The problem with an intrusive linked list is that the code has to be rewritten every time it is used. So if you only measure the effort for implementation for a single use, obviously a more general solution would appear to be a waste.

Quote:

---

Coding is a learnign process, and its much better/easier to learn from doing than learn from reading someone elses code.

---

I agree. However, it is much better and easier to use the interface of an existing container than implement such a container yourself.

Quote:

---

Beat that with STL

---

Your implementation is woefully incomplete. It has been beaten before it even got started.

Quote:

---

Beat that with STL

---

Ok, you have 86 lines to implement a singly-linked-list-doubly-linked-list-dynamic-array-queue-dequeue-stack template with circular-functionality.

Let's see your stab at that...

EDIT: you can remove queue and stack from that, I can't think of any reason those two would need circular functionality, but good luck with everything else....

Quote:

---

BTW: By the time students get to the point I'm at in college, why aren't we taught things like boost? They certainly can't make the claim that boost is non-standard since boost is likely one of the most influential forces in deciding present and future C++ standards. I don't get it...

---

You are probably expected to be independent and learn things on your own. Boost is indeed non-standard, even if it was intended to provide libraries that may eventually be standardised.

Quote:

---

You are probably expected to be independent and learn things on your own.

---

that's how we were expected to learn Java, those were good times...

Good point though, I guess my degree is Computer Science, not C++, however it would be nice if we could at least use something like boost when we put together some of our larger projects.

In one of my classes, we've done everything short of building our own graphics library, which, while it has its merits, the code is unusable spaghetti code, so there's the catch... make us take on a crazy project like that (and expecting us to do it in a HORRIBLY wrong implementation to teach us what? that that's probably NOT the best way to do it?) I find a lot of that in school...

But that's a far cry from creating an intrusive list, which you definitely should know how to do, but I was even taught some very bad ways of doing that too...

One teacher thought he'd kill two birds with one stone by teaching us how to make a linked-list by using inheritance, something like:

Code:

---


class Base{

public:

Base(){ next = NULL: }

private:

Base * next;
};

class List : public Base{

public:

List(){ head = NULL; }

private:

Base * head;
};

---

That's incomplete but pretty much how it went (shudders), it's amazing I even know how to program anything, but like you suggested, much of what I've learned, I did so on my own, and with the help of the experts in this forum, so...

Thank you experts!

Quote:

---

The problem with an intrusive linked list is that the code has to be rewritten every time it is used.

---

Dare I point to Boost.Intrusive?

Quote:

---

Dare I point to Boost.Intrusive?

---

Apparently you don't dare, since you did not provide a link :p

I have never heard of it, it does not seem to be listed on Boost (yet), though it certainly seems to exist from a Web search. My guess is that it requires inheritance instead of requiring composition, which in itself implies design trade-offs for classes that use it.

It's not yet in Boost (will be in 1.35).

And it can work with either inheritance or composition.

Quote:

---

Originally Posted by dudeomanodude

I guess my degree is Computer Science, not C++, however it would be nice if we could at least use something like boost when we put together some of our larger projects.

In one of my classes, we've done everything short of building our own graphics library,

---

Wow you have classes doing real projects with real problems and real source code?! Lucky dog!

Quote:

---

Wow you have classes doing real projects with real problems and real source code?! Lucky dog!

---

Real as in they give us an assignment, however when it comes to this graphics API, if it even qualifies as an API, the only REAL reason you might use it would be to get a few REAL laughs.

Quote:

---

It's not yet in Boost (will be in 1.35).

---

Fair enough.

Quote:

---

And it can work with either inheritance or composition.

---

I find the composition option rather interesting.

That said, I think I took abachler's point out of context. He seems to be suggesting reinventing the wheel when the wheel is simple instead of extending the standard library and other existing libraries. In that sense, it is not about intrusive versus non-intrusive linked lists, but about writing your own components from scratch instead of extending existing components.

Quote:

---

Originally Posted by dudeomanodude

Ok, you have 86 lines to implement a singly-linked-list-doubly-linked-list-dynamic-array-queue-dequeue-stack template with circular-functionality.

---

CLinkedList.h

Code:

---

#include <windows.h>
#ifndef CLINKEDLIST_CLASS
#define CLINKEDLIST_CLASS
struct LINK {
    LINK* Prev;
    LINK* Next;
    LPVOID pObject;
    BOOL IsMasterLink;
    };

class CLinkedList {
public:
    LINK* MasterLink;
    CLinkedList();
    ~CLinkedList();
    BOOL Insert(LINK*);
    BOOL Create(LPVOID);
    BOOL Remove(LINK*);
    BOOL Delete(LINK*);
    };
#endif

---

CLinkedList.cpp

Code:

---

#include <windows.h>
#include "CLinkedList.h"
#define MAKE_LINK (LINK*)HeapAlloc(GetProcessHeap() , 0 , sizeof(LINK)
CLinkedList::CLinkedList(){
    this->MasterLink = MAKE_LINK;
    this->MasterLink->IsMasterLink = TRUE;
    this->MasterLink->Next = this->MasterLink;
    this->MasterLink->Prev = this->MasterLink;
    this->MasterLink->pObject = NULL;
    }
CLinkedList::~CLinkedList(){
    LINK* pTemp;
    LINK* pNext;
    pTemp = this->MasterLink->Next;
    while(!pTemp->IsMasterLink){
        pNext = pTemp->Next;
        this->Delete(pTemp);
        pTemp = pNext;
        }
    this->Delete(this->MasterLink);
    }
BOOL CLinkedList::Create(LPVOID pTarget){
    LINK* pTemp;
   
    pTemp = MAKE_LINK;
    pTemp->IsMasterLink = FALSE;
    pTemp->pObject = pTarget;
    return this->Insert(pTemp);
    }
BOOL CLinkedList::Insert(LINK* pLink){
    LINK* pNext = this->MasterLink->Next;
    LINK* pPrev = this->MasterLink;
    pNext->Prev = pLink;
    pPrev->Next = pLink;
    pLink->Next = pNext;
    pLink->Prev = pPrev;
    return TRUE;
    }
BOOL CLinkedList::Delete(LINK* pLink){
    HeapFree(GetProcessHeap() , 0 , pLink->pObject);
    return this->Remove(pLink);
    }
BOOL CLinkedList::Remove(LINK* pLink){
    pLink->Next->Prev = pLink->Prev;
    pLink->Prev->Next = pLink->Next;
    HeapFree(GetProcessHeap() , 0 , pLink);
    return TRUE;
    }

---

83 lines including whitespace which cboard stripped out on paste

Quote:

---

83 lines including whitespace which cboard stripped out on paste

---

Unfortunately, due to the inclusion of <windows.h> it is not portable. It is also error prone since you did not test it (it looks like it is missing return types for some functions, so it may not even compile), unlike existing containers that are well tested. Then, it does not quite fulfill what dudeomanodude challenged since it is not a class template (and not particularly typesafe either, methinks) and only implements linked list functionality.

The argument was templates versus code, it wouldnt really be arguing my point if I then turned around and implemented it as a template now would it. It is perfectly portable, just not copy and paste portable, the only thing it uses from window.h is a few typedef's which can easily fit into the remaining 3 lines plus the 2 saved by removing the include. just replace

Code:

---

#include <windows.h>

---

with

Code:

---

#define BOOL unsigned long
#define TRUE 1
#define FALSE 0

---

I'll definitely give you credit for the attempt.

However there is a catch to this, including windows.h adds how many lines of code underneath? So then what's the difference fundamentally between using borrowed code from the STL, or borrowing code from windows.h?

Either way, you've ended up doing what you originally preached against, borrowing code.

EDIT: for a hypothetical challenge, do like in systems programming, and use no headers of any kind, only core language functionality, in under 86 or 83 lines. I dare anyone out there...

Quote:

---

The argument was templates versus code, it wouldnt really be arguing my point if I then turned around and implemented it as a template now would it.

---

No, the argument is not template versus code.

What's your point? Suppose the standard library containers were not class templates, would you still say "Why woudlyou want to, just make a regular double linked list. Don't rely on teh (standard library) to do everythign for you, especially nto somethign this simple."

Talking about "the STL" is ambiguous: do you really mean the original Standard Template Library, or the parts of the C++ Standard Library that come from the original STL?

Quote:

---

Originally Posted by dudeomanodude

I'll definitely give you credit for the attempt.

However there is a catch to this, including windows.h adds how many lines of code underneath? So then what's the difference fundamentally between using borrowed code from the STL, or borrowing code from windows.h?

Either way, you've ended up doing what you originally preached against, borrowing code.

EDIT: for a hypothetical challenge, do like in systems programming, and use no headers of any kind, only core language functionality, in under 86 or 83 lines. I dare anyone out there...

---

As I stated, the only reason for using window.h was for the BOOL typedef's, which I then prceeded to implement using few enough lines that it woudl still be less than 86 lines. If I wanted to be anal I could of ocurse strip out the whitespace btu I chose to implement it in readable form.

Quote:

---

you have 86 lines to implement a singly-linked-list-doubly-linked-list-dynamic-array-queue-dequeue-stack template with circular-functionality.

---

Well it doesn't do all that. CornedBee's does. That was the original argument.

I can implement a "linked-list", even a template one at that in less than 86 lines, but it doesn't mean it does all of the above.

EDIT: again that is minus queue and stack of course.

You also used LPVOID and HeapAlloc from windows.h, but that's hardly the point.

Here's a point: your class has totally broken copy behaviour.

Here's another: it has a horrible design for the sake of brevity. And it still doesn't support a single block of memory as the underlying storage, or an array of pointers to blocks, or any of this stuff.

Here's a hint:
When you're challanged to, or dared to do something; Do, or do not. There is no 'try'.

Quote:

---

As I stated, the only reason for using window.h was for the BOOL typedef's,

---

Out of curiosity, what's wrong with the built-in bool?

Out of curiosity why do all the normal list operation functions need to return a bool?

Not only bool, but they all seem to return only TRUE for some reason...

However, that list looks completely dysfunctional. How am I supposed to iterate it? Am I really supposed to follow the next and previous pointer myself? Does it look like the brevity comes at the expense of massive amounts of code required by the user to make this class usable for something?

Quote:

---

It is perfectly portable, just not copy and paste portable, the only thing it uses from window.h is a few typedef's

---

I just searched my linux box and, no windows.h found. This == not portable at all.

And if I have to change any line of code in it to make it portable or work for that matter it's useless as a generic solution. Hence the merit of the STL, it's portable, and it works great for you, me or anyone.

Quote:

---

Does it look like the brevity comes at the expense of massive amounts of code required by the user to make this class usable for something?

---

Yea, check out my latest OS:

Code:

---


// USER FILL IN THE BLANKS

---

Oh you are just mad becasue I took yrou challenge and beat it in under 30 minutes. Im really not going to listen to you cry about windows.h when it has already been pointed out that it isnt required.

You haven't beat the challenge. You implemented a buggy and effectively unusable linked list. The challenge was to beat my feat, however.

Buggy how? it compiles on my system just fine. I even made modification's to make it portable, even though that wasnt part of the original challenge. Since noone bothered ot point out the one really obvious bug (caused by a bad copy/past) I can only assume that noone bothered to even attempt to compile it.

I may be mistaken but the Heap functions appear also to come from <windows.h>. Why don't you just stick with malloc and free?

Not sure what this challenge is all about, but your List class only allows you to Create, Insert, Delete and Remove things. As a class it is useless: it doesn't take care of anything behind the back, it is entirely up to the user to provide all functionality and encapsulation to make this even remotely useful. Basically it is up to the user to manage the internals of the list class.

This class design is not really acceptable in C++. You might start by getting acquainted with the private keyword if you want to write anything but plain and messy C with some C++ keywords here and there.

Come on, you are not the only one here who could easily implement a linked list, but you are bragging about a class that has virtually no interface at all. While it may-be took you 20-30 minutes to write, trying to use it in practical programs will inevitably lead to hours of bug-chasing (unless someone takes a few hours and hides the mess behind a nice wrapper).

what anon was hinting about private was this:

In a hypothetical template linked-list class you would make your node struct private, and next (and previous pointers if applicable) private as well. typically the iterator class is part of the public interface. The whole point of the iterators are to provide the user with random access to the list. Lists should (as templates) should not provide any indexing features (like insert at position 6), that's what the iterators are for. The user should decide how they want to use the list, the creator of the list should only provide being able to get to that node by pointing to it through the use of iterators. This is the whole idea in OOP behind encapsulation and information hiding. Like anon or CornedBee (not sure who exactly) pointed out that they shouldn't have to manipulate next and prev pointers to iterate the list (hence the point of iterators).

I don't want to put your effort down however, you know what you're doing, however your attempt simply fails to meet the requirements of a generic solution.

>> Buggy how? it compiles on my system just fine.
What does successful compilation have to do with bugginess? There is one real bug that has already been mentioned.

Quote:

---

Since noone bothered ot point out the one really obvious bug (caused by a bad copy/past) I can only assume that noone bothered to even attempt to compile it.

---

I did point out that it would not compile (at least from my visual inspection, which could be wrong), but I did not notice that you had corrected it soon after.

The reason why I said this is not "templates versus code" is that my point is:

Quote:

---

However, it is much better and easier to use the interface of an existing container than implement such a container yourself.

---