Singly linked list implementation in C

Question

Header file:

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

typedef struct linked_list linked_list;
typedef struct cons cons;

void append(cons *cons, int value);
void linked_list_append(linked_list *ll, int value);
int size(linked_list *ll);
void insert_after(cons *c, int value, int index, int current);
void linked_list_insert_after(linked_list *ll, int value, int index);
void delete(cons *c, int index, int current);
void linked_list_delete(linked_list *ll, int index);
linked_list *new_linked_list(void);
void linked_list_destroy(linked_list *ll);
void destroy(cons *c);
int get(cons *c, int index, int current);
int linked_list_get(linked_list *ll, int index);
void cons_print(cons *c);
void linked_list_print(linked_list *ll);

Actual code:

#include "ll.h"

struct cons {
  int value;
  cons *next;
};

struct linked_list {
  int size;
  cons *list;
};

linked_list *new_linked_list(void) {
  linked_list *ll = malloc(sizeof(linked_list));
  assert(ll);
  ll->size = 0;
  ll->list = NULL;
  return ll;
}

int linked_list_get(linked_list *ll, int index) {
  assert(ll);
  assert(index >= 0);
  assert(index <= (ll->size - 1));
  return get(ll->list, index, 0);
}

int get(cons *c, int index, int current) {
  if (index == current) {
    return c->value;
  } else {
    return get(c->next, index, ++current);
  }
}

void linked_list_append(linked_list *ll, int value) {
  assert(ll);
  (ll->size)++;
  if (ll->list) {
    append(ll->list, value);
  } else {
    cons *new = malloc(sizeof(cons));
    new->value = value;
    new->next = NULL;
    ll->list = new;
  }
}

void append(cons *c, int value) {
  if (c->next) {
    append(c->next, value);
  } else {
    cons *new = malloc(sizeof(cons));
    new->value = value;
    new->next = NULL;
    c->next = new;
  }
}

void linked_list_insert_after(linked_list *ll, int value, int index) {
  assert(ll);
  assert(index >= 0);
  assert(index <= (ll->size - 1));
  ll->size++;
  insert_after(ll->list, value, index, 0);
}

void insert_after(cons *c, int value, int index, int current) {
  if (index == current) {
    cons *new = malloc(sizeof(cons));
    new->value = value;
    new->next = c->next;
    c->next = new;
  } else { 
    insert_after(c->next, value, index, ++current);
  }
}

int linked_list_size(linked_list *ll) {
  if (ll) {
    return ll->size;
  } else {
    return -1;
  }
}

void linked_list_delete(linked_list *ll, int index) {
  assert(ll);
  assert(index >= 0);
  assert(index <= (ll->size - 1));
  ll->size--;
  delete(ll->list, index, 0);
}

void delete(cons *c, int index, int current) {
  if (index == current) {
    cons *temp = c;
    *c = *(c->next);
    free(temp);
  } else {
    delete(c->next, index, ++current);
  }
}

void linked_list_destroy(linked_list *ll) {
  if (ll) {
    destroy(ll->list);
    free(ll);
  }
}

void destroy(cons *c) {
  if (c) {
    destroy(c->next);
    free(c);
  }
}

void linked_list_print(linked_list *ll) {
  assert(ll);
  cons_print(ll->list);
}

void cons_print(cons *c) {
  if (c) {
    printf("%d ", c->value);
    cons_print(c->next);
  } else {
    printf("\n");
  }
}

int main(void) {
  linked_list *new = new_linked_list();
  linked_list_print(new);
  linked_list_append(new, 2);
  linked_list_print(new); // 2
  linked_list_append(new, 3);
  linked_list_print(new); // 2 3
  linked_list_append(new, 4);
  linked_list_print(new); // 2 3 4
  linked_list_insert_after(new, 15, 1);
  linked_list_print(new); // 2 3 15 4
  linked_list_delete(new, 1);
  linked_list_print(new); // 2 15 4
  printf("get 0: %d\n", linked_list_get(new, 0));
  printf("get 2: %d\n", linked_list_get(new, 2));
  printf("get 1: %d\n", linked_list_get(new, 1));
  linked_list_destroy(new);
  return 0;
}

I'm trying to split up my code into a code file and a header file, but it doesn't feel right. I'm not actually hiding any of the implementation details from the client if they can see the helper methods. What's the correct way to do this?
My delete function works, but I don't really understand it. Previously the meat of it was
```
if (index == current) { cons *temp = c; c = temp->next; free(temp); }
```
but this didn't work. Why?
I've tried to incorporate style / memory advice I've gotten in my previous submissions stack and binary search tree. I don't think there are any memory leaks, but I'd like some double checking.

Any and all criticism is welcome here.

ChrisW · Accepted Answer · 2014-02-28 09:58:04Z

I'm not actually hiding any of the implementation details from the client if they can see the helper methods. What's the correct way to do this?

Define the helper ~~methods~~ functions in the C file:

Define them before (higher/earlier in file) than the public functions, so that the public functions have seen them before they're compiled
Define them lower/later in the C file, but put their declarations at the top of the file

And, define them as static: that way they're not visible outside the C file (the linker doesn't create public symbols for them, therefore not only client code hasn't seen them in the header file, but also the linker won't permit client code to link to them.

For example remove append from the header, and write the code like this:

// helper for linked_list_append
static void append(cons *c, int value) {
  if (c->next) {
    append(c->next, value);
  } else {
    cons *new = malloc(sizeof(cons));
    new->value = value;
    new->next = NULL;
    c->next = new;
  }
}

void linked_list_append(linked_list *ll, int value) {
  assert(ll);
  (ll->size)++;
  if (ll->list) {
    append(ll->list, value);
  } else {
    cons *new = malloc(sizeof(cons));
    new->value = value;
    new->next = NULL;
    ll->list = new;
  }
}

