Do you have ideas or better approaches to implement my linked listimplementation?

Discussion in 'C++' started by PowerStudent, Aug 2, 2010.

  1. PowerStudent

    PowerStudent Guest

    PowerStudent, Aug 2, 2010
    #1
    1. Advertising

  2. PowerStudent

    PowerStudent Guest

    Re: Do you have ideas or better approaches to implement my linkedlist implementation?

    P.S. I know I could have used std::list, but I wanted to write my own
    implementation
    PowerStudent, Aug 2, 2010
    #2
    1. Advertising

  3. PowerStudent

    PowerStudent Guest

    Re: Do you have ideas or better approaches to implement my linkedlist implementation?

    I posted my source files already on an other board, but the board
    software destroyed every format I used, so I thought it would be
    better to provide the files via download.

    So here is my source code:
    ---------------
    listEntry.h
    ---------------
    #ifndef __listEntry_H
    #define __listEntry_H
    #define null 0

    #include <memory>
    using namespace std;

    class listEntry
    {

    public:
    static const listEntry empty;

    class iterator
    {
    friend class listEntry;
    public:
    /*
    * purpose: to determine if next() can be savely called
    * (only accurate after first call)
    */
    bool hasNext();

    /*
    * purpose: to set the currentEntry on the next entry in the list
    * returns: current entry
    */
    const listEntry& next();
    protected:
    // only the correspending list shall produce an iterator
    iterator(){}
    iterator(const listEntry &in);
    private:
    const listEntry *currentEntry;
    };

    // to get an iterator of the list which is set on the first entry
    iterator getIteratorInstance() const;

    listEntry(int value);
    listEntry(listEntry const & copy);

    // to determine if the first entry of a is also in this instance
    bool inList(const listEntry& a) const;

    // add the entry a on the last position on the list
    bool addLast(const listEntry& a);

    static listEntry* createArray(int length, int initValue);
    static listEntry* createArray(int length, const listEntry
    &initEntry);

    // appends the list at the end of a copy of this list
    listEntry operator+(const listEntry &in) const;

    // creates a list of entries which are either in this list or in the
    list of the parameter in
    listEntry operator|(const listEntry &in) const;

    // creates a list of entries which are both in this list and in the
    list of the parameter in
    listEntry operator&(const listEntry &in) const;
    private:
    listEntry(){};
    std::auto_ptr<listEntry> next;
    int value;
    };

    #endif


    ------------------
    listEntry.cpp
    ------------------
    #include "listEntry.h"

    using namespace std;

    const listEntry listEntry::empty=listEntry();

    listEntry::iterator::iterator(const listEntry &in)
    {
    currentEntry=&in;
    }


    bool listEntry::iterator::hasNext()
    {
    return currentEntry==null?false:true;
    }


    const listEntry& listEntry::iterator::next()
    {
    const listEntry *value = currentEntry;
    currentEntry=currentEntry->next.get();
    return *value;
    }

    listEntry::iterator listEntry::getIteratorInstance() const
    {
    return iterator(*this);
    }

    listEntry::listEntry(int value):
    next(null)
    {
    this->value=value;
    }

    listEntry::listEntry(listEntry const & copy):
    next(copy.next.get()==null?null:new listEntry(*copy.next))
    {
    value=copy.value;
    }


    bool listEntry::inList(const listEntry& a) const
    {
    if(value==a.value){
    return true;
    } else if(next.get()==null){
    return false;
    }
    return next->inList(a);
    }

    bool listEntry::addLast(const listEntry &a){
    if(next.get()==null){
    next.reset(new listEntry(a.value));
    return true;
    } else {
    return next->addLast(a);
    }
    }

    listEntry* listEntry::createArray(int length, const listEntry
    &initEntry)
    {
    listEntry *result = new listEntry[length];
    for(int i=0; i<length; ++i){
    result.value=initEntry.value;
    if(initEntry.next.get()==null){
    result.next.reset();
    } else {
    result.next.reset(new listEntry(*initEntry.next));
    }
    }
    return result;
    }

    listEntry* listEntry::createArray(int length, int initValue)
    {
    listEntry temp(initValue);
    return createArray(length, temp);
    }

    listEntry listEntry::eek:perator +(const listEntry & in) const
    {
    listEntry result(*this);
    listEntry *curPos=&result;
    while(curPos->next.get()!=null){
    curPos=curPos->next.get();
    }
    curPos->next.reset(new listEntry(in));
    return result;
    }

    listEntry listEntry::eek:perator |(const listEntry &in) const
    {
    listEntry result(*this);

    listEntry::iterator it = in.getIteratorInstance();
    do {
    listEntry curEntry = it.next();
    if(!result.inList(curEntry)){
    result.addLast(curEntry);
    }
    } while(it.hasNext());
    return result;
    }

    listEntry listEntry::eek:perator &(const listEntry &in) const
    {
    listEntry result(-1);
    listEntry::iterator it = in.getIteratorInstance();
    do {
    listEntry curEntry = it.next();
    if(inList(curEntry)){
    result.addLast(curEntry);
    }
    } while(it.hasNext());

    if(result.next.get()==null){
    return listEntry::empty;
    }
    result=*result.next.get();
    return result;
    }

    /*
    * findConnections : (array of connected values) (length of array) ->
    (array of connected values)
    * to determine which values are connected.
    * exemple: connections: {(1-2), (7-4), (5-3), (4-6), (5-2)}
    * result of "findConnections(connections, 5);" : {(1-2-3-5),
    (4-6-7)}
    */
    listEntry* findConnections(listEntry* connections, int length)
    {
    int arrayLength=1;
    listEntry* result=listEntry::createArray(arrayLength, *connections);

    for(int y=1; y<length; ++y){
    bool addNewComponentToResult=true;
    for(int x=0; x<arrayLength; ++x){
    listEntry::iterator it=connections[y].getIteratorInstance();
    do {
    listEntry curEntry = it.next();
    if(result[x].inList(curEntry)){
    result[x]=result[x] | connections[y];
    addNewComponentToResult=false;
    break;
    }
    } while(it.hasNext());
    }
    if(addNewComponentToResult){
    listEntry *temp=listEntry::createArray(++arrayLength,0);
    for(int i=0; i<arrayLength-1; ++i){
    temp=result;
    }
    temp[arrayLength-1]=connections[y];
    delete[] result;
    result=temp;
    }
    }

    return result;
    }

    int main(int argc, char * argv[]){
    listEntry a(0),b(1),c(2),d(3),e(4),ab=a+b, bc=b+c,de=d+e;
    listEntry test[]={ab, bc, a, a, c, c, de};
    listEntry* result = findConnections(test,7);
    return 0;
    }
    PowerStudent, Aug 2, 2010
    #3
  4. PowerStudent

    Öö Tiib Guest

    Re: Do you have ideas or better approaches to implement my linkedlist implementation?

    On 2 aug, 13:06, PowerStudent <> wrote:
    > Hy,
    > I try to get used to the c++ programming language again and I'm
    > currently working on reimplementing different algorithms.
    >
    > I had especially problems with memory allocation while implementing my
    > linked list class.



    > I would like to know, where I could improve my source files or if you
    > have maybe better approaches.


    I think that get rid of that auto_ptr. It feels like being wrong
    there. If you do not then override compiler generated assignment
    operator at least.
    Öö Tiib, Aug 2, 2010
    #4
  5. Re: Do you have ideas or better approaches to implement my linked ?list implementation?

    Yannick Tremblay <> wrote:
    > Good, implementing a link list from scratch is a very useful and
    > worthwhile exercise. Any programmer worth his salt should be able to
    > implement a link list from scratch.


    OTOH, if what you want is to (re)implement std::list, which is actually
    quite an exercise in C++ programming, it can become quite laborious,
    although very didactic (speaking from personal experience).

    Most of the member functions of std::list are relatively easy to
    implement, but some of them can require some thinking, as there's no
    unique "perfect" way of doing it (eg. splicing). And once you get to
    std::list::sort, you are ready for a ride.

    Also you'll learn a lot about allocators and how they are used (if you
    are really replicating std::list faithfully, iow. you want your container
    to be fully STL-compliant). Certainly not beginner C++ programmer stuff.
    Juha Nieminen, Aug 2, 2010
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vicky

    better approaches

    Vicky, Jan 31, 2004, in forum: ASP .Net
    Replies:
    6
    Views:
    368
    Vicky
    Feb 2, 2004
  2. Danno
    Replies:
    29
    Views:
    885
    Jeffrey Schwab
    Sep 16, 2006
  3. shoplifes
    Replies:
    0
    Views:
    306
    shoplifes
    Nov 25, 2007
  4. Patrick Li
    Replies:
    4
    Views:
    124
    Patrick Li
    Aug 10, 2008
  5. Haoqi Haoqi
    Replies:
    4
    Views:
    82
    Haoqi Haoqi
    Oct 24, 2009
Loading...

Share This Page