Linked List arrow operator looping without p=p->link-CodePudding

How can I get to the last node of the linked list that has x numbers of nodes by using multiple arrow operators(->)?

I am curious how I can express do the -> operation x times in my codes

pseoudo code p (->next)*x

I want to make p->link->link->..... I want to do this x times WITHOUT USING p=p->link

CodePudding user response：

you can use recursion:

struct List
{
    struct List *next;
};


struct List *findLast(struct List *node)
{
    if(node -> next) return findLast(node -> next);
    return node;
}

struct List *findNth(struct List *node, size_t N)
{
    if(N && node -> next) return findLast(node -> next, N - 1)
    if(!N) return node;
    return NULL;
}

CodePudding user response：

Looks to me like you just want some kind of an iterated next function or macro/inline-function where your p=p->next is encapsulated.

struct list { struct list *next; };
struct list *iterated_next(struct list *p, int x){ 
   for(int i=0; i<x;i  ) p=p->next; return p; 
}

I don't the point in avoiding p=p->next. It's just notation. If it's encapsulated, it doesn't have any effect observable from outside.

With the above, notice that if you then do:

struct list *iterated_next3(struct list *p){
    return iterated_next(p,3);
}

on either gcc and clang with optimizations on (the small iteration count will make optimizing compilers want to inline the function and unroll the loop), you will get (x86_64):

iterated_next3:
        movq    (%rdi), %rax
        movq    (%rax), %rax
        movq    (%rax), %rax
        ret

which is absolutely the same thing as what you'd get from (https://gcc.godbolt.org/z/zM684oxex):

struct list *iterated_next3_(struct list *p){
    return p->next->next->next;
}

, reinforcing the point that insisting on no p=p->next is not a very reasonable requirement.

Of course, you can achieve the same effects with a recursion-based iterated_next and without a spelled-out p=p->next (see 0___________'s answer), but that's tail recursion, which will want to get optimized into an effective while loop anyway, so I'd stick to a p=p->next loop as I find that more descriptive of the algorithm.