Linked Lists
The intention of this post is to create a LinkedList class and implement all generally asked questions on linked lists. So here it is:
class Node {
public:
Node( int nData ) : m_nData( nData ), m_pNext( NULL ) {};
~Node() { m_nData = 0; };
void SetData( int nData ) { m_nData = nData;};
int GetData() const { return m_nData;};
void SetNext( Node* pNode ) { m_pNext = pNode;};
Node* GetNext() const { return m_pNext;};
void Print( bool bReverse = false ) const;
void Print( bool bReverse = false ) const;
private:
int m_nData;
Node* m_pNext;
};
void Node:: Print( bool bReverse /*= false*/ ) const {
if( bReverse && !m_pNext )
std::cout << "NULL";
if( bReverse )
std::cout << "<-- span="span"> << m_nData;
else
std::cout << m_nData << " --> ";
if( !bReverse && !m_pNext ) {
//this is the last node
std::cout << "NULL";
}
}
void Node:: Print( bool bReverse /*= false*/ ) const {
if( bReverse && !m_pNext )
std::cout << "NULL";
if( bReverse )
std::cout << "<-- span="span"> << m_nData;
else
std::cout << m_nData << " --> ";
if( !bReverse && !m_pNext ) {
//this is the last node
std::cout << "NULL";
}
}
class LinkedList {
public:
LinkedList() : m_pHead( NULL ) {};
~LinkedList() { Clear();};
Node* AddNode( int nData, bool bSorted = false );
Node* AddHead( int nData );
Node* AddTail( int nData );
Node* AddAt( size_t nPos, int nData );
size_t Length() const;
void Clear();
bool Delete( Node* pNode );
bool IsEmpty() const { return m_pHead == NULL; };
bool Delete( Node* pNode );
bool IsEmpty() const { return m_pHead == NULL; };
Node* GetNthLastNode( size_t nN ) const;
bool IsCyclic() const;
Node* FindCycleNode() const;
int FindCycleLength() const;
Node* FindMidNode() const;
Node* FindIntersectingNode( Node* pList1, Node* pList2 ) const;
Node* FindMidNode() const;
Node* FindIntersectingNode( Node* pList1, Node* pList2 ) const;
bool IsPalindrome() const;
void Reverse();
void ReversePrint( bool bRecursive = true );
void Print() const;
void ReversePrint( bool bRecursive = true );
void Print() const;
static size_t Length( Node* pHead );
private:
//member functions
void ReversePrint( Node* pNode ) const;
Node* IsPalindrome( Node* pLeft, Node* pRight );
//attributes
//member functions
void ReversePrint( Node* pNode ) const;
Node* IsPalindrome( Node* pLeft, Node* pRight );
//attributes
Node* m_pHead;
};//class LinkedList
void LinkedList::Print() const {
Node* pStart = m_pHead;
while( pNode ) {
pNode->Print( false );
pNode = pNode->GetNext();
}
}
void LinkedList::ReversePrint( Node* pNode ) const {
if( !pNode )
return;
else {
ReversePrint( pNode->GetNext() );
pNode->Print( true );
}
}
/*
* There are two do this:
* 1. Recursive solution: In this we recursively call the function
* till we reach the end of the list and while returning back
* display the content of the node
* 2. Iterative: Reverse the list, print it and then reverse it back
* again. However this entails changing the list
* 3. Iterative: If there is a need to not to change the list
* then a stack can be used. Iterate the list, push elements
* onto the stack. Next pop the elements and print the poped
* element poped.
void LinkedList::ReversePrint( bool bRecursive /*= true*/ ) {
if( bRecursive )
ReversePrint( m_pHead );
else {
//iterative solution
//Reverse the linked list O(n)
//print the list O(n)
//Reverse it back again O(n)
Reverse();
Print();
Reverse();
}
}
Node* LinkedList::IsPalindrome( Node* pLeft, Node* pRight ) {
if( !pRight )
return pLeft;
//Calling IsPalindrome recursively will
//go on till we hit the end of the list
pLeft = IsPalindrome( pLeft, pRight->GetNext() );
//Now we have hit the end of the list
if( pLeft ) {
if( pLeft->GetData() == pRight->GetData() ) {
pLeft = pLeft->GetNext() ? pLeft->GetNext() : pLeft;
}
}
return pLeft;
}
/*
* A palindrome is a word, phrase, number, or other sequence of
* units that may be read the same way in either direction, with
* general allowances for adjustments to punctuations and word
* dividers.
* There are many ways to implement this algorithm
* 1. Find the mid-point, then reverse the second part of the list
* then compare the firs half and 2nd half and then reverse the 2nd
* half back to get the original list
* 2. Using recursion, in this case we divide the linked list into
* smaller lists and check whether the smaller lists are palindrome
* This implementation uses the recursion technique time complexity
* is O(n) and space complexity is O(n).
bool LinkedList::IsPalindrome() const {
return NULL == IsPalindrome( m_pHead, m_pHead ) ? false : true;
}
/*
* If two intersecting linked lists intersect they will form a
* Y kind of pattern. The way to find the intersecting node
* is to find the length of both the lists.
* Then find the one which is bigger.
* Iterate the bigger list delta (difference in lengths) nodes
* Now start moving both the lists simultaneously
* The place at which both the lists point to the same node
* is the intersecting point, if they do not meet, then they
* are not intersecting.
*/
Node* LinkedList::FindIntersectingNode( Node* pList1, Node* pList2 ) const {
if( !pList1 || !pList2 )
return NULL;
//find the length of both the lists
size_t nLen1 = LinkedList::Length( pList1 );
size_t nLen2 = LinkedList::Length( pList2 );
//find the delta
size_t nDelta = nLen1 > nLen2 ? nLen1 - nLen2 : nLen2 - nLen1;
Node* pLongerList = nLen1 > nLen2 ? pList1 : pList2;
Node* pSmallerList = nLen1 > nLen2 ? pList2 : pList1;
//iterate nDelta nodes in the longer list
size_t nCount = 0;
while( nCount++ < nDelta ) {
pLongerList = pLongerList->GetNext();
}
//now iterate both the lists
//till we come across a scenario where both the nodes
//are same or we reach the end
//NOTE: Since both the lists now are exactly the same size
//hence we can check for NULL of one pointer itself
while( pLongerList != pSmallerList || pLongerList != NULL ) {
pLongerList = pLongerList->GetNext();
pSmallerList = pSmallerList->GetNext();
}
return pLongerList;
}
/*
* This function finds the middle node of the linked list
* The way to do this is to start with two pointers, both
* starting from head. The slow pointer will move one step
* whereas the fast pointer will move two steps at a time
* When the fast pointer hits the last, the slow pointer
* will be pointing to the middle node.
* NOTE: Need to take care of end of list.
Node* LinkedList::FindMidNode() const {
Node* pSlow = m_pHead;
Node* pFast = m_pHead;
if( IsEmpty() )
return NULL;
bool bToggle = false;
while( pSlow->GetNext() ) {
if( bToggle ) {
pFast = pFast->GetNext();
}
Node* LinkedList::FindMidNode() const {
Node* pSlow = m_pHead;
Node* pFast = m_pHead;
if( IsEmpty() )
return NULL;
bool bToggle = false;
while( pSlow->GetNext() ) {
if( bToggle ) {
pFast = pFast->GetNext();
}
else {
pFast = pFast->GetNext();
pSlow = pSlow->GetNext();
}
bToggle = !bToggle; }
return pSlow;
}
/*
* The purpose of this function is to delete the Node pointer
* to in the Node* pointer. The code is not supposed to use the
* head pointer. So this means this should be done in O(1) time
*/
bool LinkedList::Delete( Node* pNode ) {
if( !pNode )
return false;
//a->b->c->e
//delete b
//Copy the data of c in b
//point b to its next next
//delete b's next
//a->b->e
//NOTE: The idea is to copy over the contents
//of the next node into this node
//then point this node to next' next.
//and then delete the next node/
//This will NOT work if the given Node is the
//last node,
if( pNode->GetNext() ) {
pNode->SetData( pNode->GetNext()->GetData() );
Node* pNext = pNode->GetNext();
pNode->SetNext( pNext->GetNext() );
delete pNext;
return true;
}
else {
//this is the last node, cannot do anything
return false;
}
}
return pSlow;
}
/*
* The purpose of this function is to delete the Node pointer
* to in the Node* pointer. The code is not supposed to use the
* head pointer. So this means this should be done in O(1) time
*/
bool LinkedList::Delete( Node* pNode ) {
if( !pNode )
return false;
//a->b->c->e
//delete b
//Copy the data of c in b
//point b to its next next
//delete b's next
//a->b->e
//NOTE: The idea is to copy over the contents
//of the next node into this node
//then point this node to next' next.
//and then delete the next node/
//This will NOT work if the given Node is the
//last node,
if( pNode->GetNext() ) {
pNode->SetData( pNode->GetNext()->GetData() );
Node* pNext = pNode->GetNext();
pNode->SetNext( pNext->GetNext() );
delete pNext;
return true;
}
else {
//this is the last node, cannot do anything
return false;
}
}
void LinkedList::Reverse() {
//1->2->3->1->5->6
//6->5->1->3->2->1
//The approach is to iterate the list and
//swap the nodes
Node* pCurr = m_pHead;
Node* pPrev = NULL;
Node* pNext = NULL;
while( pCurr ) {
//store the next
pNext = pCurr->GetNext();
//6->5->1->3->2->1
//The approach is to iterate the list and
//swap the nodes
Node* pCurr = m_pHead;
Node* pPrev = NULL;
Node* pNext = NULL;
while( pCurr ) {
//store the next
pNext = pCurr->GetNext();
//set the current's next to previous
pCurr->SetNext( pPrev );
//previous becomes the current pointer
pPrev = pCurr;
//next node is the pNext
pCurr = pNext;
}
m_pHead = pPrev;
}
}
m_pHead = pPrev;
}
int LinkedList::FindCycleLength() const {
Node* pSlow = m_pHead;
Node* pFast = m_pHead;
bool bCycle = false;
while( pSlow && pFast ) {
pFast = pFast->GetNext();
if( pSlow == pFast ) {
bCycle = true;
break;
}
if( !pFast )
break;
pFast = pFast->GetNext();
if( pSlow == pFast ) {
bCycle = true;
break;
}
pSlow = pSlow->GetNext();
}
if( bCycle ) {
//now both slow and fast are pointing to the same node
//now we need to loop and count
int nCount = 0;
pFast = pFast->GetNext();
while( pSlow != pFast ) {
pFast = pFast->GetNext();
++nCount;
}
return nCount;
}
else
return -1;
}
/*
* The approach to find the Node, where the cycle starts is
* very similar to the IsCyclic function.
* Once a cycle is detected, then reset the slow pointer to the
* beginning of the linked list and start moving both the slow
* and the fast node simultaneously, one node at a time.
* The node at which they meet is the Node where the cycle starts
* Note: This algorithm is also known as Floyd Cycle finding
* algorithm.
* There is one more algorithm called Brent's Algorithm.
*
*/
Node* LinkedList::FindCycleNode() const {
Node* pSlow = m_pHead;
Node* pFast = m_pHead;
bool bCycle = false;
while( pSlow && pFast ) {
pFast = pFast->GetNext();
if( pSlow == pFast ) {
bCycle = true;
break;
}
if( !pFast )
break;pFast = pFast->GetNext();
if( pSlow == pFast ) {
bCycle = true;
break;
}
pSlow = pSlow->GetNext();
}
if( bCycle ) {
pSlow = m_pHead;
while( pSlow != pFast ) {
pFast = pFast->GetNext();
pSlow = pSlow->GetNext();
}
return pSlow;
}
else
return NULL;
}
/*
* The way to find whether a node is cyclic or not
* is to use two pointers. Move the ahead pointer two node at a time
* whereas move the slower node one node at a time.
* If the faster node reaches NULL then it is not cyclic
* At some point of time the slow and the fast node will meet.
* If they meet then the linked list is cyclic.
*/
bool LinkedList::IsCyclic() const {
Node* pSlow = NULL;
Node* pFast = NULL;
while( pSlow && pFast ) {
pFast = pFast->GetNext();
if( pSlow == pFast )
return true;
if( !pFast )
break;
pFast = pFast->GetNext();
if( pSlow == pFast )
return true;
pSlow = pSlow->GetNext();
}
return false;
}
/*
* The way to do this is to use 2 pointers.
* Move one pointer nN positions from the head.
* (Take care of scenarios wherein we reach the end before the nN position)
* Now move both the pointers simultaneously. When the first pointer reaches the end, the node at which the first pointer is pointing will be the NthLastNode
*/
Node* LinkedList::GetNthLastNode( size_t nN ) const {
Node* pAhead = m_pHead;
Node* pBehind = m_pHead;
//Move the pAhead node by nN positions
size_t nCurrPos = 0;
while( pAhead && nCurrPos++ < nN ) {
pAhead = pAhead->GetNext();
}
if( !pAhead ) {
//we reached the end before nN nodes
return NULL;
}
//Now move both the nodes simultaneosuly till pAhead reaches
//the end
while( pAhead ) {
pAhead = pAhead->GetNext();
pBehind = pBehind->GetNext();
}
return pBehind;
}
/*
* This function returns the length of the linked list
* Note: In a real world implementation, you would want to
* store the length as a private member and keep it updated
* on every add/remove operation happening in the linked list.
* Node* pHead: Pointer to the head of the linked list
*/
size_t LinkedList::Length( Node* pHead ){
size_t nLength = 0;
Node* pNode = pHead;
while( pNode ) {
++nLength;
pNode = pNode->GetNext();
}
return nLength;
}
size_t LinkedList::Length() const {
return LinkedList::Length( m_pHead );
}
/*
* This functions adds a new node in the linked list
* if the bSorted flag is true, then the data is added in
* ascending order
*/
Node* LinkedList::AddNode( int nData, bool bSorted /*= false*/ ) {
if( !m_pHead ) {
m_pHead = new Node( nData );
return m_pHead;
}
//so this is not a empty node
//if the node is to be added in a sorted order
//then we find the position at which the node
//needs to be inserted and then add it here
//else we add a new head
if( bSorted ) {
//search the position where it needs to be inserted
Node* pCurr = m_pHead;
Node* pPrev = NULL;
while( pCurr && pCurr->GetData() < nData ) {
pPrev = pCurr;
pCurr = pCurr->GetNext();
}
Node* pNode = new Node( nData );
pNode->SetNext( pPrev->GetNext() );
pPrev->SetNext( pNode );
return pNode;
}
else {
Node* pNode = m_pHead;
m_pHead = new Node( nData );
m_pHead->SetNext( pNode );
return m_pHead;
}
}Node* LinkedList::AddHead( int nData ) {
return AddNode( nData, false );
}
Node* LinkedList::AddTail( int nData ) {
Node *pNode = new Node( nData );
Node *pCurr = m_pHead;
Node *pPrev = NULL;
while( pCurr ) {
pPrev = pCurr;
pCurr = pCurr->GetNext();
}
pPrev->SetNext( pNode );
return pNode;
}
Node* LinkedList::AddAt( size_t nPos, int nData ) {
if( 0 == nPos )
return AddHead( nData );
size_t nCurrPos = 0;
Node *pCurr = m_pHead;
Node *pPrev = NULL;
while( pCurr && nCurrPos++ < nPos ) {
pPrev = pCurr;
pCurr = pCurr->GetNext();
}
Node* pNode = new Node( nData );
pNode->SetNext( pPrev->GetNext() );
pPrev->SetNext( pNode );
return pNode;
}
void LinkedList::Clear() {
Node* pPrev = NULL;
while( m_pHead ) {
pPrev = m_pHead;
m_pHead = m_pHead->GetNext();
delete pPrev;
}
}
1 comment:
Of course I have comments ....
a. No thread safety at all ? What's up with that ?
b. Although Delete is O(1), what about the cost of the copy (m_ndata is conveniently an int in this example) ?
c. What is a caller to do when Delete returns false (in other words how do I delete the last node) ?
Post a Comment