List (C)

For string handling, see strList.c. Also, in strList.c, you can find a function insert_at, which allows the programmer to insert at any position of the list.

The code contains many comments, since it’s intend is to educate. If you wish to remove it use this

gcc -fpreprocessed -dD -E test.c

which will output the code without the comments, as suggested here.

list.c

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

typedef struct listnode *Listptr;

struct listnode {
  int value;
  Listptr next;
};

int empty(Listptr);
int in(Listptr, int);
int size(Listptr list);
int n_th(Listptr, int, int *);
int write_n_th(Listptr, int, int);
void insert_at_start(Listptr *, int);
void insert_at_end(Listptr *, int);
int delete(Listptr *, int);
void print(Listptr);
void free_list(Listptr *);

int main(void)
{ Listptr alist;
  int v;
  alist = NULL;                                     /* List is NULL */
                                          /* Check if list is empty */
  printf("List is%s empty\n", empty(alist) ? "" : " not");
  insert_at_start(&alist, 44);                /* List is 44--> NULL */
  printf("List is "); print(alist);
  insert_at_end(&alist, 55);            /* List is 44--> 55--> NULL */
  printf("List is "); print(alist);
  insert_at_start(&alist, 33);     /* List is 33--> 44-> 55--> NULL */
  printf("List is "); print(alist);
  insert_at_end(&alist, 66); /* List is 33--> 44-> 55--> 66--> NULL */
  printf("List is "); print(alist);
                                          /* Check if list is empty */
  printf("List is%s empty\n", empty(alist) ? "" : " not");
                                                /* Check membership */
  printf("55 is%s in list\n", in(alist, 55) ? "" : " not");
  printf("77 is%s in list\n", in(alist, 77) ? "" : " not");
  if (n_th(alist, 2, &v))                     /* Return 2nd element */
    printf("Item no 2 is %d\n", v);
  else
    printf("Item no 2 does not exist\n");
  if (n_th(alist, 6, &v))                     /* Return 6th element */
    printf("Item no 6 is %d\n", v);
  else
    printf("Item no 6 does not exist\n");
  printf("Deleting 55. %s\n", delete(&alist, 55) ? "OK!" : "Failed!");
                                  /* List is 33--> 44--> 66--> NULL */
  printf("List is "); print(alist); 
  printf("Deleting 22. %s\n", delete(&alist, 22) ? "OK!" : "Failed!");
                                  /* List is 33--> 44--> 66--> NULL */
  printf("List is "); print(alist);
  printf("Deleting 33. %s\n", delete(&alist, 33) ? "OK!" : "Failed!");
                                        /* List is 44--> 66--> NULL */
  printf("List is "); print(alist);
  
  free_list(&alist);
  return 0;
}

int empty(Listptr list)                   /* Check if list is empty */
{ if (list == NULL)                          /* Is it really empty? */
    return 1;                                         /* Yes, it is */
  else
    return 0;                                       /* No, it isn't */
}

int in(Listptr list, int v)         /* Check if v is member of list */
{ while (list != NULL)         /* Visit list elements up to the end */
    if (list->value == v)   /* Did we find what we are looking for? */    
      return 1;                                      /* Yes, we did */
    else
      list = list->next;                  /* No, go to next element */
  return 0;                            /* Finally, v is not in list */
}

int size(Listptr list) {
  int c = 0;
  while (list != NULL) {
    ++c;
    list = list->next;
  }
  return c;
}

int n_th(Listptr list, int n, int *vaddr)
           /* Return n-th element of list, if it exists, into vaddr */
{ while (list != NULL)    /* Maybe search up to the end of the list */
    if (n-- == 1) {              /* Did we reach the right element? */
      *vaddr = list->value;                       /* Yes, return it */
      return 1;                                      /* We found it */
    }
    else
      list = list->next;                  /* No, go to next element */
  return 0;                             /* Sorry, list is too short */
}

int write_n_th(Listptr list, int n, int v)
{ while (list != NULL)    /* Maybe search up to the end of the list */
    if (n-- == 1) {              /* Did we reach the right element? */
      list->value = v;                         /* Yes, overwrite it */
      return 1;                                      /* We found it */
    }
    else
      list = list->next;                  /* No, go to next element */
  return 0;                             /* Sorry, list is too short */
}

