Double Pointer to a data type that is already a pointer!

I'm writing a function to recursively merge and sort a linked-list. (An improved merge-sort algorithm that avoids scanning the list.)

The function needs to return the sorted first half of the list and the rest of the list. The function is passed the length of the list as an argument n, it recursively calles itself with length n/2 to split the list into single elements before merging it back together in sorted order.

I think I have determined the algorithm that is required - i'm struggling with the C implementation.

As the function is required to return 2 values, I think I need to use a double pointer when calling the function. (So it can modify the calling pointer to point to the second half of the list.)

I have been provided with the following struct definition:

insert

Code:

---

typedef struct node Node;
typedef Node* Link;
struct node{int item; Link next;}

---

My interpretation of the line [typedef Node* Link] is that it defines the type Link to be a pointer, that points to something of type Node.

I'm struggling with the concept of using a double pointer to point to something that is already defined as a pointer.

Can anyone help me with which is the appropraite function prototype in order to have the pointer that is passed to the function, updated by the function? (it needs to return a pointer to a node in the linked list)

Link mergesort_no_scan(int n, Link **list)
-> this to me looks like a double pointer to something that is already a pointer (triple pointer?)

Link mergesort_no_scan(int n, Link *list)
-> Link is already a pointer. If I define the function like this am I calling the function with a double pointer?

Link mergesort_no_scan(int n, Node **list)
-> Or should I be avoiding using the Link pointer when calling the function, and passing the function a pointer to a pointer to a node instead?

Help! I'm totally confusing myself with all this pointer talk!

I hate people who typedef pointers.

Link is already a pointer. It points to a node. So all you need is a pointer to a Link.


Quzah.

Thanks. As I thought.
Is there any benefit to typedef'ing a pointer? All I can think is it means you don't have to type Node *list, just Link list.

For some people, they find it easier to deal with pointers that way. I don't like them because if I'm dealing with a pointer, I want that visibility when I'm using it.

Code:

---

Datatype x;

---

Is that a pointer or not? Who knows, now I have to go hunt up the typedef.

Code:

---

Datatype *x;

---

Is that a pointer? Yes, yes it is.


Quzah.

I dislike people typedefing pointers when they are not named such that it is obviously a pointer, but otherwise it's fine.
I often prefer:

Code:

---

typedef Node *NodePtr;

NodePtr x;

---

over

Code:

---

Node *x;

---

, which I always prefer over

Code:

---

typedef Node *Link;

Link x;

---

I fail to see a good reason to typedef pointers. They get longer to type and you lose track of the type unless it's really well named, but then again, what need have you for doing that? You're only going to have to type an obfuscated name or a longer name.
So avoid them.