Simple Linked List implimentation C

Question

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 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;
}

EDIT: this gist I have the current state of this code after the suggestions given: https://gist.github.com/r-s-/6395640 or alternatively here is the most recent code:

#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;
};

void deleteList(struct node *first)
{
  struct node *tmp;
  while (first != NULL)
  {
    tmp = first->next;
    free(first);
    first = tmp;
  }
}

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

  if (!first) return NULL;

  if (first && first->val == num)
  {
    struct node *temp = first;
    first = first->next;
    free(temp);
  }

  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;


}

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)
{
  struct node *temp = root;
 while (temp!= NULL)
 {
   printf("Value: %d\n", temp-> val);
   temp= temp-> next;
 }
}
int main()
{
 struct node *root = NULL, *tail = NULL;

 int i=1;
 for (;i<=20; ++i)
 {
     struct node *current =(struct node*) 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 = deleteNodes(root, 20);
 root = deleteNodes(root, 1);
 root = deleteNodes(root, 10);
 //reverse list
 root = reverseList(root);
 //print list
 printList(root);

 //delete list
 deleteList(root);
 return 0;
}

Please either post the updated code here or create a new review with the new code. The updated code has at least two NULL pointer references (fatal), so you should get it reviewed. — William Morris, Sep 1 '13 at 1:53
The gist above is now the most recent code. Any more input would be great. — r-s, Sep 1 '13 at 8:13
Please post the updated code here. That way it will always be available for future readers. If I review your code on github, there is the chance that it will disappear or change, making the review invalid. — William Morris, Sep 1 '13 at 12:11
Your current deleteNodes is wrong. What happens if the first two elements are to be deleted? — Vedran Šego, Sep 4 '13 at 22:38

Vedran Šego · Accepted Answer · 2013-09-01 09:22:09Z

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:

Delete all there is to be deleted from the list start.
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.

Thank you very much for the reply. I have made quite a few of the changes. I think in the deleteNodes function in the while(active) in the "else" there needs to be another line making prev = active. Here is what I have now: gist.github.com/r-s-/6395640 I decided to not use your suggestion of a typedef yet as I am getting some conflicting information on when it is correct to use them. There is some discussion here: stackoverflow.com/questions/252780/… Seems like most people do use typedef in this situation though. — r-s, Aug 31 '13 at 1:19
I've fixed the bug in the else-branch; thank you. In your new code, free(root); free(tail); at the end is wrong. You're to remove a list, and not just two elements (which, under some circumstances, may be the same and thus cause an error). — Vedran Šego, Aug 31 '13 at 1:39
I have added void deleteList in the gist, I think this is what you mean by deleting the whole list. If you could let me know if I did it correctly that would be great.. — r-s, Aug 31 '13 at 3:03
The last free(first) in that function frees the memory that was already freed in the last step of the while loop. — Vedran Šego, Aug 31 '13 at 9:22
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. — William Morris, Sep 1 '13 at 1:39

jev · Answer 2 · 2013-08-31 13:34:02Z

up vote 0 down vote

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.

edited Aug 31 '13 at 13:34

answered Aug 31 '13 at 2:25

jev
1011

1

Sorry, I don't understand this. Check out my new deleteList function, do you mean take a void ptr there instead of a struct node pointer? thanks – r-s Aug 31 '13 at 3:04

@jev is talking about deleteNodes. – Vedran Šego Aug 31 '13 at 9:21

updated my post to clarify what i mean – jev Aug 31 '13 at 13:34

add comment

William Morris · Answer 3 · 2013-09-01 13:56:13Z

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;
}

asked	8 months ago
viewed	1258 times
active	8 months ago

current community

your communities

more stack exchange communities

Simple Linked List implimentation C

3 Answers

Your Answer

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

Hot Network Questions

current community

your communities

more stack exchange communities

Simple Linked List implimentation C

3 Answers

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions