14 Replies - 1793 Views - Last Post: 05 October 2012 - 12:12 PM Rate Topic: -----

#1 yangz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 30-April 10

Generic node?

Posted 02 October 2012 - 10:52 PM

I'm not sure what my teachers mean when he said make the node generic. I'm implementing an array based linked list.
   struct Lnode
	    {
		int item;
		int next;
	    }

Is This A Good Question/Topic? 0
  • +

Replies To: Generic node?

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 02 October 2012 - 10:56 PM

Is this C or C++?

If C, have you covered pointers yet?

If C++, have you covered templates yet?
Was This Post Helpful? 0
  • +
  • -

#3 yangz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 30-April 10

Re: Generic node?

Posted 02 October 2012 - 10:58 PM

C++ and we haven't cover templates yet.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 02 October 2012 - 11:15 PM

Have you covered pointers?
Was This Post Helpful? 0
  • +
  • -

#5 yangz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 30-April 10

Re: Generic node?

Posted 02 October 2012 - 11:18 PM

We've covered pointers. I've actually finished an Linked List implementation using pointers and recursive functions to insert and delete data. I'm just having trouble setting up an array based linked list.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 03 October 2012 - 07:51 AM

One approach to making that node generic without using templates in replacing int item with void * item. Note that with this approach, your linked list node holds a pointer to the actual data rather that holding the actual data.

This post has been edited by Skydiver: 03 October 2012 - 07:52 AM

Was This Post Helpful? 0
  • +
  • -

#7 obviousninja  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 68
  • Joined: 17-February 10

Re: Generic node?

Posted 03 October 2012 - 09:30 AM

casting it to void *, but remember to store what type of variable it is, or otherwise you would never know if the list gets too long.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 03 October 2012 - 09:37 AM

How will storing the variable type help determine if the list is getting too long?
Was This Post Helpful? 0
  • +
  • -

#9 obviousninja  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 68
  • Joined: 17-February 10

Re: Generic node?

Posted 03 October 2012 - 01:34 PM

View PostSkydiver, on 03 October 2012 - 09:37 AM, said:

How will storing the variable type help determine if the list is getting too long?


polymorphic type like void * doesn't set the data type to anything but, well, "void *" and "void *" can be anything. so that means after you cast the item type into void you can cast it back into anything you want. "like a philosopher stone!, except its a fake one, its only for the looks". anyway i digress. for example, initially you have a integer pointer called "intPtr" you cast it into a void *, then you put it into a container struct, without knowing the item type beforehand you would never know what type of variable it is. you may cast it to char * or whatever you want, but by doing so you may lose data, not to mention that sometimes incompatible type will cause errors if you try to dereference it improperly, in the otherword, if you don't know what data type void * is beforehand, you will almost definitely eat errors when you try to run the program.
Was This Post Helpful? 0
  • +
  • -

#10 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1072
  • View blog
  • Posts: 4,532
  • Joined: 09-June 09

Re: Generic node?

Posted 03 October 2012 - 01:59 PM

Quote

but remember to store what type of variable it is, or otherwise you would never know if the list gets too long.

How exactly would you store a type?

The purpose of a generic container is simply ... to make it generic! If client wants to add data to generic container, then it is their responsibility to know what type they are adding/retrieving. If a user wants to add some data, then they should tell the container the size of the data that they are entering

example (in C)
typedef struct Node {
   void *data;
   struct Node *next;
} Node;

void add(Node *head, void *data, int bytes) {
   Node *temp = malloc(sizeof(Node));
   temp->data = malloc(bytes);
   memcpy(temp->data, data, bytes);
   temp->next = head;
   return temp;
}



In C++ however, this type ambiguity can be overcome with templates, which the compiler will generate types at compile time

This post has been edited by jjl: 03 October 2012 - 02:00 PM

Was This Post Helpful? 0
  • +
  • -

#11 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 03 October 2012 - 11:15 PM

View Postobviousninja, on 03 October 2012 - 01:34 PM, said:

View PostSkydiver, on 03 October 2012 - 09:37 AM, said:

