Stack implementation of Linked List

[Kenny McCormack]

What, and eliminate his entire raison d'être? If he did that, the
implosion would leave a greater void than the Tunguska event.

Richard

Quite possibly so. Still, I doubt it would compare to the seismic
effects we'd see if Kiki actually let something go.

 

[Barry Schwarz]

Any advice, implemented only one operation yet. Will implement others if
this one is okay:

/* A Stack implementation of a singly linked list with 4 operations: Pop, Push, Top and Print elements in the list.
 *
 * VERISON 0.0
 *
 */

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

enum { STACK_ARR_SIZE = 10 };

struct my_stack
{
  char arrc[STACK_ARR_SIZE];
  struct my_stack* next;

};

struct stack_list
{
  struct my_stack* head;

};

struct stack_list* push( struct stack_list*, const char* );
struct stack_list* pop( struct stack_list* );
struct stack_list* top( struct stack_list* );

struct stack_list* stack_new( void );
void stack_print( const struct stack_list* );
void stack_print_element( const struct my_stack* );
void stack_free( struct my_stack* );

int main( void )
{
  struct stack_list* ms = NULL;
  ms = stack_new();

stack_new can fail. Once you fix the undefined behavior there, either
that function needs to abort the program or you need to check for the
failure here. Checking in each of the operation functions seems
inefficient.

  stack_print(ms);

  push(ms, "comp");
  push(ms, "(dot)");
  push(ms, "lang");
  push(ms, "(dot)");
  push(ms, "c");

  stack_print(ms);

  return 0;

}

struct stack_list* push(struct stack_list* s, const char* c )

You always return the same value of s that you were provided. (What s
points to may change but that does not affect the value of s itself.)
Seems like a waste.

{
  struct my_stack* p = malloc( 1 * sizeof *p );
  struct my_stack* n = NULL;

  if( NULL == p )
    {
      fprintf(stderr, "malloc() failed\n");
      return s;
    }

  strcpy(p->arrc, c);
  p->next = NULL;

  if( NULL == s )
    {
      fprintf(stderr, "Stack not initialized ?\n");
      return s;

You now have a memory leak. p points to allocated memory and p will
disappear as soon as this function returns. You will never be able to
free the memory p points to.

    }
  else if( NULL == s->head )
    {
      /*      printf("Stack is Empty, adding first element\n"); */
      s->head = p;
      return s;
    }
  else
    {
      /*      printf("Stack not Empty, adding in front of first element\n"); */
      n = s->head;  /* save current head */
      s->head = p;  /* push new element onto the head */
      s->head->next = n; /* attach the earlier saved head to the next of new element */

Since s->head is guranteed to equal p, this would be easier as
p->next = n;

    }

  return s;

}

/* ---------- small helper functions -------------------- */
struct stack_list* stack_new( void )
{
  struct stack_list* p = malloc( 1 * sizeof *p );

  if( NULL == p )
    {
      fprintf(stderr, "malloc() in Stack Initialization failed\n");

At this point you know p is NULL. But you allow the code to fall
through ...

    }

  p->head = NULL;

.... and here you dereference the null pointer!

 

[arnuld]

... SNIP...

stack_new can fail. Once you fix the undefined behavior there, either
that function needs to abort the program or you need to check for the
failure here. Checking in each of the operation functions seems
inefficient.

I check in each operation because those operations can be run
independent of of stack_new(), you just have to provide a pointer to
stack_list type and that can be done without using stack_new() (e.g.
like using a NULL pointer). It won't help in such a small program but
in bigger programs which have 16 source files and around 10 headers
where function calls are made at many places, I will never have any
idea when something will go NULL. I work in a compnay and that
Segfaults happen most of the time when whole team of 5 people sit
together to write code for one application. With my check in each
operation, I was ablw to know the reasons of Segfaults at many time,
the add/remove (push/pop) operations were gettign NULL arguments. So
these checks are not for this small program but for programs written
by teams in a corporate. I have just made a habit of it.


How is this new fixed code:


/* A Stack implementation of a singly linked list with 4 operations:
Pop, Push, Top and Print elements in the list.
*
* VERISON 0.3
*
*/

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

enum { STACK_ARR_SIZE = 10 };

struct my_stack
{
char arrc[STACK_ARR_SIZE];
struct my_stack* next;
};

struct stack_list
{
struct my_stack* head;
};


struct stack_list* push( struct stack_list*, const char* );
struct stack_list* pop( struct stack_list* );
struct my_stack* top( struct stack_list* );
struct my_stack* make_null( struct stack_list* );
struct my_stack* is_empty( struct stack_list* );


struct stack_list* stack_new( void );
void stack_print( const struct stack_list* );
void stack_print_element( const struct my_stack* );
struct stack_list* stack_free( struct stack_list* );


int main( void )
{
struct my_stack* p = NULL;
struct stack_list* ms = NULL;
ms = stack_new();

stack_print(ms);

push(ms, "comp");
push(ms, "(dot)");
push(ms, "lang");
push(ms, "(dot)");
push(ms, "c");

stack_print(ms);

pop(ms);
p = top(ms);
stack_print_element(p);
printf("---------------------------\n");
stack_print(ms);

stack_free(ms);
free(ms);
ms = NULL;

return 0;
}


struct stack_list* push(struct stack_list* s, const char* c )
{
struct my_stack* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() failed\n");
return s;
}

strcpy(p->arrc, c);
p->next = NULL;

if( NULL == s )
{
fprintf(stderr, "Stack not initialized ?\n");
free(p);
return s;
}
else if( NULL == s->head )
{
/* printf("Stack is Empty, adding first element\n"); */
s->head = p;
return s;
}
else
{
/* printf("Stack not Empty, adding in front of first element
\n"); */
p->next = s->head;
s->head = p; /* push new element onto the head */
}

return s;
}


