Linked List

[SasuKe]

I'm doing my Final Exam revision and I'm stuck. Here's the question.

Question 3 (15 marks)

Use the following declaration for singly linked list.

struct node {     
int data;     
node * next; 
}; 

The following diagram shows the structure of the singly liked list. (I can't show the diagram but I think you can draw from my code)

a) Write C++ codes to create a linked list that has the data and a “Head” pointer pointing to the first node as shown in the diagram above. Hint: create four nodes and pointer and pointer. Link the four nodes as shown above. (5 marks)

b) Write a function that will insert a node at the end of the list. The function declaration is given below. The function takes input a pointer to the list and the data. (5 marks) void InsertNode(node *p, int key)

c) Write a function that will remove last node of the list. The function declaration is given below. (5 marks)

This is what I've done so far, I've answered part a) and b) and it's giving run time error:

  #include <iostream>

using namespace std;

struct node{
	int data;
	node *next;
};

node *Head = NULL;

void insertNode(node *p, int key);

int main(){
	
	int key;
	
	node *n1, *n2, *n3, *n4, *n5;
	
	n1 = new node;
	n2 = new node;
	n3 = new node;
	n4 = new node;
	
	Head = n1;
	
	n1->data = 5;
	n1->next = n2;
	n2->data = 4;
	n2->next = n3;
	n3->data = 6;
	n3->next = n4;
	n4->data = 7;
	n4->next = NULL;
	
	cout << "Enter key: ";
	cin >> key;
	insertNode(n5, key);
	
	system("PAUSE");
	return 0;
}

void insertNode(node *p, int key){
	for(p = Head; p != NULL; p = p->next){
		if(p->next == NULL){
			p->next = p;
			p = new node;
			p->data = key;
			p->next = NULL;
		}
	}	
}

[MikeyBoy]

Right at the start of the insertNode function, you throw away the value of p you passed in, and replace it with the same value as Head. I don't see any purpose in doing that.

The logic of "inserting" a new node doesn't look right. You traverse the list to get to the end alright, at which point p is the final node. However, straight away, you then set p->next to be pointing to p, i.e. the final node has its next pointer pointing to itself.

You then create a new node, and replace the value of p with the address of this new node, setting this new p->next to NULL. You don't connect this new node to the list in any way. You then continue the loop, using this new value of p, and of course p->next is NULL, so another new node is created... and so on, and so on.

The root of the problem is that you are trying to use the variable p for 2 different things - both as the pointer you're using to traverse the list, and as the pointer to the new node you create. In doing so, you end up using the wrong values for the wrong purposes.