OSDev.org

Posted: **Wed Sep 12, 2007 9:09 pm**

i have constructed a "simple" and somewhat incomplete stacklike double linked list class.

#include <stdint.h>
class List_t {
  struct Node_t {
    int32_t N;
    Node_t *Next, *Prew;
    Node_t():Next(0),Prew(0),N(0) {}
    Node_t(Node_t *next,Node_t *prew,int32_t n):Next(next),Prew(prew),N(n) {}
    ~Node_t() {}
  } *Front, *Back;
  public:
    List_t() {}
    List_t(int32_t n) {
      Front = new Node_t(0,0,n);
      Back = Front;
    }
    ~List_t() {}
    void push_back(int32_t n) {
      Back->Next = new Node_t(0,Back,n);
      Back = Back->Next;
    }
    void push_front(int32_t n) {
      Back->Next = new Node_t(Front,0,n);
      Front = Front->Prew;
    }
    void pop_back() {
      if(count() != 0) {
        Back = Back->Prew;
        delete Back->Next;
        Back->Next = 0;
      }
    }
    void pop_front() {
      if(count() != 0) {
        Front = Front->Next;
        delete Front->Prew;
        Back->Prew = 0;
      }
    }
    int32_t get_back() {
      if(count() != 0) return Back->N;
      else return 0;
    }
    int32_t get_front() {
      if(count() != 0) return Front->N;
      else return 0;
    }
    uint32_t count() {
      uint32_t i = 1;
      for(Node_t *temp = Front; temp->Next != 0; temp = temp->Next, i++) {}
      return i;
    }
};

I think i have it under control, however i need to be able to determine if the list is initialized, e.g. i need to get count() to return zero if not.

Im pretty tired and the code might look somewhat scrambled and probably is, but for now i just need to get an answer to that one question.
Allso youll notice that the code isnt commented, but i think it selfexplainatary.

Hope you can help.

Goodnight

Posted: **Thu Sep 13, 2007 12:10 am**

Initialize Front and Back to NULL, then if Front == NULL, Count = 0. An optimization (for speed) you can do is maintain a count variable which you just return on a call to Count. Increment it on each call to push and decrement on a call to pop.

Regards,
John.

Posted: **Thu Sep 13, 2007 9:23 am**

Don't know if this will help, but here's a doubly-linked list I created, the copy constructor should be on page 2:
http://www.osdev.org/phpBB2/viewtopic.php?t=14759

Posted: **Thu Sep 13, 2007 9:31 am**

jnc100 wrote:Initialize Front and Back to NULL, then if Front == NULL, Count = 0. An optimization (for speed) you can do is maintain a count variable which you just return on a call to Count. Increment it on each call to push and decrement on a call to pop.

Regards,
John.

I believe i understand what you mean. Ill should allways have afront/back node initialized to 0, e.g. not used but there?
to take an example i can understand, if count() == 2, then it really should equal 0?

Posted: **Thu Sep 13, 2007 10:10 am**

A revised version which seems to work perfectly:

Code: Select all

#include <stdint.h>

class List_t {

    struct Node_t {
      int32_t N;
      Node_t *Next, *Prew;
      Node_t(Node_t *next,Node_t *prew,int32_t n):Next(next),Prew(prew),N(n) {}
      ~Node_t() {}
    } *Front, *Back;

  public:

    List_t() {

      Front = new Node_t(0, 0, 0);
      Back = new Node_t(0, Front, 0);
      Front->Next = Back;

    }

    ~List_t() {}

    void push_back(int32_t n) {

      Back->Prew = new Node_t(Back, Back->Prew, n);
      Back->Prew->Prew->Next = Back->Prew;

    }

    void push_front(int32_t n) {

      Front->Next = new Node_t(Front->Next, Front, n);
      Front->Next->Next->Prew = Front->Next;

    }

    int32_t pop_back() {

      if(Back->Prew->Prew != 0) {

        int32_t temp = Back->Prew->N;
        Back = Back->Prew;
        delete Back->Next;
        Back->Next = 0;
        Back->N = 0;
        return temp;

      }

      else return -1;

    }

    int32_t pop_front() {

      if(Front->Next->Next != 0) {

        int32_t temp = Front->Next->N;
        Front = Front->Next;
        delete Front->Prew;
        Front->Prew = 0;
        Front->N = 0;
        return temp;

      }

      else return -1;

    }

