Circular Linked List


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 8 of 8

Thread: Circular Linked List

  1. #1
    alfred Guest

    Circular Linked List


    I am trying to implement a circular linked list. I have no idea of how to
    implement it as far as, the number of nodes required and how to link them.
    I know the last node linker must point to null, but I have no idea on how
    to link those node such that they form a circular linked list and how many
    nodes will I need. Any suggestion will be greatly appreciated.

    Thanks,
    alfred

  2. #2
    James Curran Guest

    Re: Circular Linked List

    I wrote an article about that once. In was printed in the June 2000 VC
    Developer's Journal, and is online here:
    http://www.noveltheory.com/Iterators/Iterator_N1.htm

    --
    Truth,
    James Curran
    www.NJTheater.com (Professional)
    www.NovelTheory.com (Personal)
    www.BrandsForLess.Com (Day Job)


    "alfred " <alfredmarte@aol.com> wrote in message
    news:3bd6d979$1@news.devx.com...
    >
    > I am trying to implement a circular linked list. I have no idea of how to
    > implement it as far as, the number of nodes required and how to link them.
    > I know the last node linker must point to null, but I have no idea on how
    > to link those node such that they form a circular linked list and how many
    > nodes will I need. Any suggestion will be greatly appreciated.
    >
    > Thanks,
    > alfred




  3. #3
    Mark C Guest

    Re: Circular Linked List


    Why is everyone so quick to show examples, or offer solutions to questions,
    using STL. I may be mistaken, but I think Alfred's question was about how
    to implement a circular linked list, not how to iterate through one...

    You need to create a linked list (singly or doubly linked), where each node
    has a pointer to the next item in the list (for singly linked), and a pointer
    to the previous item in the list (for doubly linked)...i.e.

    Class CAlfredsNode
    {
    public:
    CAlfredsNode( void )
    {
    m_pPrevNode = NULL;
    m_pNextNode = NULL;
    }
    void SetPrevNode( CAlfredsNode *pNode ){ m_pPrevNode = pNode; }
    CAlfredsNode *GetPrevNode( void ){ return( m_pPrevNode ); }

    void SetNextNode( CAlfredsNode *pNode ){ m_pNextNode = pNode; }
    CAlfredsNode *GetNextNode( void ){ return( m_pNextNode ); }

    private:
    CAlfredsNode *m_pPrevNode;
    CAlfredsNode *m_pNextNode;
    };

    CAlfredsNode *pStartNode = new CAlfredsNode();
    CAlfredsNode *pNode1 = new CAlfredsNode();
    CAlfredsNode *pNode2 = new CAlfredsNode();
    CAlfredsNode *pLastNode = new CAlfredsNode();

    pStartNode->SetNextNode( pNode1 );
    pNode1->SetNextNode( pNode2 );
    pNode2->SetNextNode( pLastNode );
    pLastNode->SetNextNode( pStartNode );

    pStartNode->SetPrevNode( pLastNode );
    pLastNode->SetPrevNode( pNode2 );
    pNode2->SetPrevNode( pNode1 );
    pNode1->SetPrevNode( pStartNode );
    pStartNode->SetPrevNode( pLastNode );

    I've oversimplified the code so you can make some sense of it...
    So the following statements are true...
    pNode1 == pStartNode->GetNextNode();
    pNode2 == pStartNode->GetNextNode()->GetNextNode();
    And a complete circle
    pStartNode == pStartNode->GetNextNode() // pNode1
    ->GetNextNode() // pNode2
    ->GetNextNode() // pLastNode
    ->GetNextNode(); // pStartNode

    Hope this helps...
    Truth,
    Mark
    www.whatsupwiththat - (Professional)
    www.kindofridiculousdontyouthink - (Personal)
    www.areweageekorwhat - (Day Job)

    // A complete circle...
    pStartNode = pStartNode->GetNextNode()->GetNextNode()->GetNextNode()

    "James Curran" <JamesCurran@mvps.org> wrote:
    > I wrote an article about that once. In was printed in the June 2000

    VC
    >Developer's Journal, and is online here:
    >http://www.noveltheory.com/Iterators/Iterator_N1.htm
    >
    >--
    >Truth,
    >James Curran
    >www.NJTheater.com (Professional)
    >www.NovelTheory.com (Personal)
    >www.BrandsForLess.Com (Day Job)
    >
    >
    >"alfred " <alfredmarte@aol.com> wrote in message
    >news:3bd6d979$1@news.devx.com...
    >>
    >> I am trying to implement a circular linked list. I have no idea of how

    to
    >> implement it as far as, the number of nodes required and how to link them.
    >> I know the last node linker must point to null, but I have no idea on

    how
    >> to link those node such that they form a circular linked list and how

    many
    >> nodes will I need. Any suggestion will be greatly appreciated.
    >>
    >> Thanks,
    >> alfred

    >
    >



  4. #4
    James Curran Guest

    Re: Circular Linked List

    Why would anyone would to write their own version of something that's
    already built into the language (except as a homework assignment)?
    What exactly is the *practical* difference between making a circular
    linked link, and circularly iterating through a standard linked list?

    --
    Truth,
    James Curran
    www.NJTheater.com (Professional)
    www.NovelTheory.com (Personal)
    www.BrandsForLess.Com (Day Job)


    "Mark C" <mdcashion@hotmail.com> wrote in message
    news:3bd77791$1@news.devx.com...
    >
    > Why is everyone so quick to show examples, or offer solutions to

    questions,
    > using STL. I may be mistaken, but I think Alfred's question was about how
    > to implement a circular linked list, not how to iterate through one...
    >
    > You need to create a linked list (singly or doubly linked), where each

    node
    > has a pointer to the next item in the list (for singly linked), and a

    pointer
    > to the previous item in the list (for doubly linked)...i.e.
    >





  5. #5
    Mark C Guest

    Re: Circular Linked List


    What if you want to have a linked list of objects that you want to include
    in a DLL, and export it so that other applications can use it? I don't think
    that you can export an STL implementation like this from a DLL, can you?

    "James Curran" <JamesCurran@mvps.org> wrote:
    > Why would anyone would to write their own version of something that's
    >already built into the language (except as a homework assignment)?
    > What exactly is the *practical* difference between making a circular
    >linked link, and circularly iterating through a standard linked list?
    >
    >--
    >Truth,
    >James Curran
    >www.NJTheater.com (Professional)
    >www.NovelTheory.com (Personal)
    >www.BrandsForLess.Com (Day Job)
    >
    >
    >"Mark C" <mdcashion@hotmail.com> wrote in message
    >news:3bd77791$1@news.devx.com...
    >>
    >> Why is everyone so quick to show examples, or offer solutions to

    >questions,
    >> using STL. I may be mistaken, but I think Alfred's question was about

    how
    >> to implement a circular linked list, not how to iterate through one...
    >>
    >> You need to create a linked list (singly or doubly linked), where each

    >node
    >> has a pointer to the next item in the list (for singly linked), and a

    >pointer
    >> to the previous item in the list (for doubly linked)...i.e.
    >>

    >
    >
    >



  6. #6
    James Curran Guest

    Re: Circular Linked List

    Why not? An instantiated template is just a class like any other.

    --
    Truth,
    James Curran
    www.NJTheater.com (Professional)
    www.NovelTheory.com (Personal)
    www.BrandsForLess.Com (Day Job)


    "Mark C" <mdcashion@hotmail.com> wrote in message
    news:3bd84fc1$1@news.devx.com...
    >
    > What if you want to have a linked list of objects that you want to include
    > in a DLL, and export it so that other applications can use it? I don't

    think
    > that you can export an STL implementation like this from a DLL, can you?





  7. #7
    Steve F Guest

    Re: Circular Linked List



    Well yes and no, sure it's a class like any other but it's linkage isn't
    quite the same as most classes. Take the situation where you have 2 dll's
    that use the list template. One dll links to the standard c lib as a static
    library. The other links to the dll version implicitly. Now if a list object
    is passed from one dll to another then modified you'll have problems with
    memory allocation. Speciffically, when deleting an object created in the
    other dll it will not be found in the deleting dll's heap. This is because
    the template is fully compiled and linked in each dll rather than exported
    from a central place. One implimentation winds up linked to the dll crt and
    the other to the static lib crt and they have seperate heaps.

    Steve

    "James Curran" <JamesCurran@mvps.org> wrote:
    > Why not? An instantiated template is just a class like any other.
    >
    >--
    >Truth,
    >James Curran
    >www.NJTheater.com (Professional)
    >www.NovelTheory.com (Personal)
    >www.BrandsForLess.Com (Day Job)
    >
    >
    >"Mark C" <mdcashion@hotmail.com> wrote in message
    >news:3bd84fc1$1@news.devx.com...
    >>
    >> What if you want to have a linked list of objects that you want to include
    >> in a DLL, and export it so that other applications can use it? I don't

    >think
    >> that you can export an STL implementation like this from a DLL, can you?

    >
    >
    >



  8. #8
    James Curran Guest

    Re: Circular Linked List

    How would templates affect this? In your example, A.DLL and B.DLL both use
    a facility to manage a linked-link. This facility can be compiled directly
    into the code, or it can be put into a static linked library, or it can be
    put into a dynamically linked library. Some of those ways it will work, and
    some ways it will not. The fact that the linked list manager is templated
    or not is irrelevant to any of the above scenarios.
    --
    Truth,
    James Curran
    www.NJTheater.com (Professional)
    www.NovelTheory.com (Personal)
    www.BrandsForLess.Com (Day Job)


    "Steve F" <ssfulton@bigfoot.com> wrote in message
    news:3bd9de57$1@news.devx.com...
    >
    >
    > Well yes and no, sure it's a class like any other but it's linkage isn't
    > quite the same as most classes. Take the situation where you have 2 dll's
    > that use the list template. One dll links to the standard c lib as a

    static
    > library. The other links to the dll version implicitly. Now if a list

    object
    > is passed from one dll to another then modified you'll have problems with
    > memory allocation. Speciffically, when deleting an object created in the
    > other dll it will not be found in the deleting dll's heap. This is because
    > the template is fully compiled and linked in each dll rather than exported
    > from a central place. One implimentation winds up linked to the dll crt

    and
    > the other to the static lib crt and they have seperate heaps.
    >
    > Steve
    >
    > "James Curran" <JamesCurran@mvps.org> wrote:
    > > Why not? An instantiated template is just a class like any other.
    > >
    > >--
    > >Truth,
    > >James Curran
    > >www.NJTheater.com (Professional)
    > >www.NovelTheory.com (Personal)
    > >www.BrandsForLess.Com (Day Job)
    > >
    > >
    > >"Mark C" <mdcashion@hotmail.com> wrote in message
    > >news:3bd84fc1$1@news.devx.com...
    > >>
    > >> What if you want to have a linked list of objects that you want to

    include
    > >> in a DLL, and export it so that other applications can use it? I don't

    > >think
    > >> that you can export an STL implementation like this from a DLL, can

    you?
    > >
    > >
    > >

    >




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center