- Joined
- Apr 16, 2012
- Messages
- 4,041
Well, I was coding a bit and made something that I consider being Linked List 
Dont know if it really can be clasified as one but well...meh.
I have done some benchmarking, and I found out that while push works very fast(1000 pushes in 1 ms), pop is a very slow(7 ms for 1000 pops). At higher rates, the pop slows done until it gets to around 77,4x slower then push(1 mil calls).
So I want to ask for any suggestions on imrpvoing either functionality(more functions or less functions) and some points to optimization(if any)
(I am fully aware that swap() is damn slow, I will do my best to make it faster, currently runs at ~0,3 ms with 100 items in list)
(null is defined as NULL, which is defined as either 0(C++) or ((void)*0) (C)
Also I considered making the value pointer but it was for some reason not working :/
All help is greatly appreciated
Dont know if it really can be clasified as one but well...meh.I have done some benchmarking, and I found out that while push works very fast(1000 pushes in 1 ms), pop is a very slow(7 ms for 1000 pops). At higher rates, the pop slows done until it gets to around 77,4x slower then push(1 mil calls).
So I want to ask for any suggestions on imrpvoing either functionality(more functions or less functions) and some points to optimization(if any)
C++:
//#define DEBUG_MODE
/*
template <class T>
class node{
node* next;
node* prev;
T v; <-- variable stored in the list
Methods:
node()
~node()
void push(T value)
T pop()
node* getnext()
node* getprev()
bool isEmpty()
T pop(int frompos)
T seek()
int getNodesCount()
T seek(int fromposition)
void push(T value, int position)
void push(T value, int position)
void copyList(node* copyinto)
void clear()
*/
#define UNUSED_RETURN_VALUE -1
namespace glo{
template <class T>
class node{
node* next;
node* prev;
T v;
public:
node()
{
next = null;
prev = null;
}
~node()
{
node* a = null;
while(this->next != null)
{
a = this->next->next;
this->next->next = null;
this->next->prev = null;
if (this->next)
delete this->next;
this->next = a;
}
a = null;
}
void push(T value)
{
node* n = this->next;
this->next = null;
this->next = new node;
if (n != null)
n->prev = this->next;
this->next->next = n;
this->next->v = value;
n = null;
}
T pop()
{
if (this->next == null) return UNUSED_RETURN_VALUE;
T i = this->next->v;
node* n = this->next->next;
this->next->next = null;
this->next->prev = null;
delete this->next;
this->next = n;
n = null;
return i;
}
node* getnext()
{
if (this->next == null) return this;
return this->next;
}
node* getprev()
{
if (this->prev == null) return this;
return this->prev;
}
bool isEmpty()
{
return this->next != null ? false : true;
}
T pop(int frompos)
{
if (frompos <= 0)
return UNUSED_RETURN_VALUE;
else if (frompos == 1)
return this->pop();
node* n = this;
while(n->prev != null)
{
n = n->prev;
}
while(frompos-- > 1 && n->next->next != null)
{
n = n->next;
}
return n->pop();
}
T seek()
{
if (this->next == null) return null;
return this->next->v;
}
int getNodesCount()
{
int i = 0;
node* n = this;
while(n->next != null)
{
i++;
n = n->next;
}
return i;
}
T seek(int fromposition)
{
if (fromposition <= 0) return UNUSED_RETURN_VALUE;
node *n = this;
//ensuring that the node is the first on the list:
//in debug mode
#ifdef DEBUG_MODE
while(n->prev != null)
{
n = n->prev;
}
#endif
// safety for overflow
while(fromposition-- > 1 && n->next != null)
{
n = n->next;
}
return n->seek();
}
void push(T value, int position)
{
node* n = this;
while(n->prev != null)
{
n = n->prev;
}
while(position-- > 1 && n->next != null)
{
n = n->next;
}
n->push(value);
n = null;
}
void copyList(node* copyinto)
{
if (copyinto == null) return;
int itter = this->getNodesCount()+1;
node* n = this;
while(itter-- > 1)
{
copyinto->push(n->seek(itter));
}
n = null;
}
void clear()
{
while(!isEmpty())
{
pop();
}
}
void swap()
{
node* n = new node;
while(!isEmpty())
n->push(pop(getNodesCount()+1));
while(!n->isEmpty())
{
push(n->pop());
}
delete n;
}
}; //node<T>
}; //glo(I am fully aware that swap() is damn slow, I will do my best to make it faster, currently runs at ~0,3 ms with 100 items in list)
(null is defined as NULL, which is defined as either 0(C++) or ((void)*0) (C)
Also I considered making the value pointer but it was for some reason not working :/
All help is greatly appreciated
Last edited:
