linked lists 
Author Message
 linked lists

I am a new programmer(teaching myself) and am having problems
implimenting a linked list.  I can get a list in, but cannot get it in
order.  Any suggestions?



Thu, 06 Jan 2000 03:00:00 GMT  
 linked lists

Quote:

> I am a new programmer(teaching myself) and am having problems
> implimenting a linked list.  I can get a list in, but cannot get it in
> order.  Any suggestions?

Visit http//:home.cc.umanitoba.ca/~mitchl


Fri, 07 Jan 2000 03:00:00 GMT  
 linked lists

Quote:

> I am a new programmer(teaching myself) and am having problems
> implimenting a linked list.  I can get a list in, but cannot get it in
> order.  Any suggestions?

Hi Bruce Kube,

Your description is very vague and does not contain any clues as to what
your problem really is. Could you please rephrase it and maybe try to
add some code sample of what's not working.

Might it be that you are trying to sort an existing linked list ?
Please clarify.

Stephan
(initiator of the campaign against grumpiness in c.l.c)



Fri, 07 Jan 2000 03:00:00 GMT  
 linked lists



Quote:
> I am a new programmer(teaching myself) and am having problems
> implimenting a linked list.  I can get a list in, but cannot get it in
> order.  Any suggestions?

Try using the qsort() function.  You can give qsort() the size of the array
elements,
the number of elements and the compare function.  For example:

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

/* Be sure to prototype your compare function */

int compare(const void *, const void *);

int main()
{
   int i;
   int *nArray = NULL;
   int nArraySize = 0;

   ......
   ......     /* some code to allocate and store your link list */
   ......

   qsort(nArray, nArraySize, sizeof(int), compare)

   ......
   ......     /* some code to aft process your link list */
   ......

Quote:
}

int compare(const void *a, const void *b)
{
   return(*(int *)a - *(int *)b);

Quote:
}

This particular example is setup to return an integer.  You should easily
be able to modify this snippet to return anything you need.

--
                              \\|//
                             \\   //

+-----------------oOOO-----(_)-----OOOo-----------------------+
|                          Gary W Hellman                        |

