Swap nodes in a double linked list - slow sorting algorithm drops nodes

Question

For practice, I've been working on a compressor which does the find-repeated-parts, make-dictionary, compress-with-huffman codes thing.

It's not really working.

One of the problems is, for some reason my sorting algorithm drops keywords from the dictionary. I think the problem is in the swap routine, but I'm not sure. ( this routine swaps adjacent keywords, with next being current->next ).

I do have a static keyword * head;

void swap(keyword * current, keyword * next) {
  keyword * prev = current->prev;
  if (prev){
    prev->next = next;
    next->prev = prev;
  } else { /* no prev - current is head */
    head = next;
    next->prev = 0;
  }
  current->prev = next;
  current->next = next->next;
  next->next = current;
}

Spot anything wrong with this?

Answer 1

You don't set next->next->prev.

Getting data-structure implementations correct is notoriously difficult. The way to spot this sort of thing is to work out how many pointers should need updating (6). You're only updating 5, so one must be missing!

Answer 2

I have seen many question related to Linked Lists, so I decide to share my Linked List version, so it can be adapted and/or improved. This version is written in C++, some methods were omitted for saving space:

class Node {    
    friend class LinkedList;
public:
    Node();
    Node(const node& krNode);
    explicit Node(const int kiData);
    virtual ~Node();
    Node& operator=(const Node& krNode);
    int GetData(void) const {return _idata; }
private: int _iData; Node* _pNetxNode; 
}
Node::Node(): _iData(0), _pNextNode(0) {}
Node::Node(const Node& krnode): _iData(krNode._iData), _pNextNode(0) {}
Node::~Node() {}
Node& Node::operator=(const Node& krNode) {_iData = krNode._iData; return *this; }

class LinkedList {
public:
    LinkedList();
    virtual ~LinkedList();
    int GethLenght(void) {return _iSize;}
    void Append(Node* pNode);
    void Insert(const int kiIndex, node* pNode);
    Node* GetItem(const int kiIndex);
    int IndexOf(Node* pNode);
    void Remove(const int kiInde);  
    void Swap(constconst int kiIndexA, const int kiIndexB); 
    void Clear(void);
    void Print(void);
protected:
    LinkedList(const LinkedList& krLinkedList);
    LinkedList& operator=(const LinkedList& krLinkedList);
private:
    Node* Detach(const int kiIndex);
    Node* _pFirstNode;
    Node* _pLastNode;
    int _iSize;
}

LinkedList::LinkedList() : _pFirstNode(0), _pLastNode(0), _iSize(0) {}
LinkedList::~LinkedList() { Clear(); }
void LinkedList::Append(Node* pnode) { if(0==_iSize{_pFistrNode = pNode; } else { _pLastNode->_pNextNode = pnode; } _pLastNode = pNode; _iSize++; }
void LinkedList::Insert(const int kiIndex, node* pNode) {
    Node* pNext = 0; Node* pPrevious = 0;
    if(0==_iSize) { Append(pNode); }
    else {
        if(0==kiIndex){ pNode->_pNextNode = _pFirstNode; _pFirstNode = pNode; }
        else { pPrevious = Getitem(kiIndex-1); pNext=pPrevoius->_pNextnode; pNode->_pNextNode=pNext; pPrevious->_pNextnode=pNode;}
    } _iSize++;
}
Node* LinkedList::GetItem(const int kiIndex){
    Node* pNode = _pFirstNode; int iCounter = 0;
    while(icounter++ != kiIndex) { pNode = pNode->_pNextnode; }
    return pNode;
}

int LinkedList::IndexOf(Node* pSearchNode){
    node* pNode = _pFirstnode; int iIndex=0;
    while(o != pNode) { if(pnode==pSearchNode) { break;} iIdex++; pNode=pnode->_pnextnode; }
    if(iIndex ==_iSize) {iIndex = -1;}
    return iIndex;
}

void LinkedList::Remove(const int kiIndex){ delete Detach(kiIndex); }

void LinkedList::Swap(const int kiIndexA, const int kiIndexB){
    int iLowIndex = 0; int iHighIndex = 0;
    if(kiIndex>==kiIndexB) {return;}
    iLowIndex = (kiIndexA < kiIndexB) ? kiIndexA : kiIndexB;
    iHighIndex = (kiIndexA > kiIndexB) ? kiIndexA : kiIndexB;
    Insert(iHighIndex, Detach(iLowIndex));
    Insert(iLowIndex, Detach(iHighIndex-1));
}
void LinkedList::Clear(void) {
    Node* pNode=_pFirstNode; while(0!=pnode){delete pNode; pNode=pNode-_pNextNode;}
    _pFirstnode=0; _pLastnode=0;
}
void LinkedList::Print(void) {
    Node* pNode = _pFirstNode;
    while(0 != pnode) {printf("%d ", pNode_iData); pNode = pNode->_pNextNode;}
}
Node* LinkedList::Detach(const int kiindex){
    Node* pnode = _pFirstnode; Node* pToDetachNode = 0;
    if(kiIndex==0){
        pToDetachNode = _pFirstNode; _pFirstNode=pnode->_pNextNode; if(1==_iSize){_pLastNode=0;}
    }
    else{
        Node* pPreviousNode = GetItem(kiIndex-1);
        pToDetachNode = pPreviousNode->_pNextNode;
        if(kiIndex<_iSize){pPreviousNode->_pNextNode=pPreviousNode->_pNextnode; }
        else {pPreviousNode->_pNextnode=0; _pLastNode=pPrevoiusNode;}
    }_iSize--;
}