Linked List Function?

Question

So i'm writing this function that makes the smallest node at the end of the linked list. So Far it works except for the last element. if the linked list is created as nodes containing items from 0~9, the list after this function is {1,2,3,4,5,6,7,8,0,9} and the zero does not become at the end.

Any ideas why?

my function;

int connecting(linkk A)
{
    linkk L = A;
    for (int i = 0; i<sizeof(L);i++)
    {
        if (L->item < L->next->item)
        {
            int a = L->item;
            L->item = L->next->item;
            L->next->item = a;
            L = L->next;
        }
        else{L=L->next;}
    }
    return 0;
}

Answer 1

Let's start with what I think you should be doing differently:

1. The name of your function is connecting. Given the description of what you'd like the function to do, this is not a good name.
2. I can infer from the usage that linkk is a typedef'ed pointer. Hiding pointers this way is not a good idea, most of the time.
3. Your function returns an int. It's always 0. Why? This does not make any sense.
4. Because linkk is probably a pointer to a node, and you pass the head pointer by value (i.e. a copy of it) to the function, you're unable to handle the case where the head of your list is the minimum. Either return the "new" head pointer, or pass a pointer to the head pointer to be able to modify the head pointer.
5. Your use of sizeof is completely wrong, as already suggested. sizeof(L) will give you the size (in chars) of the pointer, thus probably 8 on a 64 bit system or 4 on a 32 bit system.
6. You're not changing the nodes, but rather moving the values in between the nodes. This is OK if it's what you want to do, but the description of your algorithm suggest that you want to move the node instead.
7. Your function is doing too much, IMO. This can be hard to split, but a better approach would be to separate finding / extracting the minimum and putting it at the end of the list.
8. You're modifying a lot more than you originally wanted to. Consider a list like 1, 2, 3, 0, 4. Using your algorithm, the list will be changed to 2, 3, 1, 4, 0. Doing this is not only bad for the performance, but also very surprising for the caller. Surprises aren't good when it comes to programming!

So, let's get to a hopefully good implementation, step by step:

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

I assume that you want to move the node containing the minimum value to the end of the list, as in your description. I'm also going to keep this into a single function receiving a struct node * head pointer, despite my point above, in order to keep closer to the original code. Let's get out the special / base cases first: Moving the minimum element of an empty list as well as of a single element list is trivial: Do nothing.

if (head == NULL || head->next == NULL) {
  return head;
}

I'm returning the "new" head of the list to allow the caller to update it's own head pointer. (As already said, head is just a copy of the caller's head pointer, modifying it will not have any effect at the call site).

Because we're dealing with a singly linked list here, and the implementation should not unnecessarily iterate over the list, we should remember the node we've previously visited. Otherwise we couldn't easily extract a node from the list:

struct node * follow, * point;

follow follows directly behind the point.

Initially, we place the point to the second node of the list (we already checked that there are at least 2 nodes in the list). follow will thus point to the head:

point = head->next;
follow = head;

Since we want to find the minimum item, we need to keep track of the minimum of the already searched part of the list. We initialize it with the head node's value:

int currentMinimum = head->item;

Now we're ready to iterate over the list, in order to find the node containing the minimum. But we need not only find the node containing the minimum, but also the one before it and the one after it, in order to be able to extract it easily. So, 3 pointers:

struct node * predecessor, * minimum, * successor;

As we set the currentMinimum to heads item, we should also set the pointers accordingly:

predecessor = NULL; // Nothing preceding the head
minimum = head;
successor = head->next;

Now let's iterate, moving the point completely over the list, until it falls off at the end:

while (point != NULL) {
  // to be continued
  follow = point;
  point = point->next;
}
// when we're here, follow will point to the last node

In each iteration, we need to check if we found a smaller value than the current minimum, and eventually remember the node containing it:

if (point->item < currentMinimum) {
  predecessor = follow;
  minimum = point;
  successor = point->next;
  currentMinimum = point->item;
}

Now, when we get out of the loop, the following state should be reached:

• minimum points to the node containing the minimum.
• follow points to the last node of the list.
• The two above could be the same, which is a special case!
• predecessor could still be NULL, which is another special case!

Considering first the special case of minimum = follow: In that case, the minimum is already at the end of the list, so profit! Otherwise, we need to "cut" the node at minimum out of the list and append it to the last node, pointed to by follow:

if (follow != minimum) {
  if (predecessor != NULL) {
    predecessor->next = successor; // Cut out
    minimum->next = NULL; // will be the last node
    follow->next = minimum; // append at end
  } else {
    // to be continued
  }
}

As you can see, there's the second special case to consider: If predecessor is still NULL, then no item was smaller than heads item. (Therefore, we could also test for minimum == head) Thus, the first node of the list will be moved to the end. We need to inform the caller about this!

head = head->next; // Second node is now the first one, though this is not all we need to do, see further down!
minimum->next = NULL; // Will be the last node
follow->next = minimum; // Append at end

Since the assignment to head only changed the function parameter (which is a copy of the pointer with which the function has been called), we need to return the (possibly modified!) head pointer, giving the caller the ability to update its own head pointer:

return head;

A caller would thus use this function like so:

struct node * head = get_a_fancy_list();
head = move_minimum_to_end(head); // This is our function being called!

Finally, a thing to consider: As you can see, moving the node (instead of the item) is more complicated. We need to modify at least 2 pointers in order to achieve what we want. In contrast: Moving the item value requires two modifications of item values (and iterating is easier). Moving the node instead of the item thus makes only sense when pointer assignments are faster than item assignments. Since the items are of type int this is not the case here.

Moving the item instead of the node containing the item is considerably easier. First of all, we need to keep track of the minimum (value as well as node):

struct node * minimum;
int currentMinimum;

To iterate, we're again going to use two pointers. It can be done with a single one, but the code is going to be more readable this way:

struct node * point, * follow;

We start off with the same initial state:

minimum = head;
currentMinimum = head->item;
follow = head;
point = head->next;

Iterating is similar to the other implementation, as is the iteration step:

while (point != NULL) {
  if (point->item < currentMinimum) {
    minimum = point;
    currentMinimum = point->item;
  }
  follow = point;
  point = point->next;
}
// follow points to the last node now

Now, doing the same as the previous implementation, we can swap the items of the last node and the node with the minimum:

minimum->item = follow->item;
follow->item = currentMinimum; // contains minimum->item

There's no point in checking for follow != minimum like in the previous approach: You could do it, but swapping the item of a node with its own item won't do any harm. OTOH adding an if will add a branch, and thus a possible performance penalty.

Since we didn't change the list structure (the linking between nodes), there's not much more to consider. We don't even need to inform the caller about a new head, as there will never be any change to it. For style purposes, I'd add it either way:

return head;

Ok, this got a bit long now, but hopefully it's easy to understand!

Answer 2

Try this function

int connecting(linkk A)
{
 linkk L = A;
  while(L->next!=NULL)
  {
    if (L->item < L->next->item)
    {
        int a = L->item;
        L->item = L->next->item;
        L->next->item = a;

    }

    L=L->next;
  }
  return 0;
 }