#include<iostream>

using namespace std;

//define self referential structure
struct Node
{
	int key;
	string value;
	Node *next;
};

int main()
{
	int size;
	cout<<"Enter the number of elements: ";
	cin>> size;
	
	//Ideally, we need 3 pointers for creating a list - head, previous and current
	Node *head,*pre,*cur;
	string dummy; 
	head=null;
	cout<<"Enter "<<size<<" key and values"<<endl;
	//The following loop creates a linked list with size number of nodes
	for(int i=0; i<size; i++)
	{
		cur = new Node; //make a new node
		//read in data
		cin>>cur->key;
		getline(cin,dummy);
		getline(cin,cur->value);	
		cur->next = null;
		if(head == null)	//first element
		{
			head=cur;
		}
		else
		{
			pre->next = cur;
		}
			pre = cur;
	}

	int num;
	cout<<"Enter the key: ";
	cin>>num;

	//traversing the linked list to search
	cur=head;
	while(cur!=null) //until the list runs out
	{
		if(cur->key == value)
			cout<<"The corresponding value is "<<cur->value<<endl;
		cur=cur->next; //move on to the next element
	}

	cur = head; //cleanup
	head=null;
	while(cur!=null)
	{
		pre=cur; //store the current
		cur=cur->next; //move on to the next
		delete pre; //delete the previous
	}

	return 0;
}