A tip for newbies in data structure design
Memory is cheap, it is not a priority for developers anymore. However, developers trys their best to avoid as much as possible to reserve extra memory for their programs, sometimes it can’t be helped when performance is needed more. When more performance needed, more memory is needed. Speed and memory are vise versa. To increase speed of a program you need extra memory from the RAM. For example, using double linked list is much faster than single linked list, but double linked list reserves extra memory for the extra link each node will have. You don’t have to go through the whole list again to search for a prevoiuse node if its a single linked list. You just use the previouse link and increase the speed of the program.
Look at the following C++ code:
typename <Item class>class node
{
private:
int nodeNumber;
<Item> data;
node *next;
};
For double linked list node you have to add an extra pointer for previouse node:
typename <Item class> class node
{
private:
int nodeNumber;
<Item> data;
node *next;
node *previous;
};
