singly linked list

[Felicia123]

newnode->next = current ->next;
current->next = newnode;

My Question is :
Suppose that a singly linked-list is implemented with both a header and a tail node. Devise linear-time algorithms to:



so did i do correctly? or someplace are wrong?

[Felicia123]

any senior?

[MiiNiPaa]

a) looks like you inserting after given position
b) you should check if new node will be at the head or tail of your list and change head or tail pointers accordingly.

[Felicia123]

so you mean before i insert i have to check whether it's empty or not?
the tail is just to trace the previous node a.
if like what you want me to do at b)

struct node{
       node *head;
       node *tail;
};

node *newnode;
node *current;

newnode->head = current->head
current->head = newnode;

confuse. haha

[ResidentBiscuit]

Your node struct is wrong. Node should store a pointer to the next node, and the data. Your list should have a head node, and a tail node. That's it.

[Felicia123]

this is my question



from what you say.
i should implement in

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

struct list{
      node *head;
      node *tail;
};

isn't what you mean ? but i thought question said is implement with both header and tail? is i mistaken the question ?

[ResidentBiscuit]

That does have a head and tail pointer. Since the requirement is singly-linked list, each node should only have a single link. Really, there's no need to even have a tail pointer in this example unless you are also keeping track of size, which you are not.

EDIT:
I guess a tail pointer gives you the option to add at tail in constant time.

[Felicia123]

because in (ii) Remove the item stored at position p (given by an iterator)
So for the remove isn't i need the tail already ?
to delete previous record

and so.
need i implement correctly for my 2 struct as you said?
am i correct?

[ResidentBiscuit]

Your two structs are correct right now. You don't need a tail pointer ever. It's just for convenience for working with the end like I said. As for the nodes, all you need is a pointer to the next node, which is what your requirements are asking.

[Felicia123]

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

void insertNode( int data ){

	node *temp;
	node *addNode = new node;
	addNode->data = data;
	addNode->next = NULL;

	temp = head;
	if( temp != NULL ){
		while( temp->next != NULL ){
			temp = temp->next;
		}
		temp->next = addNode;
	}
	else{
		head = addNode;
	}
}

i always face problem with my linked list . always not confidence with it,
this is i think with my own without reference to other , i prefer keep do my own only can get understanding..
isn't correct?

[Lowest0ne]

The function you just posted appends the new node to the end of the list. Consider changing the name of it to push_back.

In order to add a node before another, you need to make sure that you find that node without loosing the previous node. Something like this:

temp = head;
while (temp->next != iterator)  // make sure temp->next exists
  temp = temp->next;
// temp is the node before the node you want to insert before :) 

An important thing with containers like this is that you don't loose nodes when you change their pointers. Note the difference

// The correct way
node *toInsert = new node;
toInsert->next = temp->next;
temp->next = toInsert;

// Incorrect, we loose the pointer
node *toInsert = new node;
temp->next = toInsert;
toInsert->next = // ??? 

I typically keep paint open whenever I deal with nodes. It helps me to draw the code that is happening.

I wonder, what is the iterator? A node*, a class?

[Felicia123]

my question stated like this
Suppose that a singly linked-list is implemented with both a header and a tail node. Devise linear-time algorithms to:

(i) Insert item x before position p (given by an iterator)

for my thinking.
iterator = pointer already. so if i using the node * it should be iterator already ?

and your code

temp = head;
while (temp->next != iterator)  // make sure temp->next exists
  temp = temp->next;
// temp is the node before the node you want to insert before :) 

is same with this code what?

if( temp != NULL ){
		while( temp->next != NULL ){
			temp = temp->next;
		}
		temp->next = addNode;
	}
	else{
		head = addNode;
	}

i alreacy check that next will exist first?


and

// The correct way
node *toInsert = new node;
toInsert->next = temp->next;
temp->next = toInsert;

// Incorrect, we loose the pointer
node *toInsert = new node;
temp->next = toInsert;
toInsert = // ???  

i didn't declare like this a?

[Felicia123]

any?

[ResidentBiscuit]

Sorry but what's your question now? Looks like you have the right way to insert figured out.

[Felicia123]

@resident

ya . am i implement correctly?
and fullfil what my question want me to do?
the keypoint
Insert item x before position p (given by an iterator)

i don't really get @lowestone said.
is my code doing wrong or?

[ResidentBiscuit]

Have you tested it? This is where printing out your list comes in handy. Write down on paper the expected output, run the program and output the list after each addition. Then you'll see if it's working. If not, come back and we'll help you.

[Felicia123]

tested and working fine.
i know how the concept run.
i always use paper to draw it, but not really sure it's fullfill my question or not.
as the question given by the UOW australia are really sucks enough.

said by my lecturer . haha.

so can i ask any senior here?
i really need make sure about it that isn't my question that i implement for the addNode
full fill Insert item x before position p (given by an iterator)? need to make sure..
before position p is mean what..

[ResidentBiscuit]

Before position p means this:

If you have a list, [0] -> [1] -> [2] -> [3] -> [4]
and you want to insert element A at position 2, you have to make a choice. Does that mean you place it in front of 2, or behind 2. Since it says before, you place it behind, so the new list would be:

[0] -> [1] -> [A] -> [2] -> [3] -> [4]

That's all it means.

[Felicia123]

#include <iostream>

using namespace std;

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

void insertNode( int data ){

	node *temp;
	node *addNode = new node;
	addNode->data = data;
	addNode->next = NULL;

	temp = head;
	if( temp != NULL ){
		while( temp->next != NULL ){
			temp = temp->next;
		}
		temp->next = addNode;
	}
	else{
		head = addNode;
	}
}

void display(){

	node* temp;
	temp = head;

	if( temp == NULL )
		cout << "No data inside !" << endl;

	while( temp != NULL ){
		cout << "Data : " << temp->data << endl;
		temp = temp->next;
	}
}

int length(){
	node *n;
	int c = 0;

	n = head;
	while( n != NULL ){
		n = n->next;
		c++;
	}
	return c;
}

void insert_position(){
	int pos = 0;
	node *addNode = new node;
	node *temp , *temp1;

	cout << "Enter data to add : ";
	cin  >> addNode->data;

	addNode->next = NULL;

	do{
		cout << "Enter position to add : ";
		cin  >> pos;

		if( pos > length() || pos < 0 ){
			cout << "Invalid length ! " << endl;
		}
	}while( pos > length() || pos < 0 );

		if( head == NULL ){
			head = addNode;
		}
		else{
			temp = head;
			for( int i = 1 ; i < pos - 1 ; i++ ){
				temp = temp->next;
			}
			temp1 = temp->next;
			temp->next = addNode;
			addNode->next = temp1;
		}
}

int main(){

	insertNode( 43 );
	insertNode( 42 );
	insertNode( 93 );
	insertNode( 100 );
	display();
	cout << "size : " << length() << endl;

	insert_position();

	display();

	cout << "size : " << length() << endl;

	system( "pause" );
	return 0;
}

here is my full program . but then when i insert data at position middle it's posibble to add.
but if i wan insert the data to the head. it seem like fail. but now my answer is fullfill question requirement already ya?

[Felicia123]

someone?