Google Answers Logo
View Question
Q: Linked list 'c'-UPDATED PRICE ( Answered,   1 Comment )
Subject: Linked list 'c'-UPDATED PRICE
Category: Computers > Programming
Asked by: linkinpark-ga
List Price: $25.00
Posted: 03 Mar 2004 09:20 PST
Expires: 02 Apr 2004 09:20 PST
Question ID: 312972
Need someone to write a simple linked list.  Here are the details, I
need a struct of "dogs", the struct will have two fields (for
shortness sake), one field will be name, the other, owners name.  I
need a way to add more dogs, a linked list needs to be used.  It needs
the normal operations: add, remove. But it also needs a sort.(be sure
to give an example on how to "call" each of these, just in case)  The
sort should sort by dogs name.  This needs to be in 'C'. Also, it has
to have a sort function i.e. you cant put the items into the list "in
order".  A good tip
will be given to a great answer

Clarification of Question by linkinpark-ga on 03 Mar 2004 09:21 PST
Also needs an function to output the list

Request for Question Clarification by mathtalk-ga on 03 Mar 2004 17:23 PST
Hi, linkinpark-ga:

Your description of this programming assignment ("write a simple
linked list") is not very clear.  Perhaps by simple you mean "singly

The topic of manipulating linked lists in C has come up on Google
Answers threads before, e.g.

You'll notice there that the Customer got help from a couple of
knowledgeable Researchers, but what expedited the discussion was the
code written by the Customer.  Dealing with fixing a few demonstrable
bugs in a known program is much more tractable than trying to write a
satisfactory program from loose requirements.

Let's identify some of the goals:

The linked list relates to some to-be-defined struct "dogs" which has
two (character string) fields.

You've asked for code to implement/illustrate adding "dogs", removing
them, and sorting by dogs' names.

Perhaps looking at the Question "linked" above will partly clarify for
you how these operations can be done in C.  Narrowing your own
Question would go a long way toward helping a Researcher to provide a
well thought out Answer.  In C the code to do each kind of
manipulation might be written out "in line" in the main routine, or it
might be isolated in individual routines (functions) for better reuse.
 You will probably have a preference in this respect.

regards, mathtalk-ga

Request for Question Clarification by studboy-ga on 03 Mar 2004 19:23 PST

Is your compiler gcc?
I might be able to help.
I'm assuming you have an add function:

add(list, dogname, ownername);

a delete:

delete(list, dogname)

a sort:


and a print:


Clarification of Question by linkinpark-ga on 03 Mar 2004 20:07 PST
Ok, let me try to clarify a few things.  Yes, a singly linked list if fine.

  hear is a "psuedo" example:
      say, i have this struct, or a similar one:
                  struct dog{
                        char name[20];
                        char ownersname[20];
     so the linked list would be a list of dogs.  Does that make more sense?
    I want the user to be able to add a dog to the list, remove a dog,
and sort the dogs by name, also to output the whole list of dogs.

           I think something like this may work to start out , but i
am not sure:    typedef struct dog_list_node_struct {
                            char name[20];
                            char ownername[20];
                            struct dog_list_node_struct *next;
                            } dog_list_node;
Hopefully, this is enough info to get someone started.
Subject: Re: Linked list 'c'-UPDATED PRICE
Answered By: studboy-ga on 03 Mar 2004 20:18 PST
Here you go--examples of calling each function is in main.  Use gcc to compile:

#include "stdio.h"

typedef struct dog dog;
struct dog {
   char name[20];       /* The dog's name                         */
   char owner[20];      /* The owner of dog                       */
   dog *next;           /* Pointer to the next dog                */

/* For list update operations, return new head pointer since that may
change (after deletion, sorting, etc.) */

dog *addtolist(dog *list, char *name, char *owner) { /* Traverse list
and add to the end */
   dog *tmp, *cur;

   tmp = (struct dog *)malloc(sizeof(struct dog));
   strcpy(tmp->name, name);
   strcpy(tmp->owner, owner);
   tmp->next = NULL;

   cur = list;
   if (cur == NULL) {
      list = tmp;
   } else {
      while (cur->next != NULL)
        cur = cur->next;
      cur->next = tmp;

   return list;

dog *removefromlist(dog *list, char *name) { /* Traverse list and
remove matching element(s) */
   dog *tmp = NULL, *cur;

   cur = list;
   while (cur != NULL) {
      if (strcmp(cur->name, name) == 0) { /* A match in name */
         if (cur->next == NULL && tmp == NULL) { /* Only element case */
            list = NULL;
         } else { 
            if (tmp == NULL) { /* First element case */
               list = cur->next;
               cur = list;
            } else {
               tmp->next = cur->next;
               cur = tmp->next;
      tmp = cur;
      cur = tmp->next;
   return list;

/* print does not alter list so does not need to return head pointer */

void printlist(dog *list) {
   dog *point;
   point = list;
   while (point != NULL)
      printf("%s is owned by %s.\n", point->name, point->owner);
      point = point->next;

dog *sortlist(dog *list) { /* This sort algorithm is based on
mergesort--see web page link in comments */
    dog *p, *q, *e, *tail, *oldhead;
    int insize, nmerges, psize, qsize, i;

    if (!list)
	return NULL;

    insize = 1;

    while (1) {
        p = list;
	oldhead = list;		       /* only used for circular linkage */
        list = NULL;
        tail = NULL;

        nmerges = 0;  /* count number of merges we do in this pass */

        while (p) {
            nmerges++;  /* there exists a merge to be done */
            /* step `insize' places along from p */
            q = p;
            psize = 0;
            for (i = 0; i < insize; i++) {
		q = q->next;
                if (!q) break;

            /* if q hasn't fallen off end, we have two lists to merge */
            qsize = insize;

            /* now we have two lists; merge them */
            while (psize > 0 || (qsize > 0 && q)) {

                /* decide whether next element of merge comes from p or q */
                if (psize == 0) {
		    /* p is empty; e must come from q. */
		    e = q; q = q->next; qsize--;
		} else if (qsize == 0 || !q) {
		    /* q is empty; e must come from p. */
		    e = p; p = p->next; psize--;
		} else if (strcmp(p->name, q->name) <= 0) {
		    /* First element of p is lower (or same);
		     * e must come from p. */
		    e = p; p = p->next; psize--;
		} else {
		    /* First element of q is lower; e must come from q. */
		    e = q; q = q->next; qsize--;

                /* add the next element to the merged list */
		if (tail) {
		    tail->next = e;
		} else {
		    list = e;
		tail = e;

            /* now p has stepped `insize' places along, and q has too */
            p = q;
	tail->next = NULL;

        /* If we have done only one merge, we're finished. */
        if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
            return list;

        /* Otherwise repeat, merging lists twice the size */
        insize *= 2;

main() { /* Main test program: examples of calling the above functions */

   dog *list;

   list = addtolist(NULL,"Jim","Jason");

   printf("\nInitial list:\n");
   list = addtolist(list,"Jack","Jill");
   list = addtolist(list,"John","Jennifer");

   printf("\nAfter adding to list:\n");
   list = sortlist(list);

   printf("\nAfter sorting list:\n");
   list = removefromlist(list,"Jack");

   printf("\nAfter removing from list:\n");

Request for Answer Clarification by linkinpark-ga on 03 Mar 2004 20:42 PST
is there any way to pass the whole struct or do you have to pass the
elements individually?  I dont assume it really matters unless there
are alot of elements in the struct, just wandering though

Clarification of Answer by studboy-ga on 03 Mar 2004 21:53 PST
Hi linkinpark-ga

The element *IS* a pointer to the whole structure--
I assume by whole structure you meant the entire linked list?
Or do you mean the dog name, owner name pairs when you make the function call?
You can pass anything to anything (the beauty of C and pointers).

Hope thi shelps.
Subject: Re: Linked list 'c'-UPDATED PRICE
From: studboy-ga on 03 Mar 2004 20:22 PST

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy