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.

Hint: an array index is very similar to a pointer.

Henry
– Henry

2020-10-16 12:25:47 +00:00
Commented Oct 16, 2020 at 12:25 — Henry
– Henry, Commented Oct 16, 2020 at 12:25
@Henry Thanks for the Hint, but I am still confused

Alwin John
– Alwin John

2020-10-16 12:35:27 +00:00
Commented Oct 16, 2020 at 12:35 — Alwin John
– Alwin John, Commented Oct 16, 2020 at 12:35

soothsooth · Accepted Answer · 2020-10-18 11:02:26Z

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.

Willy K. · Accepted Answer · 2020-10-19 07:32:35Z

0

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;
}

edited Oct 19, 2020 at 7:32

answered Oct 16, 2020 at 14:19

Willy K.

4525 silver badges16 bronze badges

3 Comments

Alwin John Over a year ago

Thank you for the response, but I want to know whether it is possible using only arrays, and not using structure at all.

Willy K. Over a year ago

See second example. As far as data type is known (here: int), you simply can create a pointer to the first element and iterate through the data using the "++" operator.

Joan Venge Over a year ago

@WillyK. Hi I am trying to reach you for your answer on stackoverflow.com/questions/60854878/… Can you please help? I am just trying to figure out how your solution worked? You mentioned small window 0x0, but where did you add this as a child? I am trying to do the same for my app but don't understand your solution.

Collectives™ on Stack Overflow

Linked list without struct, but using only arrays

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related