Circular Lists

This is a discussion on Circular Lists within the C++ Programming forums, part of the General Programming Boards category; 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> ...

  1. #46
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by dudeomanodude View Post
    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
    Last edited by abachler; 03-05-2008 at 10:04 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  2. #47
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,935
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #48
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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
    Last edited by abachler; 03-05-2008 at 10:11 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  4. #49
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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...
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  5. #50
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,935
    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?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #51
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by dudeomanodude View Post
    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.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #52
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  8. #53
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #54
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Here's a hint:
    When you're challanged to, or dared to do something; Do, or do not. There is no 'try'.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #55
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #56
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Out of curiosity why do all the normal list operation functions need to return a bool?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  12. #57
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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?
    Last edited by anon; 03-05-2008 at 01:02 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #58
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  14. #59
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    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
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  15. #60
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Page 4 of 5 FirstFirst 12345 LastLast
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, 02:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21