Thread: Clarification/Explanation Insert linked list

  1. #1
    Registered User
    Join Date
    Jun 2005

    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.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    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:
    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:
    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.
    n->link = q->link;
    q->link = n;
    For the second to occur:
    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.

    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jun 2005
    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)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  4. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM