c++ - How can I improve this intrusive linked list implementation of Dictionary? -

to more specifically, without changing nature of intrusive linked list implementation, how can make more memory friendly , more efficient insert/remove algorithms?

i first encountered intrusive linked list here, i'm struggling concept(especially way uses offset access elements in struct), i'm not sure if it's implemented.

i read bit how memory friendly , efficient, seems can achieved by:

1. allocating memory @ beginning. easy array , std::vector, i'm not sure how achieve intrusive linked list. intrusive linked list improve bit allocating memory "nodes" altogether.

2. less branching. used dummy head this, there still branching.

the dictionary entry data structure:

template<typename key, typename item> class entry { public:     item item;     key key;     //  intrusive     entry<key, item>* prev;     entry<key, item>* next; public:     entry();     entry(key k, item i); };  template<typename key, typename item> entry<key, item>::entry() {     prev = this; // dummy head     next = this; }  template<typename key, typename item> entry<key, item>::entry(key k, item i) {     key = k;     item = i;     prev = this;     next = this; } 

the dictionary list data structure:

template<typename key, typename item> class entry_list { private:     entry<key, item>* head; protected:     void insertafter(entry<key, item>* e, entry<key, item>* target);     void remove(entry<key, item>* target); public:     entry_list();     ~entry_list();      void inserthead(const key& k, const item& i); // after dummy head     void remove(const key& k);     void clear(); };  template<typename key, typename item> void entry_list<key, item>::insertafter(entry<key, item>* e, entry<key,  item>* target) {     if (target->next == target)     {         target->next = e;         e->prev = target;     }     else     {         target->next->prev = e;         e->next = target->next;         e->prev = target;         target->next = e;     } }  template<typename key, typename item> void entry_list<key, item>::remove(entry<key, item>* target) {     //  works 1 node     target->prev->next = target->next;     target->next->prev = target->prev;     target->prev = target;     target->next = target; }  template<typename key, typename item> void entry_list<key, item>::remove(const key& k) {     //  have find entry first     entry<key, item>* walker = head->next;     while (walker != walker->next)     {         if (walker->getkey() == k)         {             remove(walker);             return;         }         walker = walker->next;     }     //  check last entry     if (walker->getkey() == k)     {         remove(walker);     } }  template<typename key, typename item> void entry_list<key, item>::clear() {     entry<key, item>* walker = head->next;     while (walker != walker->next)     {         remove(walker);         walker = walker->next;     }     //  last entry     remove(walker); }