    uint32_t count() {

      uint32_t i = 0;
      for(Node_t *temp = Front; temp->Next != 0; temp = temp->Next, i++) {}
      return i-1;

    }

};

A few questions reamins:
Error handling. You'll see that i have used return -1 but that doesnt really cut it, how would you normally do this?

Also the pop funciton look like this:

Code: Select all

if(Back->Prew->Prew != 0) { 

        int32_t temp = Back->Prew->N; 
        Back = Back->Prew; 
        delete Back->Next; 
        Back->Next = 0; 
        Back->N = 0; 
        return temp; 

      }

but i rather i looked like this

Code: Select all

if(Back->Prew->Prew != 0) { 

        Back = Back->Prew; 
        delete Back->Next; 
        Back->Next = 0; 
        return Back->Prew->N;
        Back->N = 0; 

      }

but im not sure weather it is "legal" or even works, havent tryed it.
For now i just dont set N to 0, its not that important after all..

Posted: **Thu Sep 13, 2007 7:07 pm**

Wow, sometimes i amaze my self...
Well i looked up "template", have tryed to understand it before, but never really did...

Code: Select all

template<class T> struct Node_t {
    T N;
    Node_t<T> *Next, *Prew;
    Node_t<T>(Node_t<T> *next,Node_t<T> *prew,T n):Next(next),Prew(prew),N(n) {}
    ~Node_t<T>() {}
};
template<class T> class List_t {
    Node_t<T> *Front, *Back;
    unsigned long Count;
  public:
    List_t();
    ~List_t();
    void push_back(T);
    void push_front(T);
    T pop_back();
    T pop_front();
    unsigned long count();
};
template<class T> List_t<T>::List_t():Count(0) {
  Front = new Node_t<T>(0, 0, 0);
  Back = new Node_t<T>(0, Front, 0);
  Front->Next = Back;
}
template<class T> List_t<T>::~List_t() {}
template<class T> void List_t<T>::push_back(T n) {
  Back->Prew = new Node_t<T>(Back, Back->Prew, n);
  Back->Prew->Prew->Next = Back->Prew;
  Count++;
}
template<class T> void List_t<T>::push_front(T n) {
  Front->Next = new Node_t<T>(Front->Next, Front, n);
  Front->Next->Next->Prew = Front->Next;
  Count++;
}
template<class T> T List_t<T>::pop_back() {
  if(Count != 0) {
    Back = Back->Prew;
    delete Back->Next;
    Back->Next = 0;
    return Back->N;
    Count--;
  }
  else return -1;
}
template<class T> T List_t<T>::pop_front() {
  if(Count != 0) {
    Front = Front->Next;
    delete Front->Prew;
    Front->Prew = 0;
    return Front->N;
    Count--;
  }
  else return -1;
}
template<class T> unsigned long List_t<T>::count() {
  return Count;
}

I believe i do now

Posted: **Thu Sep 13, 2007 8:05 pm**

Dammit, count() doesnt work! yes it counts up allright when pushing onto the list, but when popping of again, it doesnt count down!

I cant seem to find the problem...

Posted: **Thu Sep 13, 2007 11:01 pm**

In pop_back and pop_front you're calling return before you're calling count--. So your function is returning, but count is never decrementing.

Posted: **Fri Sep 14, 2007 7:18 am**

of course! doh... thanks

Posted: **Sat Sep 15, 2007 11:54 am**

Zacariaz wrote:of course! doh... thanks

Compiler warnings for the win!

Posted: **Sun Sep 16, 2007 1:35 am**

Candy wrote:
Zacariaz wrote:of course! doh... thanks
Compiler warnings for the win!

care to explain? cant say i understand... i get no warnings

Posted: **Sun Sep 16, 2007 3:32 am**

Zacariaz wrote:
Candy wrote:
Zacariaz wrote:of course! doh... thanks
Compiler warnings for the win!
care to explain? cant say i understand... i get no warnings

Do you compile with -Wall -Wextra? One of them should warn about unreachable code.

Posted: **Sun Sep 16, 2007 1:13 pm**

eh... no, i use blodshed IDE, anyway works now.

Posted: **Sun Sep 16, 2007 3:09 pm**

Zacariaz wrote:i use blodshed IDE

Which, without looking at the documentation, I am quite convinced offers some way to configure the compiler flags being used for building.

Posted: **Sun Sep 16, 2007 3:54 pm**

probably, but eh, you cant know it all, im looking into it, no worrys...

OSDev.org

More linked lists (c++)

More linked lists (c++)