10
\$\begingroup\$

Here is my beginner code for dealing with a linked list. I appreciate any comments on structure, logic, formatting, and anything small or large. I have run the code using gcc and tested the small main function using Valgrind with no errors.

ll.h

#ifndef LL_H
#define LL_H

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

typedef struct ll_LinkedList ll_LinkedList;
typedef struct ll_LinkedListNode ll_LinkedListNode;

struct ll_LinkedList {
  ll_LinkedListNode* head;
};

struct ll_LinkedListNode {
  void* data;
  ll_LinkedListNode* next;
};

ll_LinkedList* ll_create    ();
void           ll_destroy   (ll_LinkedList* ll);

void           ll_append    (ll_LinkedList* ll, void* data);
void*          ll_at        (ll_LinkedList* ll, size_t pos);
void           ll_clear     (ll_LinkedList* ll);
void           ll_insert    (ll_LinkedList* ll, size_t pos, void* data);
void*          ll_remove    (ll_LinkedList* ll, size_t pos);
bool           ll_is_empty  (ll_LinkedList* ll);
size_t         ll_length    (ll_LinkedList* ll);
void           ll_prepend   (ll_LinkedList* ll, void* data);

#endif

ll.c

#include "ll.h"

void ll_append(ll_LinkedList* ll, void* data) {
  ll_insert(ll, ll_length(ll), data);
}

void* ll_at(ll_LinkedList* ll, size_t pos) {
  ll_LinkedListNode* node = ll->head;
  while (pos > 0) {
    node = node->next;
    pos--;
  }
  return node->data;
}

void ll_clear(ll_LinkedList* ll) {
  ll_LinkedListNode* node = ll->head;
  while (node != NULL) {
    ll_LinkedListNode* next = node->next;
    free(node);
    node = next;
  }
  ll->head = NULL;
}

ll_LinkedList* ll_create() {
  ll_LinkedList* ll = malloc(sizeof(*ll));
  ll->head = NULL;
  return ll;
}

void ll_destroy(ll_LinkedList* ll) {
  ll_LinkedListNode* node = ll->head;
  while (node != NULL) {
    ll_LinkedListNode* next = node->next;
    free(node);
    node = next;
  }
  free(ll);
}

void ll_insert(ll_LinkedList* ll, size_t pos, void* data) {
  assert(pos <= ll_length(ll));
  
  ll_LinkedListNode* new_node = malloc(sizeof(*new_node));
  new_node->data = data;

  if (ll->head == NULL) {
    new_node->next = NULL;
    ll->head = new_node;
  }
  else if (pos == 0) {
    new_node->next = ll->head;
    ll->head = new_node;
  }
  else {
    ll_LinkedListNode* node = ll->head;
    while (pos > 1) {
      node = node->next;
      pos--;
    }
    new_node->next = node->next;
    node->next = new_node;
  }
}

bool ll_is_empty(ll_LinkedList* ll) {
  return ll_length(ll) == 0;
}

size_t ll_length(ll_LinkedList* ll) {
  size_t length = 0;
  ll_LinkedListNode* node = ll->head;
  while (node != NULL) {
    node = node->next;
    length++;
  }
  return length;
}

void ll_prepend(ll_LinkedList* ll, void* data) {
  ll_insert(ll, 0, data);
}

void* ll_remove(ll_LinkedList* ll, size_t pos) {
  assert(pos <= ll_length(ll));

  if (pos == 0) {
    ll_LinkedListNode* rm = ll->head;
    ll->head = rm->next;
    void* data = rm->data;
    free(rm);
    return data;
  }
  else {
    ll_LinkedListNode* h = ll->head;
    ll_LinkedListNode* t = h->next;
    while (pos > 1) {
      h = h->next;
      t = t->next;
      pos--;
    }
    h->next = t->next;
    void* data = t->data;
    free(t);
    return data;
  }
}