void insert_at_start(Listptr *ptraddr, int v)
                      /* Insert v as first element of list *ptraddr */
{ Listptr templist;
  templist = *ptraddr;                /* Save current start of list */
  *ptraddr = malloc(sizeof(struct listnode)); /* Space for new node */
  (*ptraddr)->value = v;                               /* Put value */
  (*ptraddr)->next = templist;      /* Next element is former first */
}

void insert_at_end(Listptr *ptraddr, int v)
                       /* Insert v as last element of list *ptraddr */
{ while (*ptraddr != NULL)                     /* Go to end of list */
    ptraddr = &((*ptraddr)->next);/* Prepare what we need to change */
  *ptraddr = malloc(sizeof(struct listnode)); /* Space for new node */
  (*ptraddr)->value = v;                               /* Put value */ 
  (*ptraddr)->next = NULL;              /* There is no next element */
}

int delete(Listptr *ptraddr, int v)
               /* Delete element v from list *ptraddr, if it exists */
{ Listptr templist;
  while ((*ptraddr) != NULL)   /* Visit list elements up to the end */
    if ((*ptraddr)->value == v) {    /* Did we find what to delete? */
      templist = *ptraddr;         /* Yes, save address of its node */
      *ptraddr = (*ptraddr)->next;        /* Bypass deleted element */
      free(templist);     /* Free memory for the corresponding node */
      return 1;                           /* We deleted the element */
    }
    else
      ptraddr = &((*ptraddr)->next);/* Prepare what we might change */
  return 0;        /* We did't find the element we were looking for */
}

void print(Listptr list)                  /* Print elements of list */
{ while (list != NULL) {       /* Visit list elements up to the end */
    printf("%d--> ", list->value);         /* Print current element */
    list = list->next;                        /* Go to next element */
  }
  printf("NULL\n");                            /* Print end of list */
}

void free_list(Listptr *ptraddr)
{ Listptr templist = *ptraddr;
  while(*ptraddr != NULL) {
      *ptraddr = (*ptraddr)->next;
      free(templist);
      templist = *ptraddr;
  }
  *ptraddr = NULL; 
}

This code comes from the course of ip, from DIT, Athens.

sort_list.c

Below we sort the list, based on QuickSort.

#include <stdio.h>
#include "fun.h"

void quickSort(Listptr a, int first, int last);
int pivot(Listptr a, int first, int last);
void swap(Listptr list, int a_pos, int b_pos);

int main() {

  Listptr alist;
  alist = NULL; /* List is NULL */


  insert_at_start(&alist, 7);
  insert_at_start(&alist, -13);
  insert_at_start(&alist, 1);
  insert_at_start(&alist, 3);
  insert_at_start(&alist, 10);
  insert_at_start(&alist, 5);
  insert_at_start(&alist, 2);
  insert_at_start(&alist, 4);
  int N = size(alist);

  printf("Before sorting : \n");
  print(alist);

  quickSort(alist, 1, N);

  printf("After sorting : \n");
  print(alist);

  return 0;
}

void quickSort(Listptr a, int first, int last) {
  int pivotElement;

  if (first < last) {
    pivotElement = pivot(a, first, last);
    quickSort(a, first, pivotElement - 1);
    quickSort(a, pivotElement + 1, last);
  }
}

int pivot(Listptr a, int first, int last) {
  int tempElement, pivotElement, i, p = first;
  n_th(a, first, &pivotElement);

  for (i = first + 1; i <= last; i++) {
    n_th(a, i, &tempElement);
    if (tempElement <= pivotElement) {
      p++;
      swap(a, i, p);
    }
  }

  swap(a, p, first);

  return p;
}

void swap(Listptr list, int a_pos, int b_pos) {
  int temp_a, temp_b;
  n_th(list, a_pos, &temp_a);
  n_th(list, b_pos, &temp_b);
  write_n_th(list, a_pos, temp_b);
  write_n_th(list, b_pos, temp_a);
}

Have questions about this code? Comments? Did you find a bug? Let me know! :D
Page created by G. (George) Samaras (DIT)

3 thoughts on “List (C)

  1. Pingback: Linked List Process in C

  2. Pingback: Singly-linked list

  3. Pingback: Reading files of unknown size

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s