5
\$\begingroup\$

I am learning C and tried to make a basic singly linked list. I am looking for some feedback on my implementation. I have implemented deletion and reversal functions. Be hard on me as I am trying to improve.

#include <stdio.h>
#include <stdlib.h>

//very basic linked list implimentation in C. 
//basic node structure. No typedef.
struct node
{
  int val;
  struct node *next;
};

struct node *deleteNode(struct node *first, int num)
{
  struct node *prev=NULL;
  struct node *root = first;
  while (root != NULL)
  {
    if (root->val == num)
    {
      if (prev != NULL && root->next != NULL) //middle elements
      {
        prev->next = root -> next;
        free(root);
      }
      else if (prev == NULL) //first element
      {
        free(first);
        first = root->next;
        root = root->next;
      }
      else if (root->next == NULL) //last element
      {
        prev->next = NULL;
        free(root);
      }
    }
    prev = root;
    root = root -> next;
  }
  return first;
}

struct node *reverseList(struct node *root)
{
  struct node *temp= NULL;
  struct node *prev= NULL;

  while (root!= NULL)
  {
    temp = root->next;
    root->next = prev;
    prev = root;
    root = temp;
  }
  return prev;
}

void printList(struct node *root)
{
 while (root!= NULL)
 {
   printf("Value: %d\n", root -> val);
   root = root -> next;
 }
}

int main()
{
 struct node *root = NULL, *tail = NULL;

 int i=1;
 for (;i<=20; ++i)
 {
     struct node *current = malloc(sizeof(struct node));
     current -> val = i;
     current -> next = NULL;

     if (root==NULL) root = current;
     else tail -> next = current;

     tail = current;
 }

 //delete first,last and middle element 
 root = deleteNode(root, 20);
 root = deleteNode(root, 1);
 root = deleteNode(root, 10);
 root = reverseList(root);
 printList(root);

 return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Your current deleteNodes is wrong. What happens if the first two elements are to be deleted? \$\endgroup\$ – Vedran Šego Sep 4 '13 at 22:38
2
\$\begingroup\$

I suggest using this declaration:

typedef struct _node {
  int val;
  struct _node *next;
} node;

After that, you can declare node *t instead of struct node *t. Also, you'll use sizeof(node) instead of sizeof(struct node).

Your delete is buggy. I'll quote just a bit:

struct node *deleteNode(struct node *first, int num)
{
  struct node *prev=NULL;
  struct node *root = first;
  while (root != NULL)
  {
    if (root->val == num)
    {
      ...
      else if (prev == NULL) //first element
      {
        free(first);
        first = root->next;
        root = root->next;
      }
      ...
    }
    ...
  }
  return first;
}

So, you have root = first, then you free the memory of first, and then you access root->next which is the same as first->next, which is a value contained in the already freed memory.

I'd write it in two parts:

  1. Delete all there is to be deleted from the list start.

  2. Delete all there is to be deleted, but is not at the list start.

Like this:

node *deleteNodes(node *first, int num) {
  node *prev, *active;

  while (first && first->val == num) {
    node *tmp = first;
    first = first->next;
    free(tmp);
  }

  if (!first) return NULL;

  prev = first;
  active = first->next;

  while (active)
    if (active->val == num) {
      prev->next = active->next;
      free(active);
      active = prev->next;
    } else {
      prev = active;
      active = active->next;
    }

  return first;
}

I have changed the name of the function because you seem to want to remove all the nodes containing the value num.

A matter of personal choice: I prefer to transverse through a list the same way I do with arrays -- by using a for loop.

void printList(node *root) {
  node *t;
  for (t = root; t; t = t->next)
    printf("Value: %d\n", t->val);
}

If you really want to reuse root, you can, but one or few additional variables (like my t (stands for "temporary") in the above code) can make your code much more readable.

It may be useful to finish void functions with return;, as it helps you detect certain problems in code (i.e., if you change the return value to something else, such return will result in error and warn you to fix it).

This

node *current = malloc(sizeof(node));

can be written like this like this:

node *current = (node*)malloc(sizeof(node));

Read about using such a cast here and decide for yourself. I prefer to use it.

You should always release all your memory (i.e., delete the remaining list) when you program ends, instead of relying on the OS to do it properly.

\$\endgroup\$
  • \$\begingroup\$ I disagree about casting malloc - see the disadvantages section of the link you gave. I always add a comment that such casts as wrong when reviewing code. On ++i vs i++, the issue comes from C++ where with non-built-in types ++i is faster than i++ because no temporary object is created. For C (and for built-in types in C++) I believe it makes no difference. \$\endgroup\$ – William Morris Sep 1 '13 at 1:39
  • \$\begingroup\$ For cast, I said it can be done, and I gave a reference so that the OP can chose for himself. I prefer it with cast (and I know the disadvantages), but I don't claim that everyone should. As for ++, it made perfect sense to me that ++i is faster, so I've been using it for quite a while, but then I've switched. I remember it being for the speed, but I've retested it now, and the two seem to be of an equal speed, at least on my machines, so I'll remove that part of the answer. Thank you. \$\endgroup\$ – Vedran Šego Sep 1 '13 at 9:21
0
\$\begingroup\$

you can make the list more generic by using void * val and taking a pointer to a comparison function as argument of the deleting function (check out qsort from the standard library to see how it works)

like so:

typedef struct node {
  void * val;
  struct node *next;
} node;

struct node *deleteNode(struct node * first, 
                        void * val_to_delete, 
                        int (*cmp)(const void *, const void*))

where cmp is user-defined function that takes to void pointers, casts them to the actual type used and compares them. this way you can store and delete any value (e.g. another list) as a value.

\$\endgroup\$
0
\$\begingroup\$

A few comments:

  • It is generally considered best practice to define one variable per line.
  • Be consistent with variable names (eg tmp and temp, root and first)
  • Use const and static where possible (eg printList should have a const parameter

  • Your delete_list fails if first is NULL (tries to free tmp). Define tmp inside the loop where it is first used.


Your deleteNodes (derived from the answer from @VedranŠego) is still too complicated and you introduce a fault by omitting the answer's check if (!first) return NULL;

And easier solution is this:

static struct node *deleteNodes (struct node *n, int num)
{
    struct node start = {.next = n};
    struct node *prev = &start;

    while (n) {
        if (n->val == num) {
            prev->next = n->next;
            free(n);
            n = prev->next;
        } else {
            prev = n;
            n = n->next;
        }
    }
    return start.next;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.