int main() {
  int a = 1;
  int b = 2;
  int c = 3;
  int d = 4;

  ll_LinkedList* ll = ll_create();
  ll_insert(ll, 0, &c);
  ll_insert(ll, 0, &b);
  ll_insert(ll, 0, &a);
  ll_insert(ll, 2, &d);
  ll_insert(ll, 4, &d);

  ll_clear(ll);
  ll_insert(ll, 0, &c);
  ll_insert(ll, 0, &b);
  ll_insert(ll, 0, &a);
  printf("Removed: %d\n", *((int*) ll_remove(ll, 0)));
  printf("Removed: %d\n", *((int*) ll_remove(ll, 0)));
  printf("Removed: %d\n", *((int*) ll_remove(ll, 0)));

  ll_insert(ll, 0, &c);
  ll_insert(ll, 0, &b);
  ll_insert(ll, 0, &a);
  printf("Removed: %d\n", *((int*) ll_remove(ll, 1)));

  if (!ll_is_empty(ll)) {
    printf("It is not empty.\n");
  }

  ll_clear(ll);
  if (ll_is_empty(ll)) {
    printf("It is empty.\n");
  }

  ll_append(ll, &a);
  ll_append(ll, &b);
  ll_append(ll, &c);
  ll_prepend(ll, &c);
  ll_prepend(ll, &c);

  printf("Length: %ld\n", ll_length(ll));
  for (size_t i = 0; i < ll_length(ll); ++i) {
    printf("%d, ", *((int*) ll_at(ll, i)));
  }
  printf("null\n");

  ll_destroy(ll);
  return 0;
}
```
\$\endgroup\$
17
\$\begingroup\$

I recommend some additional compiler warning options:

gcc -std=c17 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds  -Wstrict-prototypes    -Wconversion    252015.c    -o 252015
252015.c:22:1: warning: function declaration isn’t a prototype [-Wstrict-prototypes]
 ll_LinkedList* ll_create    ();
 ^~~~~~~~~~~~~
252015.c:60:16: warning: function declaration isn’t a prototype [-Wstrict-prototypes]
 ll_LinkedList* ll_create() {
                ^~~~~~~~~
252015.c:144:5: warning: function declaration isn’t a prototype [-Wstrict-prototypes]
 int main() {
     ^~~~

Most of the #include lines are not needed for the header file, only by the implementation. In particular, these three can be moved to ll.c:

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

while (node != NULL) is a little long-winded; it's idiomatic to simply write while (node). Some coding standards disallow that, in which case you may be required to use the long form.


  ll_LinkedList* ll = malloc(sizeof(*ll));
  ll->head = NULL;
  ll_LinkedListNode* new_node = malloc(sizeof(*new_node));
  new_node->data = data;

These are problems waiting to happen - ll or new_node might be a null pointer, and we failed to check.


void* ll_remove(ll_LinkedList* ll, size_t pos) {
  assert(pos <= ll_length(ll));

ll_remove() is a public function, so we're in no position to vouch for the condition we're asserting. That should be a real check rather than an assert():

   if (pos <= ll_length(ll) {
       return NULL;
   }

I don't like the way this function walks the list twice (once in ll_length() and then again to actually do the insert. It would be more efficient to just check for going off the end of the list as we traverse it, just once. ll_append() traverses the list three times!


ll_destroy() could simply delegate most of its work to ll_clear().


The special-casing for element 0 in many functions could be removed by using an empty element as list head.


A final style point that might be contentious - I would write sizeof *p rather than sizeof(*p), only using parens around the argument in the rare cases you actually need to use a type name as argument to the sizeof operator (and I do prefer a space after the keyword, unlike the non-alphabetic unary operators such as - and ++). So sizeof (struct tm), for example.

\$\endgroup\$
6
  • \$\begingroup\$ Thanks very much for the detailed pass! I've made a number of changes thanks to this answer. \$\endgroup\$ – sdasdadas Nov 12 '20 at 23:09
  • 1
    \$\begingroup\$ Regarding "while (node != NULL)", that's debatable. The MISRA C guidelines actually say that this should not be done. More specifically, they say "if (node)" should be reserved for Boolean values, because using it to test for zero/non-zero or null/non-null is a common cause of people misunderstanding the code when maintaining it. The OP should be aware of the idiom, but they shouldn't necessarily adopt it. \$\endgroup\$ – Graham Nov 13 '20 at 9:22
  • \$\begingroup\$ I'd recommend keeping the includes and using header guards. See stackoverflow.com/questions/1804486/… \$\endgroup\$ – thzoid Nov 14 '20 at 0:41
  • \$\begingroup\$ @thzoid: The point is that those includes are not needed by users of the library, only by the implementation. So users shouldn't have to pay the price, and they don't belong in our header. If you read the top-voted answer to the question you linked, that's exactly what it recommends, too. \$\endgroup\$ – Toby Speight Nov 15 '20 at 10:20
  • \$\begingroup\$ Direct quote: "if the implementation file needs some other headers, so be it, and it is entirely normal for some extra headers to be necessary. But the implementation file (magicsort.c) should include them itself, and not rely on its header to include them. The header should only include what users of the software need; not what the implementers need." \$\endgroup\$ – Toby Speight Nov 15 '20 at 10:22
12
\$\begingroup\$

Design

Your list includes the head of the list.

struct ll_LinkedList {
   ll_LinkedListNode* head;
};

You could make a lot of your code a lot simpler by including two other values (the tail and the length).

struct ll_LinkedList {
   ll_LinkedListNode* head;
   ll_LinkedListNode* tail;
   size_t             size;
};

This would make sure you don't have to keep calculating the size and would make appending really easy.

Code Review:

#include "ll.h"

void ll_append(ll_LinkedList* ll, void* data) {
  ll_insert(ll, ll_length(ll), data);            // doubles the cost of the insert
                                                 // you have to traverse the list
                                                 // twice.
}

What happens if pos is beyond the end?

void* ll_at(ll_LinkedList* ll, size_t pos) {
  ll_LinkedListNode* node = ll->head;
  while (pos > 0) {
    node = node->next;
    pos--;
  }
  return node->data;
}

You should validate that ll is not NULL before assigning.

ll_LinkedList* ll_create() {
  ll_LinkedList* ll = malloc(sizeof(*ll));
  ll->head = NULL;
  return ll;
}

Simplify the destroy:

void ll_destroy(ll_LinkedList* ll) {
  ll_clear(ll);
  free(ll);
}

void ll_insert(ll_LinkedList* ll, size_t pos, void* data) {

    // assuming pos is in range.    
    while (pos > 1) {
      node = node->next;
      pos--;
    }

Some repeated code you could remove from the if statement.

void* ll_remove(ll_LinkedList* ll, size_t pos) {
  if (pos == 0) {

    // STUFF
    void* data = rm->data;
    free(rm);
    return data;
  }
  else {
    // STUFF
    void* data = t->data;
    free(t);
    return data;
  }
}
\$\endgroup\$
3
  • \$\begingroup\$ Thanks! This included a number of suggestions -- I accepted the current answer because it came first. \$\endgroup\$ – sdasdadas Nov 12 '20 at 23:21
  • 1
    \$\begingroup\$ @sdasdadas Do not worry, just upvote any answer you feel tackles your problem. :-) \$\endgroup\$ – theProgrammer Nov 13 '20 at 0:17
  • \$\begingroup\$ Disagree with tripling the size of the head node. When linked list are used a lot in user code, many of them are empty. The size of an empty LL is good to keep small. As far a having ready access to the head and tail, the "head" node can save the tail instead and have the tail.next point to the head. \$\endgroup\$ – chux - Reinstate Monica Nov 14 '20 at 4:09
7
\$\begingroup\$

For a beginner the code is neat. Most is already given by the previous, much more elaborate answer.

One thing though w.r.t. coding: C is unique in that it can use aliases, pointers to a variable/field.

For instance below current first is an alias of head and after that of a node's next. With *current = ... you can fill the original variable.

void ll_insert(ll_LinkedList* ll, size_t pos, void* data) {
  assert(ll != NULL);
  // Not needed: assert(pos <= ll_length(ll));
  
  ll_LinkedListNode** current = &ll->head;
  //while (*current != NULL && pos > 0) {
  while (*current && pos > 0) {
    current = &(*current)->next;
    --pos;
  }
  // Maybe check here that pos reached 0.
  ll_LinkedListNode* new_node = malloc(sizeof(*new_node));
  new_node->data = data;
  new_node->next = *current;
  *current = new_node;
}

As you see this gives very compact code.

ll_LinkedListNode's struct declaration could move to the .c implementation with a bit of trickery.

In an other language it is customary to hold in ll_LinkedList redundantly the list size for faster operations.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ We don't call that an alias though, it's a pointer to a pointer. I'm sure there are other languages besides C and C++ which can do this! Note that if you use pointers to pointers, you can call yourself a two-star programmer :) \$\endgroup\$ – G. Sliepen Nov 12 '20 at 22:21
  • 2
    \$\begingroup\$ @G.Sliepen yes alias (aliasing) is a term I interned studying programming language design and compiler construction in Computer Science. Being a pointer to a pointer, to an existing variable or field, such pee2pees should be used locally in a smaller scope than the pointed to pointer. Yes there are some other languages, but mainstream Java cannot do this. \$\endgroup\$ – Joop Eggen Nov 12 '20 at 22:33
  • \$\begingroup\$ Thank you @JoopEggen, I have been trying to understand the double pointers in most linked lists I find and this is helpful. I will also migrate the length to be a struct member. Could you elaborate on how to move the struct declaration into the .c file? \$\endgroup\$ – sdasdadas Nov 12 '20 at 23:13
  • 2
    \$\begingroup\$ I am not active in C since sufficient years. Then I did #ifndef's so one would have a typedef void* LinkNodePtr for all API users, and in the C typedef struct {...} *LinkNodePtr. Check whether this trick is still done, maybe nicer today. \$\endgroup\$ – Joop Eggen Nov 12 '20 at 23:21
  • 3
    \$\begingroup\$ The typedef trick is still done, but considered bad style by many here since it hides C's own way of writing a pointer. \$\endgroup\$ – G. Sliepen Nov 13 '20 at 7:31
5
\$\begingroup\$

Use const when able

Functions like ll_at() and ll_length() could code with const to better convey code's usage and allow some select usages and optimizations.

// void* ll_at(ll_LinkedList* ll, size_t pos);
void* ll_at(const ll_LinkedList* ll, size_t pos);

// size_t ll_length(ll_LinkedList* ll);
size_t ll_length(const ll_LinkedList* ll);

Code looks nice, but ...

Pretty layout is work. IMO, not worth the effort/time to code and maintain versus simply using an auto-formatter. (Consider work incorporating the const idea above.)

ll_LinkedList* ll_create    (      void);
void           ll_destroy   (      ll_LinkedList* ll);

void           ll_append    (      ll_LinkedList* ll, void* data);
void*          ll_at        (const ll_LinkedList* ll, size_t pos);
void           ll_clear     (      ll_LinkedList* ll);

vs.

ll_LinkedList * ll_create(void);
void ll_destroy(ll_LinkedList *ll);
void ll_append(ll_LinkedList *ll, void *data);
void* ll_at(const ll_LinkedList *ll, size_t pos);
void ll_clear(ll_LinkedList *ll);

I'd have comments per function, so there common manual format layout is not important.

Apply

Consider an apply function, something that applies the function to every link's data. Very useful.

int ll_apply(ll_LinkedList* ll, int f(void *state, void *data), void *state) {
  ll_LinkedListNode* node = ll->head;
  while (node != NULL) {
    int retval = f(state, node->data);

    // maybe break on non-zero?
    if (retval) return retval;
        
    node = node->next;
  }
  return 0;
}

Use correct specifier with size_t

// printf("Length: %ld\n", ll_length(ll));
printf("Length: %zu\n", ll_length(ll));

Could collapse code

if (ll->head == NULL) {
  new_node->next = NULL;
  ll->head = new_node;
}
else if (pos == 0) {
  new_node->next = ll->head;
  ll->head = new_node;
}

vs

if (ll->head == NULL || pos == 0) {
  new_node->next = ll->head;
  ll->head = new_node;
}

Include trick

When the unnecessary #includes move from ll.h to ll.c, include ll.h there first:

// ll.c
#include "ll.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

This helps verify ll.h does indeed compile on its own.

Lack of comments

IMO, the .h file deserves a fair amount of comment to let users know what the set does. Assume the user does not have access to the .c file.

\$\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.