linked_list.cpp

linked_list的简单实现 数据结构的经典问题

#include "linkedlist.h"

//Compare is used to decide where in the list a particular object belongs
int Data::Compare(const Data& theOtherData)
{
	if(myValue<theOtherData.myValue)
		return kissmaller;
	if(myValue>theOtherData.myValue)
		return kislarger;
	else
		return kissame;
}

InternalNode::InternalNode(Data* theData,Node* next):myData(theData),myNext(next)
{
}

// the mean of the list 
//when you put a new object into the list
//it is passed off the node which figure out
//where it goes and insert it into the list

Node* InternalNode::Insert(Data* theData)
{
	//is the new guy bigger or smaller than me
	int result=myData->Compare(*theData);
	switch(result)
	{
		//by convention if it is the same as me it comes first
	case kissame://fall through
	case kislarger:
		{
			InternalNode *dataNode=new InternalNode(theData,this);
			return dataNode;
		}
	// it is bigger than I am so pass it on to the next node and let him handle it
	case kissmaller:
		myNext=myNext->Insert(theData);
		return this;
	}
	return this;
}
// Tail node is just a sentinel


// if data comes to me, it must be inserted before me 
//as I am the tail and nothing comes after me

Node* TailNode::Insert(Data* theData)
{
	InternalNode *dataNode=new InternalNode(theData,this);
	return dataNode;
}

HeadNode::HeadNode()
{
	myNext=new TailNode;
}
//nothing comes before the head so just pass the data on to the next node
Node* HeadNode::Insert(Data* theData)
{
	myNext=myNext->Insert(theData);
	return this;
}

//At birth, I create the head node
//It create the tail node
//So an empty list points to the head which
//points to the tail and has nothing between

LinkedList::LinkedList()
{
	myHead=new HeadNode;
}
//Delegate,delegate,delegate
void LinkedList::Insert(Data* pData)
{
	myHead->Insert(pData);
}