Linked list without struct, but using only arrays

Question

#include <stdio.h>
int main()
{
    int n, i;
    int head = 0;
    printf("No of Students:\n");
    scanf("%d", &n);
    int data[n];
    int address_of_data[n];
    int *next;
    printf("Enter Marks:\n");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &data[i]);
    }
    for (i = 0; i < n; i++)
    {
        if (data[head] != -1)
        {
            address_of_data[head] = &data[i];
        }
        else
        {
            break;
        }
        head++;
    }
    next = address_of_data[0];
    for (i = 0; i < n; i++)
    {
        printf("%d ", *(next + i));
    }
    return 0;
}

In the above code, I used pointers to print the data values. Using two arrays, one for the data and another for the address of the data. But I don't how to actually implement a linked List out of this, I am really confused, can anyone tell how to implement a Linked-List without using structures.

Answer 1

Here is a complete example of a simple linked list - for more ease in pure C. Note the "next" member in the structure - this is a pointer to the successor in the list.

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

struct MY_DATA {
    int number;
    char info[30];
    struct MY_DATA *next;
};

#define MAX_ELEMS   5

int main(int argc, char **argv)
{
    struct MY_DATA *root = NULL;        /* Root of list */
    struct MY_DATA *prev = NULL;        /* Previously created element */

    for(int i = 0; i < (MAX_ELEMS); i++)
    {
        /* Allocate memory ... */
        struct MY_DATA *new_data = (struct MY_DATA *)malloc(sizeof(MY_DATA));

        /* ...and inialize new data set */
        memset(new_data, 0x00, sizeof(MY_DATA));
        new_data->number = i * i;
        sprintf((char *)&(new_data->info), "This is data record %d", i);


        if (root == NULL)
        {
            root = prev = new_data;      /* Remember the first element */
        }
        else
        {
            prev->next = new_data;      /* The previous element has now a successor */
            prev = new_data;            /* Remember this for next iteration */
        }
    }

    struct MY_DATA *current = root;     /* Get the 1st element in the list */
    struct MY_DATA *temp = NULL;        /* Just for clean up stuff */

    for(int i = 0; i < (MAX_ELEMS); i++)
    {
        /* Display data */
        printf("Data set #%d: %s\n", current->number, current->info);

        temp = current;             /* This becomes deleted */
        current = current->next;    /* Set current pointer to successor of current element */
        free(temp);
    }

    return 0;
}

Another exampe - accessing an array with indexes or pointers:

#include <stdio.h>

#define MAX_ELEMS   5
int my_array[MAX_ELEMS] = { 5, 18, 42, 31, 10 };

int main(int argc, char **argv)
{
    int *current = (int *)my_array;     /* Get the 1st element in the list */

    for(int i = 0; i < (MAX_ELEMS); i++)
    {
        /* Using array index */
        printf("Data set #%d \n" \
               "  Indexed access: %d\n", i, my_array[i]);

        /* Using the pointer*/
        printf("  Pointer access: %d\n", *current++);
    }

    return 0;
}

Answer 2

The key advantage of a linked list is that when you insert or append an element, you can store that element anywhere in memory. Other elements in the list can point to it, and if you iterate over the list, you jump back and forth anywhere in memory following the pointers down the chain formed by the elements, until you reach the tail, which has a null pointer because it is the last element.

Implementing a linked list 'using only arrays' does not really make much sense. Even if you could, why would you want to? Arrays are great because you can index directly into them in constant time - you can't do this with linked lists, you can only iterate over them. But arrays have their drawbacks too - they are fixed size, and when they fill up, they fill up! Most shared library lists like the ArrayList in Java or the vector class in C++ store the underlying data in a fixed size array, and then if you insert too many items for that array, they create a new, larger array behind the scenes and copy the elements across for you. There really is no magic solution for when you run out of room in your array.

So with that being said, why would you implement a linked list using only arrays? You remove their only advantage - that you can append arbitrarily without costly reallocations. I'm not even sure if it's a well defined question. Perhaps if you're really desperate, you can create one large array and treat it like your own virtual memory, allocating and freeing slots in it, and then treat a two element array as an entry (entry[0] = data, entry[1] = 'address' of next, i.e. an index into your large array). But this smacks of terrible code and is really missing the point of linked lists.