TEST REVIEW
-Linked lists
-Merge sort
-Binary Trees

1)LINKED LISTS

Struct Link
{string d;
Link * n;
Link (string s, Link * L = NULL)
	{d=s;
	n=L;}};

1)
Link a("fries");
Link * first = newLink ("pizza");
Link * sf= newLink("stirfry");
	first ->n=sf;
	a.n=sf;

2)
Link * first=newLink("pizza")
	new Link("stirFry"));

3)
Link *Sf=newLink("stir Fry");
Link *first=newLink("pizza",sf);

ADD FUNC:

void add(Link*f, string s)
{f=newLink(s,f);}   

-"fries" is new link to be created
-add function makes "fries" (the new "first") to point to "pizza" ( the old first)
-it points to "first", then becomes "first"
-creates new link, makes it into first and reads in new string
-OR

Link *add(Link*f,strings)
{Link*a=new Link9s,f);
return a;}

first=add(first,"fries")

READING W/LOOPS:

void ATE(Link*f, string s)
Link*P=f;
{Link*t=f->next;
while(t!=NULL)
	{P=t;
	t=t->next;}
p->next=newLink( );

-P is previous, T is current, they're both temporaries
-when done, P will be pointing to the last object and T will be pointing to null

READING W/RECURSION:

void ATE(Link*f, string s)
{if (f->next==NULL)
	{f->next=newLink(s);}
	else
	{ATE(f->next,s);}}

(see 1.0)

-this func. adds new link after NULL.
-keeps going through function recursively until it gets to the end of the list.  then calls new Link function to create a new one at the end of the list.

INSERT BY LOOPS:
void insert(Link *f, string N)  N is new
{Link *t1, *t2;
t1=f;
if(t1!==NULL)
	t2=t1->next;                                 
while(t2!=NULL && t2->data<N)
	{t1=t2;
	t2=t2->next;}
t1->next=newLink(N,t2);}
add(f,N);
return;}

(see 1.1)

-you don't know where you're inserting it yet.

INSERT BY RECURSION:
void I(Link *F, stringN)    				   N=what we want to add ("soup")
{
if(F->n->d>N)
	F->n=new Link(N,F->n);
else
	I(F->next,N);
}

REMOVE:
void R(Link*L,string s)
{ 
Link *t1, *t2; 
t1=L;
t2=t1->next;			//t1=before what you want to del., t2=what you want to del.;
while (t2->data!=s)  		//if  next data isn't what you want to delete, keep going thru 	{t1=t2;			//the list
	t2=t2->next;}
Link*temp=t2->next;	//when t2 is equal to what you want to delete, save t2->next
delete t2;
t1->next=temp;}		//once deleted thing is gone, you connect the links

SEPARATE LINKS AND DATA:
(see 1.2)
-allows you to create multiple linked lists that can share the same data
-do it by making a struct w/ two links, one pointer links to next link, one pointer links to data
-data is all separate.  links can optionally point to data.  
(see 1.3)
 
Link
{Person*P
Link*next;}

f->p->fname="bob";

-only diff. is that the data in struct is a pointer to a different data obj.

2) MERGE SORT
-you have a list of letters and keep splitting them in half
(see 2.1)
-then recombine them

void mergeSOrt(Link*l)
{Link*L1,*Ls;
split(l, L1,L2)
mergeSOrt(L1)
mergeSort(L2);
l=combine(L1,L2);}

SPLIT:
void split(Link*l,L1,L2)
{
L1=l;
L2=l->next;
Link*t=L2->next;
bool which=false;
While(t!=NULL)
{if(!which)
	ATE(L1,t);
else(ATE(L2,t);
which=!which;
temp=t;
	t=t->next;
temp->next=NULL;
}
//add checks for NULL to this function

TIMING:
-nlogn
-its way faster than selection.
-w/ arrays, you need to copy all your data and its not as efficient.

COMBINE:
//smallest from front TO END of temp.
Link*combine(L1,L2)
{temp;
if(L1->d <l2->d)
{temp=L1; L1=L1->next;
else							//basic structure not code
	{temp=L2; L2=L2->next;}				
	while(L1=NULL && L2! NULL)
		ATE(temp, L1 or L2)
	while(L1!=NULL)
		AtTE(temp,L1);
	while(L2!=NULL)
		ATE(temp,L2);}}
return temp;
	}
3) BINARY TREES
-they give automatic ordering
(see 3.1)
-compare each letter that needs to be added until you get to right spot to add

INSERT:
void I(node*&N, string s)
{if N==NULL)
	N=new node(s);
if(s<N->d)			//if the letter you're adding is less than the current data, go L.
	I(N->L,s)
else
	I(N->R,s);}		//otherwise (greater) go right.

-keep going recursively until you get to NULL and add it.