My delete function works, but I don't really understand it.

I don't really understand it either. It says,

void delete(cons *c, int index, int current) {
  if (index == current) {
    cons *temp = c;
    *c = *(c->next);
    free(temp);
  } else {
    delete(c->next, index, ++current);
  }
}

... which means ...

If we have found the node we want to delete
copy the contents of the next node onto this node
free this node

I suspect that it seems to work only because you access memory after it has been freed, which is illegal but which may not be visible unless/until other software is doing more malloc/free which cases the freed memory to be overwritten.

Try the following and see whether it still works:

cons *temp = c;
*c = *(c->next);
// it shouldn't matter what's in the memory being freed
// because we're not allowed to use it again after feeing it
memset(temp, 0 sizeof(cons));
free(temp);

The problem/solution with deleting a node from a singly-linked list is:

You must search the list to find the node to be deleted
Before to delete the node, you must adjust the pointers so that the previous node points to the next node

Something like this (untested code ahead):

void linked_list_delete(linked_list *ll, int index) {
  assert(ll);
  assert(index >= 0);
  assert(index <= (ll->size - 1));
  ll->size--;
  cons *found;
  if (index == 0)
  {
    // delete first node on the list
    // list must point to the next node
    found = ll->list;
    ll->list = found->next;
  }
  else
  {
    for (int i = 0, cons* prev = ll->list; ; ++i, prev = prev->next)
    {
      if (i+1 == index)
      {
        // next node is the one we want to delete
        found = prev->next;
        // adjust pointers to point to the one beyond it
        // so we don't break the chain when we remove found
        prev->next = found->next;
        break;
      }
    }
  }
  free(found);
}

It's a bit hard to do this with recursion because to delete the current node you need to be able to adjust the previous node.

I think I fixed delete and cleaned up the code rather well. How does this look ? — dysruption, Mar 1 at 3:13

Jamal · Answer 2 · 2014-02-28 06:17:09Z

up vote 3 down vote

Several things that stick out to me at a glance:

What is cons? Don't you mean Node? At first I thought it was just a short form of constructor, but it appears to be corresponding to a node.
I'd strongly recommend using a different variable name other than new. Although this is C and not C++, this could still cause confusion, both to the reader and to the compiler (also notice the syntax-highlighting in the posted code). It'd be even more problematic if this happened to be compiled with a C++ compiler. You could just rename it to something like newList.
You should rename delete() to something else not corresponding to the equivalent C++ keyword. Also, I'm not sure what exactly this function is for, even from looking at the name. You already appear to have two functions that destroy nodes, so I'm not sure if this one is needed. If it is needed, then give it a more accurate name.
In linked_list_destroy(), you should have a while loop, not an if statement. The loop should manually free() each node, one at a time. You also don't need destroy(). Just have the one function that performs the aforementioned procedure.

edited Feb 28 at 6:17

answered Feb 28 at 5:59

Jamal♦
14k354118

cons is the Racket equivalent of Lisp's car, which I have some experience in. – dysruption Feb 28 at 16:26

@dysruption: Okay. Make sure that is clarified in the code, if it requires explanation. – Jamal♦ Feb 28 at 17:10

Why is the while loop better than the recursive strategy? Sure, you use fewer functions, but I think it's clearer code. Does the general C consensus contradict me on this? – dysruption Mar 1 at 2:49

1

@dysruption: That's generally how it's done, and it's also quite clear. Even if you did stay with recursion, it could still be done with just one function. – Jamal♦ Mar 1 at 3:11

add comment

Frerich Raabe · Answer 3 · 2014-03-02 23:05:19Z

up vote 2 down vote

You could consider consolidating your code by using pointers-to-pointers. Here's some untested but heavily commented code showing the idea.

void linked_list_append(linked_list *ll, int value) {
  /* Acquire a pointer to the pointer to the beginning of the list. 'it' stands for
   * 'iterator' because it's used for iterating the list. */
  cons **it = &ll->list;

  /* Walk the list, making 'it' point to every 'next' pointer in the list until
   * we find a 'next' pointer which is null (denoting the end of the list).
   */
  while ( *it ) it = &it->next;

  /* Make the null 'next' pointer point to a new 'cons' element. */
  *it = malloc(sizeof(cons));
  (*it)->value = value;
  (*it)->next = NULL;

  /* Bump the size of the list by one. */
  ++ll->size;
}

It may be a good idea to get a pen and paper and draw something involving boxes and arrows to see how this works.

edited Mar 2 at 23:05

answered Feb 28 at 9:44

Frerich Raabe
41926

But my ll is a pointer to a pointer, in effect, no? It holds a pointer to the first cons of the list at all times, and that cons can hold a next cons, etc. – dysruption Feb 28 at 16:24

@dysruption No, a pointer to a pointer is something which has two * characters in it's type. e.g. int **. The type of ll is linked_list *. It's a pointer to a struct. – Frerich Raabe Feb 28 at 16:36

I'm confused. My code that you site only occurs if the current ll->list is NULL. If it's not, it calls append, which walks the list and appends to the end. – dysruption Mar 1 at 1:33

@dysruption Oops, you're right - I'll adjust my answer. Thanks for pointing that out! – Frerich Raabe Mar 2 at 23:05

add comment

asked	4 months ago
viewed	283 times
active	4 months ago

current community

your communities

more stack exchange communities

Singly linked list implementation in C

3 Answers

Your Answer

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

Hot Network Questions

current community

your communities

more stack exchange communities

Singly linked list implementation in 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 best-practice linked-list memory-management interface or ask your own question.

Related

Hot Network Questions