// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "ullist.h"     // header file
#include <stddef.h>     // for NULL
#include <assert.h>     // for assert()
#include <iostream.h>

List::List(): Size(0), Head(NULL)
{
}  // end default constructor

List::List(List& L): Size(L.Size)
{
    if (L.Head == NULL)
        Head = NULL;  // original list is empty
    else
    {  // copy first node
	Head = new listNode;
	assert(Head != NULL);  // check allocation
	Head->Item = L.Head->Item;

	// copy rest of list
	ptrType NewPtr = Head;  // new list pointer

	// NewPtr points to last node in new list
	// OrigPtr points to nodes in original list
	for (ptrType OPtr = L.Head->Next; OPtr != NULL; OPtr = OPtr->Next)
	{
	    NewPtr->Next = new listNode;
	    assert(NewPtr->Next != NULL);
	    NewPtr = NewPtr->Next;
	    NewPtr->Item = OPtr->Item;
	}  // end for
	NewPtr->Next = NULL;
    }  // end if
}  // end copy constructor

List::~List()
{
    int Success;

    while (!isEmpty())
	Success = del(1);
} // end destructor

int List::isEmpty()
{
    return (Size == 0);
}  // end isEmpty

int List::length()
{
    return Size;
}  // end length

ptrType List::PtrTo(int Position)
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: Position is the number of the desired node.
// Postcondition: Returns a pointer to the desired
// node. If Position < 1 or Position > the number of
// nodes in the list, returns NULL.
// --------------------------------------------------
{
    if ( (Position < 1) || (Position > length()) )
	return NULL;
    else
	// count from the beginning of the list
    {
	ptrType Cur = Head;
	for (int Skip = 1; Skip < Position; ++Skip)
	    Cur = Cur->Next;
	return Cur;
    }  // end if
}  // end PtrTo

int List::retrieve(int Position, listItemType& DataItem)
{
    int Success = ( (Position >= 1) && (Position <= length()) );
    if (Success)
    {
	// get pointer to node, then data in node
	ptrType Cur = PtrTo(Position);
	DataItem = Cur->Item;
    }  // end if
    return Success;
} // end retrieve

int List::insert(int NewPosition, listItemType NewItem)
{
    int NewLength = length() + 1;

    int Success = ( (NewPosition >= 1) && (NewPosition <= NewLength) );
    if (Success)
    {
	// create new node and place NewItem in it
	ptrType NewPtr = new listNode;
	Success = (NewPtr != NULL);
	if (Success)
	{
	    Size = NewLength;
	    NewPtr->Item = NewItem;

	    // attach new node to list
	    if (NewPosition == 1)
	    {
		// insert new node at beginning of list
		NewPtr->Next = Head;
		Head = NewPtr;
	    }
	    else
	    {
		ptrType Prev = PtrTo(NewPosition-1);
		// insert new node after node to which Prev points
		NewPtr->Next = Prev->Next;
		Prev->Next = NewPtr;
	    }  // end if
	}  // end if
    }  // end if
    return Success;
} // end insert

int List::del(int Position)
{
    ptrType Cur;

    int Success = ( (Position >= 1) && (Position <= length()) );
    if (Success)
    {
	--Size;
	if (Position == 1)
	{
	    // delete the first node from the list
	    Cur = Head;  // save pointer to node
	    Head = Head->Next;
	}
	else
	{
	    ptrType Prev = PtrTo(Position-1);
	    // delete the node after the node to which Prev points
	    Cur = Prev->Next;  // save pointer to node
	    Prev->Next = Cur->Next;
	}  // end if

	// return node to system
	Cur->Next = NULL;
	delete Cur;
	Cur = NULL;
    }  // end if
    return Success;
}  // end del

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page