+------------------------------------------------------------------------+
                      oooO    Oooo
                       (   )        (   )
                        \ (          ) /
                        \_)        (_/



Sat, 08 Jan 2000 03:00:00 GMT  
 linked lists


Quote:

> Try using the qsort() function.  You can give qsort() the size of the
> array elements,
> the number of elements and the compare function.  For example:

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

> /* Be sure to prototype your compare function */

> int compare(const void *, const void *);

> int main()
> {
> int i;
> int *nArray = NULL;
> int nArraySize = 0;

> ......
> ......     /* some code to allocate and store your link list */
> ......

> qsort(nArray, nArraySize, sizeof(int), compare)

> ......
> ......     /* some code to aft process your link list */
> ......
> }

> int compare(const void *a, const void *b)
> {
> return(*(int *)a - *(int *)b);
> }

> This particular example is setup to return an integer.  You should
> easily be able to modify this snippet to return anything you need.

qsort() will not work with a linked list (unless the list happens also
to be an array - in which case there's little point in setting links).

Your last comment seems to refer to the 'compare' function. That
function *must* return int. That is a requirement for qsort().

--



Sun, 09 Jan 2000 03:00:00 GMT  
 linked lists

If you have really got a linked list which is usually allocated from
the heap per item, you cannot qsort it. qsort() only sorts arrays
of objects.

What you can do however, is to create an array of pointers to each
of the linked list elements, then use qsort to sort the array of
pointers, using a suitable comparison function. This may or may
not be useful in your application. but the nice thing about is
you can create multiple arrays of pointers and sort them using
different criteria, (age, sex, weight) etc, so index your data
in as many ways as you can think of, and its very easy to do.

Michael



Sun, 09 Jan 2000 03:00:00 GMT  
 linked lists

Quote:

> I am a new programmer(teaching myself) and am having problems
> implimenting a linked list.  I can get a list in, but cannot get it in
> order.  Any suggestions?

What you need to do is find the point at which an inserted item should
go, then 'break' the list at that point and put the item in. For
example, suppose you have the list

a->b->d->e

and you want to insert c. You search through your list until you see
that either the item you want to insert should go before the next
item, or you've reached the end of the list. You then set up your new
item to point to the item it should go before:

a->b->d->e
    c-^

(c points to d). Now you can set the item before the one you're
inserting to point to the inserted item:

a->b->c->d->e

and you're done.

--

            http://www.geocities.com/SiliconValley/Lakes/7537/
Supporter of the campaign against grumpiness in c.l.c



Sun, 09 Jan 2000 03:00:00 GMT  
 linked lists



Quote:

>> I am a new programmer(teaching myself) and am having problems
>> implimenting a linked list.  I can get a list in, but cannot get it in
>> order.  Any suggestions?

>Visit http//:home.cc.umanitoba.ca/~mitchl

Linked lists are frequently an important part of C language courses.
Usually an assignment requires modification of any existing implementation
which, of course, is a good thing.

I am providing below a complete list package that can (probably) be
modified to meet many assignments. The modification process can be very
important. The code below includes a display function that permits the
user to experiment with his/her implementations and really see the results.
There are also a few pictures to help someone just learning.

                         __     __  _____  ______  _____
                        |  |   |  |/  ___>|_    _|/  ___>
                        |  |__ |  |\___  \  |  |  \___  \
                        |_____||__|<_____/  |__|  <_____/

   Basic singly linked list (linked list_s).

        +-+       +---+    +---+             +---+    +---+
        |*+------>|obj|    |obj|             |obj|    |obj|
        +-+       +---+    +---+             +---+    +---+
                  | * |--->| * |---> ... --->| * |--->| * |--->NULL
                  +---+    +---+             +---+    +---+

+--------------- Linked List Representation -------------------- 01 ---+
   typedef struct object {                 /* An illustrative object. */
      int  key;
      char data[16];
   } object;

   typedef struct node {                    /* Node for singly and    */
      object        the_obj;                /* circular linked lists. */
      struct node  *next;
   } node_s;

    typedef node_s *LL_s;                    /* List representations. */

+--------------- Function Declarations ------------------------- 02 ---+
    int  size               (LL_s L);
    void display            (LL_s L);

    int insert_first        (LL_s *L_ptr, object new_obj);
    int insert_last         (LL_s *L_ptr, object new_obj);

    int delete_first        (LL_s *L_ptr);
    int delete_last         (LL_s *L_ptr);

    object* retrieve_first  (LL_s L);
    object* retrieve_last   (LL_s L);

+--------------- Function Implementations ---------------------- 03 ---+

/*------------------------+---------------------+---------+-----------*/
/*     list_size          |   linked list_s     |  O(n)   |   6-0-1   */
/*------------------------+---------------------+---------+-----------*/
    int list_size (LL_s L) {
       int  count = 0;
       for (; L != NULL; L = L->next)
          count++;
       return count;
    }
/*------------------------+---------------------+---------+-----------*/
/*    retrieve_first      |   linked list_s     |  O(1)   |   3-0-0   */
/*------------------------+---------------------+---------+-----------*/
    object* retrieve_first (LL_s L) {
       return (L != NULL) ? &(L->the_obj) : NULL;
    }
/*------------------------+---------------------+---------+-----------*/
/*   retrieve_last        |   linked list_s     |  O(n)   |   6-1-1   */
/*------------------------+---------------------+---------+-----------*/
   object* retrieve_last (LL_s ptr) {
      if (ptr == NULL) return NULL;
      while (ptr->next != NULL)
         ptr = ptr->next;
      return &(ptr->the_obj);
   }
/*------------------------+---------------------+---------+-----------*/
/*   insert_first         |   linked list_s     |  O(1)   |   8-1-0   */
/*------------------------+---------------------+---------+-----------*/
    int insert_first (LL_s *L_ptr, object new_obj) {
       node_s *new_ptr = (node_s*) malloc (sizeof(node_s));
       if (new_ptr == NULL) return 0;
       new_ptr->the_obj = new_obj;
       new_ptr->next = *L_ptr;
       *L_ptr = new_ptr;
       return 1;
    }

        +-+               +---+    +---+             +---+
        |*+-+..........+->|obj|    |obj|             |obj|
        +-+ |   +---+  |  +---+    +---+             +---+
         L  +-->|new|  |  | *-+--->| *-+---> ... --->| *-+-->NULL
                +---+  |  +---+    +---+             +---+
                | * |--+
                +---+
/*   +----------------+   +----------------+   +------+   +-------+   */
/*---| insert_last    |---| linked list_s  |---| O(n) |---|14-2-1 |---*/
/*   +----------------+   +----------------+   +------+   +-------+   */
   int insert_last (LL_s *L_ptr, object new_obj) {
      node_s *new_ptr = (node_s*) malloc (sizeof(node_s));

      if (new_ptr == NULL) return 0;
      new_ptr->the_obj = new_obj;
      new_ptr->next = NULL;

      if (*L_ptr == NULL) *L_ptr= new_ptr;
      else {
         node_s *ptr = *L_ptr;
         while (ptr->next != NULL)
            ptr = ptr->next;
         ptr->next = new_ptr;
      }
      return 1;
   }
/*   +----------------+   +----------------+   +------+   +-------+   */
/*---| delete_first   |---| linked list_s  |---| O(1) |---| 5-1-0 |---*/
/*   +----------------+   +----------------+   +------+   +-------+   */
   int delete_first  (LL_s *L_ptr) {
      if (*L_ptr == NULL) return 0;
      *L_ptr= (*L_ptr)->next;
      return 1;
   }

             +------------+
        +-+  |    +---+   |   +---+    +---+    +---+
        |*+--+...>|obj|   +-->|obj|    |obj|    |obj|
        +-+       +---+       +---+    +---+    +---+
         L        | *-+......>| *-+--->| *-+--->| *-+->NULL
                  +---+       +---+    +---+    +---+

/*   +----------------+   +----------------+   +------+   +-------+   */
/*---| delete_last    |---| linked list_s  |---| O(n) |---|11-2-1 |---*/
/*   +----------------+   +----------------+   +------+   +-------+   */
   int delete_last (LL_s *L_ptr) {
      if (*L_ptr == NULL) return 0;
      else if ((*L_ptr)->next == NULL) *L_ptr= NULL;
      else {
         node_s *ptr = *L_ptr;
         while (ptr->next->next != NULL)
            ptr = ptr->next;
         ptr->next = NULL;
      }
      return 1;
   }

           +-+       +---+    +---+    +---+      +---+
           |*+------>|obj|    |obj|    |obj|      |obj|
           +-+       +---+    +---+    +---+      +---+
            L        | *-+--->| *-+--->| *-+-+...>| *-+->NULL
                     +---+    +---+    +---+ |    +---+
                                             |
                                             +---> NULL
+--------------- Sample main ----------------------------------- 04 ---+
int main (int argc, char *argv[]) {
   char *s1 = "+-----------------------";
   char *s2 = "-----------------------+";
   char *s3 = "                        ";
   char *s4 = "+----------------------+";
   char *sA = "| Test insert_first    |";
   char *sB = "| Test insert_last     |";
   char *sC = "| Test delete_first    |";
   char *sD = "| Test delete_last     |";
   char *sE = "| Test retrieve first, |";
   int k;
   LL_c     SL = NULL;
   object   obj, *obj_ptr;

  /*------------------------------------------------------------------*/
   printf("%s%s\n",s3,s4);
   printf("%s%s%s\n",s1,sA,s2);   /* Insert First */
   printf("%s%s\n",s3,s4);
   for (k = 1; k <= 3; k++) {
      obj.key = 75 - 5*k;   /* 10 15 20 */
      insert_first (&SL, obj);
   }
   display (SL);
  /*------------------------------------------------------------------*/
   printf("%s%s\n",s3,s4);
   printf("%s%s%s\n",s1,sB,s2);   /* Insert Last */
   printf("%s%s\n",s3,s4);
   for (k = 1; k <= 3; k++) {
      obj.key = 75 + 5*k;   /* 10 15 20 */
      insert_last (&SL, obj);
   }
   display (SL);

Quote:
}

+--------------- Function Display         ---------------------- 05 ---+

/*------------------------+---------------------+---------+-----------*/
/*    put_a_row           |   linked list_?     |   O(1)  |   7-3-1   */
/*------------------------+---------------------+---------+-----------*/
    void put_a_row (int n,char *s1,char *s2,char ch1,char ch2) {
       if  (n > 0 || s1[3] != ' ')  printf (s1);
       for (int k = 1; k < n; k++)  printf (s2, ch1);
       if  (n > 0)                  printf (s2, ch2);
       if  (n > 0 && ch2 == '>')    printf ("NULL");
       putchar ('\n');
    }
/*------------------------+---------------------+---------+-----------*/
/*   display_list         |   linked list_s     |  O(n)   |  15-1-1   */
/*------------------------+---------------------+---------+-----------*/
    void display_list (LL_s p) {
       char *s1 = "   +-+     ",  *sA = "+--+  %c",
            *s2 = "    L      ",  *sB = "|  |--%c",
            *s3 = "           ";

       int n = list_size (p);
       put_a_row (n,s1,sA,' ',' ');                    /* 1 */
       printf ("   |*|---->");                         /* 2 */
       for (int k = n; k > 0; p = p->next, k--)
          printf ("|%2d|   ", p->the_obj.key);
       if (n) printf ("\n");
       else   printf ("NULL\n");
       put_a_row (n,s1,sA,' ',' ');                    /* 3 */
       put_a_row (n,s2,sB,'>','>');                    /* 4 */
       put_a_row (n,s3,sA,' ','|');                    /* 5 */
    }

        +-+    +--+   +--+   +--+   +--+   +--+        <1>
        |*|--->|77|   |80|   |86|   |89|   |92|        <2>
        +-+    +--+   +--+   +--+   +--+   +--+        <3>
               |  |-->|  |-->|  |-->|  |-->|  |-->NULL <4>
               +--+   +--+   +--+   +--+   +--+        <5>



Sun, 09 Jan 2000 03:00:00 GMT  
 linked lists

: I am a new programmer(teaching myself) and am having problems
: implimenting a linked list.  I can get a list in, but cannot get it in
: order.  Any suggestions?

Get the list in order?  You need to put it in order as you are adding to
it.



Tue, 11 Jan 2000 03:00:00 GMT  
 linked lists

Quote:


> : I am a new programmer(teaching myself) and am having problems
> : implimenting a linked list.  I can get a list in, but cannot get it in
> : order.  Any suggestions?
> Get the list in order?  You need to put it in order as you are adding to
> it.

As has been pointed out, building a linked list in the proper order make
take more time and overhead that building it, then sorting it.  Further,
if there are two or more different possible sort orders, you may still
have to sort.

You need to look up sorting algorithyms, there are a lot of good books
and references available, search the `Net or search you local
bookstore.  BubbleSort and QuickSort come to mind, but there are others.

P.S. If the list is large (10,000 or more nodes) you may want to keep
the list on disk and use b-tree indices to track sort order.

You may e:mail if you want to learn more.

--
********************************************

********************************************
It used to be:
Spare the rod and spoil the child.

Today it's:
Spare the rod to stay out of jail.



Fri, 14 Jan 2000 03:00:00 GMT  
 linked lists

Quote:
> BubbleSort and QuickSort come to mind, but there are others.

Indeed.  Bubble sort comes first into mind -- as an algorithm that should
be expunged from every textbook and replaced with an explanation as to why
it is not a suitable choice under any circumstances.

I'm at home, so I say anything I please.



Sat, 15 Jan 2000 03:00:00 GMT  
 linked lists

Quote:

> Indeed.  Bubble sort comes first into mind -- as an algorithm that should
> be expunged from every textbook and replaced with an explanation as to why
> it is not a suitable choice under any circumstances.

Why is bubble sort never suitable? If you're programming in a language
that doesn't have a standard library sort routine (e.g., fortran), and
you know that sorting the list has negligible effect on overall
performance of your program, what's wrong with bubble sort?


Sat, 15 Jan 2000 03:00:00 GMT  
 linked lists



| > Indeed.  Bubble sort comes first into mind -- as an algorithm that
should
| > be expunged from every textbook and replaced with an explanation as to
why
| > it is not a suitable choice under any circumstances.

| Why is bubble sort never suitable? If you're programming in a language
| that doesn't have a standard library sort routine (e.g., Fortran), and
| you know that sorting the list has negligible effect on overall
| performance of your program, what's wrong with bubble sort?

Because you stand the risk that one sad day some moron attempts to
use your software for processing, say, 100,000 elements instead of
the usual 42 your designed it for ...

kind regards,




Sat, 15 Jan 2000 03:00:00 GMT  
 linked lists


|> Because you stand the risk that one sad day some moron attempts to
|> use your software for processing, say, 100,000 elements instead of
|> the usual 42 your designed it for ...

*sigh*

Yeah... writing robust software would be SO MUCH eaiser of not for those
damned users....
--
*    "We all agree on the necessity of compromise.  We just can't agree on
*     when it's necessary to compromise."



Sat, 15 Jan 2000 03:00:00 GMT  
 
 [ 25 post ]  Go to page: [1] [2]

 Relevant Pages 

1. link list of a linked list (chained links?)

2. Incompatible NULL Assignments || Linked List inside Linked List

3. Clearing Memory || Linked List INSIDE of a Linked List

4. Freeing a Linked List inside of a Linked List

5. Linked List of Linked Lists

6. Define a linked list of a linked list

7. Link List to Link List, HELP friends

8. linked lists (searching/moving a link)

9. I/O and a linked list of linked lists! HELP

10. Link-list sort algorithm question

11. Need help with doubly linked lists

12. Disapearing linked lists

 

 
Powered by phpBB® Forum Software