How will storing the variable type help determine if the list is getting too long?


polymorphic type like void * doesn't set the data type to anything but, well, "void *" and "void *" can be anything. so that means after you cast the item type into void you can cast it back into anything you want. "like a philosopher stone!, except its a fake one, its only for the looks". anyway i digress. for example, initially you have a integer pointer called "intPtr" you cast it into a void *, then you put it into a container struct, without knowing the item type beforehand you would never know what type of variable it is. you may cast it to char * or whatever you want, but by doing so you may lose data, not to mention that sometimes incompatible type will cause errors if you try to dereference it improperly, in the otherword, if you don't know what data type void * is beforehand, you will almost definitely eat errors when you try to run the program.


You still did not answer the question. How does storing the variable type help determine if the list is getting too long?

For example if I had this these bits of code:
struct Node
{
    void * data;
    int next;
};

const size_t MAX_NODES = 1024;

class GenericList
{
public:
    GenericList()
        : m_firstFree(0)
        , m_head(MAX_NODES)
        , m_type("")
        , m_nodes(MAX_NODES)
    {
        for(size_t i = 0; i < MAX_NODES; i++)
        {
            m_nodes[i].data = nullptr;
            m_nodes[i].next = i + 1;
        }
    }

    void setType(std::string type)
    {
        m_type = type;
    }

    bool IsTooLong()
    {
        // How to implement this using variable type as information?
        return false;
    }

    bool Insert(void * data)
    {
        if (m_firstFree == MAX_NODES)
            return false;

        if (IsListTooLong())
            return false;

        size_t newNode = m_firstFree;
        m_firstFree = nodes[m_firstFree].next;

        m_nodes[newNode].data = data;
        m_nodes[newNode].next = m_head;
        m_head = newNode;

        return true;
    }

private:
    vector<Node> m_nodes;
    size_t m_firstFree;
    int m_head;
    std::string m_type;
};

struct Song
{
    std::string title;
    double duration;
    std::vector<string> artists;
};

class SongList
{
public:
    SongList()
    {
        // obviousninja says I should remember the variable type
        m_list.setType(typeid(Song).name());
    }

    bool Add(const Song & song)
    {
        Song * newSong = new Song;
        *newSong = song;
        return m_list.Add(newSong);
    }

private:
    GenericList m_list;
};

struct Moon
{
    std::string name;
    double radius;
}

struct Planet
{
    std::string name;
    double radius;
    std::vector<Moon> moons;
};

class PlanetList
{
public:
    PlanetList()
    {
        // obviousninja says I should remember the variable type
        m_list.setType(typeid(Planet).name());
    }

    bool Add(const Planet & planet)
    {
        Planet * newPlanet = new Planet;
        *newPlanet = planet;
        return m_list.Add(newPlanet);
    }

private:
    GenericList m_list;
};

int main()
{
    SongList songList;
    Song song;
    song.title = "Build Me Up Buttercup";
    song.duration = 2.9;
    song.artists.push_back("The Foundations");
    songList.Add(song);

    PlanetList planetList;
    Moon phobos = { "Phobos", 11.2 };
    Moon deimos = { "Deimos", 6.3 };
    Planet planet;
    planet.name = "Mars";
    planet.radius = 3389.5;
    planet.moons.push_back(phobos);
    planet.moons.push_back(deimos);
    planetList.Add(planet);

    return 0;
}



Which list is longer? And what constitutes a list being too long based on the variable type? Can you write the code for GenericList::IsTooLong() ? Oh wait, that is a "gimme the codez" question. Can you give an outline on how to determine that a list is too long based on the variable type?

This post has been edited by Skydiver: 03 October 2012 - 11:15 PM

Was This Post Helpful? 0
  • +
  • -

#12 yangz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 30-April 10

Re: Generic node?

Posted 04 October 2012 - 11:34 AM

I need help with the algorithm with my insert function. The inserted item will be link from smallest to biggest.

Quote

