Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   Linked List in C++ (http://www.go4expert.com/articles/linked-list-cpp-t18600/)

naimish 18Jul2009 11:02

Linked List in C++
 

Introduction



Code for LinkList in C++

The code



Code: Cpp

#include "LinkedList.h"
/**
* Construct the list
*/

template <class Object>
List<Object>::List( )
{
    header = new ListNode<Object>;
}

/**
* Copy constructor
*/

template <class Object>
List<Object>::List( const List<Object> & rhs )
{
    header = new ListNode<Object>;
    *this = rhs;
}

/**
* Destructor
*/

template <class Object>
List<Object>::~List( )
{
    makeEmpty( );
    delete header;
}

/**
* Test if the list is logically empty.
* return true if empty, false otherwise.
*/

template <class Object>
bool List<Object>::isEmpty( ) const
{
    return header->next == NULL;
}

/**
* Make the list logically empty.
*/

template <class Object>
void List<Object>::makeEmpty( )
{
    while( !isEmpty( ) )
        remove( first( ).retrieve( ) );
}

/**
* Return an iterator representing the header node.
*/

template <class Object>
ListItr<Object> List<Object>::zeroth( ) const
{
    return ListItr<Object>( header );
}

/**
* Return an iterator representing the first node in the list.
* This operation is valid for empty lists.
*/

template <class Object>
ListItr<Object> List<Object>::first( ) const
{
    return ListItr<Object>( header->next );
}

/**
* Insert item x after p.
*/

template <class Object>
void List<Object>::insert( const Object & x, const ListItr<Object> & p )
{
    if( p.current != NULL )
        p.current->next = new ListNode<Object>( x, p.current->next );
}

/**
* Return iterator corresponding to the first node containing an item x.
* Iterator isPastEnd if item is not found.
*/

template <class Object>
ListItr<Object> List<Object>::find( const Object & x ) const
{
    /* 1*/ ListNode<Object> *itr = header->next;
    /* 2*/ while( itr != NULL && itr->element != x )
    /* 3*/ itr = itr->next;
    /* 4*/ return ListItr<Object>( itr );
}

/**
* Return iterator prior to the first node containing an item x.
*/

template <class Object>
ListItr<Object> List<Object>::findPrevious( const Object & x ) const
{
    /* 1*/ ListNode<Object> *itr = header;
    /* 2*/ while( itr->next != NULL && itr->next->element != x )
    /* 3*/ itr = itr->next;
    /* 4*/ return ListItr<Object>( itr );
}

/**
* Remove the first occurrence of an item x.
*/

template <class Object>
void List<Object>::remove( const Object & x )
{
    ListItr<Object> p = findPrevious( x );
    if( p.current->next != NULL )
    {
        ListNode<Object> *oldNode = p.current->next;
        p.current->next = p.current->next->next; // Bypass deleted node
        delete oldNode;
    }
}

/**
* Deep copy of linked lists.
*/

template <class Object>
const List<Object> & List<Object>::operator=( const List<Object> & rhs )
{
    ListItr<Object> ritr = rhs.first( );
    ListItr<Object> itr = zeroth( );
    if( this != &rhs )
    {
        makeEmpty( );
        for( ; !ritr.isPastEnd( ); ritr.advance( ), itr.advance( ) )
        insert( ritr.retrieve( ), itr );
    }
    return *this;
}


shabbir 18Jul2009 12:34

Re: Linked List in C++
 
We have quite a few now on this

Sort Linked List
Basic operations in Linked List
Swap two nodes of a linked list
Move forward a node in linked list
Insert a node in a linked list
Double linked list
Double circular linked list
Circular linked list
Priority Queue implementation using Linked List
Queue implementation through linked list

naimish 18Jul2009 12:37

Re: Linked List in C++
 
Ohh, You meant we have so many article on this ? I thouth we have only few so posted this one :)

shabbir 18Jul2009 12:51

Re: Linked List in C++
 
Quote:

Originally Posted by naimish (Post 52950)
Ohh, You meant we have so many article on this ? I thouth we have only few so posted this one :)

Yeah. :D

shabbir 3Aug2009 14:33

Re: Linked List in C++
 
Nominate this article for Article of the month - Jul 2009


All times are GMT +5.5. The time now is 07:52.