Inserting into a Linked List

Here is some example code, I wrote in C++, demonstrating how to build up a linked list while respecting the sort order. In this example the list is kept in ascending order.  I defined my Node in the following way:

struct Node{
// Default Constructor
Node(): _pNext (NULL), _value(0){}

// Other Constructors
Node( Node* pNode, int value ) : _pNext( pNode ),_value ( value ) {}
Node( int value ) : _pNext( NULL ),_value ( value ) {}

// Destructor
~Node(){ delete _pNext; _value = 0; }

// Memebers
Node* _pNext;
int _value;
};

Here is the code for inserting the Node:

bool insertNodeSorted( Node* pNode, Node*& pListStart )

{

bool bAdded = false;

if ( pNode ){

Node* pHead = &*pListStart;

// Emtpy List

if ( !pHead )

pListStart = &(*pNode);

// New Node is the Head of the List

else if ( pNode->_value <= pHead->_value ){

pNode->_pNext = pHead;

pListStart = &(*pNode);

bAdded = true;

}

// One item in the list and that it the head

else if ( !pHead->_pNext ) {

pHead->_pNext = pNode;

bAdded = true;

}

// All other cases, where the list is > 1

else {

Node* pPrev = pHead;

Node* pCurrentNode = pPrev->_pNext;

bool bInsert = false;

while( pCurrentNode ){

if ( pNode->_value < pCurrentNode->_value ){

if ( pCurrentNode->_pNext != NULL && pCurrentNode->_pNext->_value != pCurrentNode->_value )

bInsert = true;

else if ( !pCurrentNode->_pNext )

bInsert = true;

if ( bInsert ){

pNode->_pNext = pCurrentNode;

pPrev->_pNext = pNode;

bAdded = true; break;

}

}

pPrev = pCurrentNode;

pCurrentNode = pCurrentNode->_pNext;

}

// Insert the item at the end

if ( !bInsert ) {

pPrev->_pNext = pNode;

bInsert = true;

}}}

return bAdded;

}

Here is some sample code for printing the List:

bool printList( Node* pNode ) {

Node* pCurrentNode = pNode;

if ( pCurrentNode ){

do {

std::cout << pCurrentNode->_value << ” “ ;

pCurrentNode = pCurrentNode->_pNext;

} while ( pCurrentNode );

std::cout << “\n”;

return true;

}

return false;

}

Any comments or improvements are welcomed.

Advertisements
This entry was posted in Development and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s