Thread: Circular Lists

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

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

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?

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

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?

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.

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