struct stack_list* pop( struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("There is no stack list ?\n");
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}
else
{
p = s->head;
s->head = s->head->next;
free(p);
}

return s;
}


struct my_stack* top( struct stack_list* s)
{
if( NULL == s )
{
printf("There is no stack list ?\n");
return NULL;
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}


return s->head;
}


/* Make a Stack empty */
struct my_stack* make_null( struct stack_list* s )
{
if( NULL == s )
{
printf("Can not make NULL when there is no Stack List\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is already Empty\n");
}
else
{
stack_free(s);
}

return s->head;
}


struct my_stack* is_empty( struct stack_list* s )
{
if( NULL == s )
{
printf("There is no Stack\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is Empty\n");
}
else
{
printf("Stack is not Empty\n");
}

return s->head;
}



/* ---------- small helper functions -------------------- */
struct stack_list* stack_free( struct stack_list* s )
{
if( NULL == s )
{
printf("Can't free a NULL stack list\n");
}

while( s->head ) pop(s);

return s;
}


struct stack_list* stack_new( void )
{
struct stack_list* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() in Stack Initialization failed\n");
exit( EXIT FAILURE ); /* There is no point in going beyond this
point */
}

p->head = NULL;

return p;
}


void stack_print( const struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("Can not print an Empty Stack\n");
}
else
{
for( p = s->head; p; p = p->next ) stack_print_element(p);
}

printf("-------------------------- \n");
}


void stack_print_element(const struct my_stack* s)
{
printf("arrc = %s\n", s->arrc);
}

 

[arnuld]

Array element of Stack remained to be fixed, so here is the fixed
version:

/* A Stack implementation of a singly linked list with 4 operations:
Pop, Push, Top and Print elements in the list.
*
* VERISON 0.4
*
*/

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

enum { STACK_ARR_SIZE = 10 };

struct my_stack
{
char arrc[STACK_ARR_SIZE]; /* Thar array must not have more thab
(STACK_ARR_SIZE - 1) elements */
struct my_stack* next;
};

struct stack_list
{
struct my_stack* head;
};


struct stack_list* push( struct stack_list*, const char* );
struct stack_list* pop( struct stack_list* );
struct my_stack* top( struct stack_list* );
struct my_stack* make_null( struct stack_list* );
struct my_stack* is_empty( struct stack_list* );


struct stack_list* stack_new( void );
void stack_print( const struct stack_list* );
void stack_print_element( const struct my_stack* );
struct stack_list* stack_free( struct stack_list* );


int main( void )
{
struct my_stack* p = NULL;
struct stack_list* ms = NULL;
ms = stack_new();

stack_print(ms);

push(ms, "comppppppppppppppppp");
push(ms, "(dot)");
push(ms, "lang");
push(ms, "(dot)");
push(ms, "c");

stack_print(ms);

pop(ms);
p = top(ms);
stack_print_element(p);
printf("---------------------------\n");
stack_print(ms);

stack_free(ms);
free(ms);
ms = NULL;

return 0;
}


struct stack_list* push(struct stack_list* s, const char* c )
{
struct my_stack* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() failed\n");
return s;
}

/* If use gave us more characters than what we want, then its his
problem */
if( strlen(c) < STACK_ARR_SIZE ) strcpy(p->arrc, c);
p->next = NULL;


