Linked list without struct

Question

Can anyone help me with a singly linked list? I know how to do it with struct, but now i wanna know how to do it with only arrays and pointers without struct or nodes.Algorithms please thank you.

#include <iostream>
using namespace std;

const int size=5; 
int data[size];
int *mem;
int add[size];
int top = -1;

void AddLast(int value)
{ 
if(top==-1)
{
  top=data[value];               
 }
 else
 {
 top++;
 top=data[value];      
 }
} 


void print()
{   cout << "Queue: ";
for(int i = 0; i != top; i = (i + 1) % size)
{
    cout << data[i] << "->";
}
cout << endl;

}


int main()
{

 AddLast(2);
print();
AddLast(3);
print();
AddLast(4);
print();
cin.get();
    return 0;
    }

I want to addlast, addfirst, and add sorted... is this the way?

Answer 1

You can't do it with only one array, you need at least two: One for the data and one for the links. If you don't want to use structures at all (though I don't really see the reason for it) you could have multiple data arrays.

The data array contains the actual data, it's nothing special with it. The link array contains indexes to the data array, where each index is a "next" pointer.

For example, lets say you want to have a linked list of integers, and you have three integers in the list (their values are irrelevant), lets call that data array d, then you have d[0], d[1] and d[2]. The first node in the list is d[1], followed by d[0] and last d[2]. Then you need a head variable, which tells which index is the head of the list, this head variable is initialized to 1 (and "points" to d[1]). Then we have the link array, lets call it l, since the head is "pointing" to 1 we fetch l[1] to get the next node, the contents of l[1] is 0 which tells us the next node is d[0]. To get the next node we check l[0] which gives us 2 for d[2]. The next link, l[2] could be -1 to mark the end of the list.

Of course, the data array(s) and the link array needs to be of the same size.

Answer 2

An array s of structs with members A, B, C, can be emulated by three arrays a, b and c, where e.g. a[i] represents s[i].A, and so forth. So that's your requirement of no structs. Then doing a linked list with arrays, i.e. with indices instead of pointers, is mere notation; the concepts are exactly the same. But you might look up the technique of using a free list, a list of available logical nodes; this allows you to free nodes as well as allocate them, in a simple way.

Answer 3

This is a hack of sorts might help with your curiosity.

It is similar in implementation to how linked lists are typically implemented with struct.

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

int * base = NULL;
int ** current = NULL;

void add(int num)
{
    if(base==NULL) 
    {
        base = (int*)malloc(sizeof(int)*3);
        base[0] = num;
        current = (int**)(base+1);
        current[0] = NULL;
    }
    else
    {
        current[0] = (int*)malloc( sizeof(int)*3 );
        current[0][0] = num;
        current = (int**)(*current+1);
        current[0] = NULL;
    }
}

void show()
{
    if(base != NULL)
    {
        int * data = base;
        int ** tmp = (int**)(base+1);
        if(tmp[0]==NULL) 
            printf("%d\n",data[0]);
        else
        {
            do
            {
                printf("%d ",data[0]);
                data = tmp[0];
                tmp = (int**)(data+1);      
            }while(tmp[0]!=NULL);
            printf("%d\n",data[0]);
        }
    }   
}

int main()
{
    int choice,num;

    do
    {
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:scanf("%d",&num);
                   add(num);
                   break;
            case 2:show();
        }
    }while(1);
    return 0;
}

It is possible to add other function like addFirst() or addSorted() but will require some more pointer manipulation, for which I don't possess the dedication right now.

Answer 4

There is a (ugly) way to do a linked list with arrays.

Here is an example of how you might do something with arrays but I would never recommend even thinking about doing it.

template<class T>
typedef char[sizeof(T) + sizeof(uintptr_t)] listNode;

template<class T>
listNode<T>* getNext(const listNode<T>& x){
    return (listNode<T>*)(((char*)x)[sizeof(T)]); //notice how you have to increment the pointer address
}

template<class T>
T& getValue(listNode<T>& x){
        return (T) x;
}

That's way too many casts. It's less ugly if you make an array of two pointers and just cast the first value in a pointer on what you care about but that's still not what I would recommend.