linked list

[RexLee]

What does this code do?

#define NEXT(x)    x = next[x]#define REMOVE(x)    { next[PREVIOUS[x]] = next[x]           previous[next[x]] = previous[x];        }#define INITIAL(n)    {unsigned long i;          for (i = 2; i <= n; i++)               previous[i] = i - 1, next[i] = i + 1;          previous[2] = next[n] = NULL;        }

And how does one usually implement linked list in code. I have read on linked list before, but I have never put it to use in code yet.

[arkon]

Is there more code? It seems like some of it might be missing.

 

Linked lists are actually very similar. You basically have nodes, where each node holds its value, and a pointer to the next node.

[fizzlesticks]

All I know is if I saw someone write code like that I would shoot them.

[RexLee]

This is full code:

/* ------------------------------------------------------ *//* PROGRAM linear sieve program of Gries and Misra :      *//*    This program finds all prime numbers between 2 and  *//* n, the input, by using Gries and Misra linear sieve    *//* method.  This method does not use division, instead    *//* multiplications are used.                              *//*                                                        *//* Copyright Ching-Kuang Shene               July/10/1989 *//* ------------------------------------------------------ */#include  <stdio.h>#include  <stdlib.h>#define   MAXSIZE    1000#define   NEXT(x)    x = next[x]#define   REMOVE(x)  { next[previous[x]] = next[x];          \                       previous[next[x]] = previous[x];      \                     }#define   INITIAL(n) { unsigned long i;                      \                       for (i = 2; i <= n; i++)              \                            previous[i] = i-1, next[i] = i+1;\                       previous[2] = next[n] = NULL;         \                     }void main(void){     unsigned long  previous[MAXSIZE+1]; /* prev. pointer */     unsigned long  next[MAXSIZE+1];     /* next pointer  */     unsigned long  prime, fact, i, mult;     unsigned long  n;     unsigned long  count = 0;     char           line[100], dummy;     printf("\nLinear Sieve Program");     printf("\n====================");     printf("\n\nPrime Numbers between 2 to --> ");     gets(line);     n = strtoul(line, &dummy, 10);       INITIAL(n);              /* initial the set          */     for (prime = 2; prime*prime <= n; NEXT(prime))          for (fact = prime; prime*fact <= n; NEXT(fact))               for (mult = prime*fact; mult <= n; mult *= prime)                    REMOVE(mult); /* remove multiples     */     for (i = 2; i != NULL; NEXT(i)) { /* display result  */          if (count % 8 == 0)  printf("\n");          printf("%6ld", i);          count++;     }     printf("\n\nThere are %ld Prime Numbers in Total", count);}

[Ciccioo]

it's a method of handling a list of numbers

 

in this case you have to deal with a list of the natural numbers between 2 and n, so imagine you have this list (2, 3, 4, 5, ... , n-2, n-1, n), and note that this list is not actually stored anywhere

now, you want to store a list that tells you, for each value, which is the next one to come, and the previous

 

 

 

so, with

n = 5

 

our list would be

(2, 3, 4, 5)

 

the "next" list would be

(3, 4, 5, null)

the n-th element of the "next" list indicates the (n+1)-th element of the original list. the last element (5) has no item after it, so null

 

the "previous" list would be

(null, 2, 3, 4)

 

so, if you evaluate next[3] you get 4, if you evaluate previous[5] you get 4, as expected

 

this is useful because as you see, you can remove the n-th item by linking the (n-1)-th item to the (n+1)-th

// let's remove 4next[3] = 5;               // because 4 is deadprevious[5] = 3;

that is handful in this program because you start from all the naturals, and excluding all the multiples one by one you get the list of prime numbers

 

in general, lists are used when you need to add, remove or move items frequently, which would be a mess with a normal array since you would need to move ALL the other items

[RexLee]

Thanks I know what it does now.

Now I have a question on how to create an add node and delete node function in linked list.(using classes)

[Ciccioo]

using classes? a specific class already built, or a class that you want to build?

[RexLee]

A class I want to build.

[Ciccioo]

i'd suggest looking around for some explaination

googling a bit i found out this video (http://www.youtube.com/watch?v=o5wJkJJpKtM) i have no idea of who is is and how the video is, but it has good feedback and it draws, so i'll just say that i like it cause yes

anyway, whatever you do with lists, drawing the situation you're representing is always a very big help, everything is crystal clear once you see it with your eyes