if( NULL == s )
{
fprintf(stderr, "Stack not initialized ?\n");
free(p);
return s;
}
else if( NULL == s->head )
{
/* printf("Stack is Empty, adding first element\n"); */
s->head = p;
return s;
}
else
{
/* printf("Stack not Empty, adding in front of first element
\n"); */
p->next = s->head;
s->head = p; /* push new element onto the head */
}

return s;
}


struct stack_list* pop( struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("There is no stack list ?\n");
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}
else
{
p = s->head;
s->head = s->head->next;
free(p);
}

return s;
}


struct my_stack* top( struct stack_list* s)
{
if( NULL == s )
{
printf("There is no stack list ?\n");
return NULL;
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}


return s->head;
}


/* Make a Stack empty */
struct my_stack* make_null( struct stack_list* s )
{
if( NULL == s )
{
printf("Can not make NULL when there is no Stack List\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is already Empty\n");
}
else
{
stack_free(s);
}

return s->head;
}


struct my_stack* is_empty( struct stack_list* s )
{
if( NULL == s )
{
printf("There is no Stack\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is Empty\n");
}
else
{
printf("Stack is not Empty\n");
}

return s->head;
}



/* ---------- small helper functions -------------------- */
struct stack_list* stack_free( struct stack_list* s )
{
if( NULL == s )
{
printf("Can't free a NULL stack list\n");
}

while( s->head ) pop(s);

return s;
}


struct stack_list* stack_new( void )
{
struct stack_list* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() in Stack Initialization failed\n");
exit( EXIT_FAILURE ); /* There is no point in going beyond this
point */
}

p->head = NULL;

return p;
}


void stack_print( const struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("Can not print an Empty Stack\n");
}
else
{
for( p = s->head; p; p = p->next ) stack_print_element(p);
}

printf("-------------------------- \n");
}


void stack_print_element(const struct my_stack* s)
{
printf("arrc = %s\n", s->arrc);
}


================== OUTPUT =================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra stack.c
[arnuld@dune programs]$ ./a.out
--------------------------
arrc = c
arrc = (dot)
arrc = lang
arrc = (dot)
arrc =

 

[Barry Schwarz]

Array element of Stack remained to be fixed, so here is the fixed
version:
snip

struct stack_list* push(struct stack_list* s, const char* c )
{
  struct my_stack* p = malloc( 1 * sizeof *p );

  if( NULL == p )
    {
      fprintf(stderr, "malloc() failed\n");
      return s;

I expect a user would like his calling function to know if this
function succeeded or not.

    }

  /* If use gave us more characters than what we want, then its his
problem */
  if( strlen(c) < STACK_ARR_SIZE ) strcpy(p->arrc, c);
  p->next = NULL;

  if( NULL == s )

If you do this test at the top of the function, you can eliminate the
free since you will nhjot yet have called malloc.

    {
      fprintf(stderr, "Stack not initialized ?\n");
      free(p);
      return s;
    }
  else if( NULL == s->head )
    {
      /*      printf("Stack is Empty, adding first element\n"); */
      s->head = p;
      return s;
    }
  else
    {
      /*      printf("Stack not Empty, adding in front of first element
\n"); */
      p->next = s->head;
      s->head = p;  /* push new element onto the head */
    }

  return s;

}
snip

struct stack_list* pop( struct stack_list* s )
{
  struct my_stack* p = NULL;

  if( NULL == s )
    {
      printf("There is no stack list ?\n");
    }
  else if( NULL == s->head )
    {
      printf("There is no element on the stack\n");
    }
  else
    {
      p = s->head;
      s->head = s->head->next;

s-head = p->next; /*it just seems cleaner*/

      free(p);
    }

  return s;

}

snip

 

[Ben Bacarisse]

Array element of Stack remained to be fixed, so here is the fixed
version:

struct my_stack
{
char arrc[STACK_ARR_SIZE]; /* Thar array must not have more thab
(STACK_ARR_SIZE - 1) elements */
struct my_stack* next;
};

<snip>

In list insert function:

/* If use gave us more characters than what we want, then its his
problem */
if( strlen(c) < STACK_ARR_SIZE ) strcpy(p->arrc, c);

This is an odd way to fix the problem. You leave lurking undefined
behaviour this way -- the user of this code can't tell if it worked or
not and examining the string they thought they stored in the array will
produce UB. It would be better to one of these:

(a) signal to the use that this failed;
(b) set the string to something they can test like p->arrc[0] = 0;
(c) copy no more characters than will fit rather than no writing
anything.