Clarification/Explanation Insert linked list

On the recomendation of "kermi3" I am posting this as a non-code related C++ question in which I need some clarification.

I am having problems understanding the following and want to know if I am correct in my understanding of inserting items in a linked list. I understand with two pointers the order the sequence performed does not matter. I have the two code sequences.

1. newNode->link =q
p->link = newNode

2. p->link = newNode
newNode->link =q

Question 1; Which of the following is required for inserting to occur correctly in 1.
my thoughts: For 1 to occur correctly I believe
p&q are both required. Q just tells where the new node
will point after inserted with p. Q is also reguired to
conect the new node with the remaining list.

Question 2; in both sequences which of the following MUST be present?

My thoughts:In 1 and 2 am I correct in thinking p must be
present. If it was not or nothing is inserted. Although if p
just occurs the list after p would be lost.


Thanks for your time.

With two pointers set up as how? To what do they point to? They could be completely different lists for all we know. There's not enough information given. Are P and Q pointing to the same node? Is one pointing to the node before, and the second after? I'll assume it's the latter:

Code:

---

/*
1. newNode->link =q
p->link = newNode
*/

Node *n, *p, *q, *list;
....
p = list;
q = list->link;
n = new Node;

n->link = q;
p->link = n;

---

The order of the last two lines doesn't matter in this case. However, assuming they're set up the way I've shown, only p is required. Here's how you can get around it:

Code:

---

n->link = p->link;
p->link = n;

---

P is only required though if you wish to insert before Q, assuming Q is not NULL. If Q is NULL, then P is required. If it's not, and you don't care where you're inserting, you can use Q in place of P.

Code:

---

n->link = q->link;
q->link = n;

---

For the second to occur:

Quote:

---

2. p->link = newNode
newNode->link =q

---

Here, for them to be in this order, both P and Q must be there. Otherwise, as you suspect, you'll lose the tail end of the list (Q) after your assignment to P. Reversing the order of these two lines removes the need for Q, as seen above.

Sounds good anyway. ;)


Quzah.

I should have drawn out the diagram for which the sequences are going.

head ---> 45 ---> 65.---->34---->76----->end
P^ q^
newNode --->50

(P points to 65) (q points to 34)