PRINT DEBUG===============
index 0 = 10 || Head 0|| freeNode 4 || next 1
index 1 = 6 || Head 0|| freeNode 4 || next 2
index 2 = 5 || Head 0|| freeNode 4 || next 3
index 3 = 7 || Head 0|| freeNode 4 || next 4
index 4 = 0 || Head 0|| freeNode 4 || next 5
index 5 = 0 || Head 0|| freeNode 4 || next 6
index 6 = 0 || Head 0|| freeNode 4 || next 7
index 7 = 0 || Head 0|| freeNode 4 || next 8
index 8 = 0 || Head 0|| freeNode 4 || next 9
index 9 = 0 || Head 0|| freeNode 4 || next -1


It should be

Quote

PRINT DEBUG===============
index 0 = 10 || Head 0|| freeNode 4 || next -1 // since that is the end of the list
index 1 = 6 || Head 0|| freeNode 4 || next 3
index 2 = 5 || Head 2|| freeNode 4 || next 1
index 3 = 7 || Head 0|| freeNode 4 || next 0
index 4 = 0 || Head 0|| freeNode 4 || next 5
index 5 = 0 || Head 0|| freeNode 4 || next 6
index 6 = 0 || Head 0|| freeNode 4 || next 7
index 7 = 0 || Head 0|| freeNode 4 || next 8
index 8 = 0 || Head 0|| freeNode 4 || next 9
index 9 = 0 || Head 0|| freeNode 4 || next -1

so, at the end of all of these insert, head should be 2, and freeNode is 4


const int MAX_LIST = 10;
const int NULL_VALUE = -1;

    struct Inode {
        ListItemType item; //use typedef to define
        ListIndexType next; //use typedef to define
    };
    Inode node[MAX_LIST];

List::List() {
    size = 0;
    freeNode = 0;
    head = -1; // -1 for empty list

    for (int i = 0; i < MAX_LIST; i++) {
        node[i].item = NULL;
        node[i].next = i + 1;
    }
    node[MAX_LIST-1].next = -1; // end of list

}

void List::insert() {
    int newNode = freeNode;
    freeNode = node[freeNode].next;

    // EMPTY list. First insert
    if (head == NULL_VALUE) {
        node[newNode].item = newItem;
        node[newNode].next = -1; // -1 indicate the list ends here.
        head = 0; // head was -1 to begin with
    } else {
        node[newNode].item = newItem;
        node[newNode].next = -1;
    }
}

Was This Post Helpful? 0
  • +
  • -

#13 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 04 October 2012 - 12:26 PM

A minor thing: You should be consistent about using either -1 or NULL_VALUE to indicate the end of the list. Don't flip-flop between them. I recommend using NULL_VALUE since it is more expressive.

Next on line 31, you are assuming that newNode == 0. What if you decided down the road to change your free node list scheme to have the first free node to be in the middle of the array, then you would be hosed.

Next, in your else clause on lines 33-34, you are not doing anything to make sure that your new node becomes part of your existing list. Are you sure the debug output you showed on post #12 matches your code? Your code always sets next to -1, but your output still shows ascending values for the filled nodes.

Now, to your main question. If you need the values maintained in ascending order, you'll have to walk the list until you find the appropriate spot in he list to insert the new node into. Once you find the spot, you pick up a free node and set the item value in it. Then you set the free node's next point to point to the node after the spot. And, lastly, have the node at the spot's next point to your new free node.

The picture in Wikipedia shows this pretty nicely: http://en.wikipedia....ly_linked_lists
Posted Image
Was This Post Helpful? 2
  • +
  • -

#14 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3530
  • View blog
  • Posts: 10,933
  • Joined: 05-May 12

Re: Generic node?

Posted 04 October 2012 - 01:55 PM

Oh, one more thing. Since your nodes are now "generic", the type that is inside your node will either have to support the comparison operators, or you teacher will have to have covered function pointers so that you can compare the value stored in one node versus another value.
Was This Post Helpful? 1
  • +
  • -

#15 yangz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 30-April 10

Re: Generic node?

Posted 05 October 2012 - 12:12 PM

Thank you! That helps a lot. :bigsmile:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1