Is a Linked-List Implementation Without Using Pointers Possible or Not

How are linked lists implemented without the use of pointer?

They are implemented using references which are essentially (excluding syntax) pointers that you can't do pointer arithmetic with (in some languages they also can't be null). In many languages, references are the default way of using variables, unlike C++ where the default is by-value.

How to implement linked list in reference without using pointer

I don't know how useful the concept is, but you CAN do it using std::reference_wrapper, as follows:

#include <iostream>
#include <list>
#include <functional>
using namespace std;

int main() {
    int a = 2, b = 6, c = 1;

    list<reference_wrapper<int>> mylist;
    mylist.push_back(a);
    mylist.push_back(b);
    mylist.push_back(c);

    for(auto x : mylist) {
        cout << x << " ";
    }
    cout << endl;
    a = 3; // <- this setting will modify mylist!

    for(auto x : mylist) {
        cout << x << " ";
    }
    return 0;
}

I would recommend learning C++ ways of handling things, specially that you are coming from Java world. Demo!

Creating a linked list without pointers but indices

Your struct Node would be like this

struct Node {
    int data;
    int index; // index of the entry in the pool to the next node
}

You can use a vector or array to create a pool

vector<Node*> pool; // stores the pointer to next nodes

Now to access the next node you can do

Node* nextNode = pool[currNode->index];

How can a Linked List be implemented using only pointers (w/o structures)?

Here is a complete solution of a LinkedList managed as int ** pointers.

Step 1 - the addNode() function to add one node to the int **head.

int **addNode(int **head, int ival)
{
    int **node = malloc(2 * sizeof(int *));

    // don't forget to alloc memory to store the int value
    node[0] = malloc(sizeof(int));
    *(node[0]) = ival;
    // next is pointing to NULL
    node[1] = NULL;

    if (head == NULL) {
        // first node to be added
        head = node;
    }
    else {
        int **temp;

        temp = head;
        // temp[1] is the next
        while (temp[1]!=NULL) {
            // cast needed to go to the next node
            temp = (int **)temp[1];
        }
        // cast needed to store the next node
        temp[1] = (int *)node;
    }
    return (head);
}

Step 2 - a function display() to explore the current linkedlist.

void display(int **head)
{
    int **temp;
    int i = 0;

    temp = head;
    printf("display:\n");
    while (temp!=NULL) {
        // temp[0] is pointing to the ivalue
        printf("node[%d]=%d\n",i++,*(temp[0]));
        temp = (int **)temp[1];
    }
    printf("\n");
}

Step 3 - the popNode() function to remove the first node.

int **popNode(int **head)
{
    int **temp;

    if (head!=NULL) {
        temp = (int **)head[1];
        // don't forget to free ivalue
        free(head[0]);
        // then free the next pointer
        free(head[1]);
        head = temp;
    }
    return (head);
}

Step 4 - then an example of main() function using the linkedlist.

int main()
{
    int **head = NULL;

    head = addNode(head,111);
    head = addNode(head,222);
    head = addNode(head,333);

    display(head);
    // display:
    // node[0]=111
    // node[1]=222
    // node[2]=333

    head = popNode(head);

    display(head);
    // display:
    // node[0]=222
    // node[1]=333

    while ((head = popNode(head))!=NULL);

    display(head);
    // display:

    return (0);
}

Linked list without struct, but using only arrays

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.

---

Related Topics