Can we implement a doubly-linked list using a single pointer?

Question

I want to use a structure like: struct node { char[10] tag; struct node *next; }; I want to use the above structure to create a doubly-linked list. Is that possible and if yes, then how I can achieve it?

Answer 1

In general: of course not, you need two pointers to point to two things.

But, if you must you can probably make this work by using the unused bits in a pointer to store the other needed pointer. Of course there are no guarantees that a a pointer will have unused bits. But on Linux x86_64 and ARM64 we do know that the upper 16 bits are always set to zero in userspace. If the pointers are aligned to something we could also use some bits from the lower bits, for example 12 bits if 4k aligned.

A scheme could be: get the difference of the previous relative to the next (next - prev), assert that this fits in the available bits, and then OR them in to the unused bits (possibly split between high and low unused bits). Note that this difference is signed, so upon extraction it must be determined if it needs to be added or subtracted..

Anyways, its a hack but that is all that is possible.

Answer 2

Not sure if you wanted to do this in C++ or in C.

Here's the C++ answer, let me know if you need the answer in C.

Ok, here's the scoop. Linked lists are made up of two separate structures, one for the nodes, and one for the list itself. The node is usually implemented as a struct, and the list is implemented as a class in C++.

For a singly linked list, it would look something like this:

#include <iostream>

struct snode {

snode() // default constructor

: snode("") { } // next will automatically be set

// because you are passing in a C string, you must make a copy of it using strdup(const char*)

// otherwise, you could have multiple nodes sharing a single string, which could be deleted anytime

snode(const char* tag, snode* next=nullptr)

: tag_(strdup(tag)), next_(next) { }

friend std::ostream& operator<<(std::ostream& os, const snode& sno); // to be implemented

char tag_[10];

struct snode* next_;

};

class slist{

public:

slist()

: head_(nullptr), size_(0) { }

push_front(const char* s); // to be implemented

bool empty() const { return size_ == 0; }

bool size() const { return size_; }

// other functions not shown yet...

friend std::ostream& operator<<(std::ostream& os, const slist& sli); // to be implemented

private:

snode* head;

size_t size;

};

//----------------------------------------------------------------------------------------------------------

//-----------------------------------------------------------------------------------------------------------

//-----------------------------------------------------------------------------------------------------------

For a doubly linked list, as mentioned above, you would need two pointers in the node struct, like so

struct dnode {

dnode() // default constructor

: dnode("") {} // prev and next pointers will automatically be set to nullptr

dnode(const char* tag, dnode* prev=nullptr, dnode*next=nullptr)

: tag_(strdup(tag)), prev_(prev), next_(next) { }

friend std::ostream& operator<<(std::ostream& os, const dnode& dno); // to be implemented

char tag_[10];

struct dnode* prev_;

struct dnode* next_;

};

class dlist{

public:

dlist()

: head_(nullptr), tail_(nullptr), size_(0) { }

push_front(const char* s); // to be implemented

push_back(const char* s); // ditto

bool empty() const { return size_ == 0; }

bool size() const { return size_; }

// other functions not shown yet...

friend std::ostream& operator<<(std::ostream& os, const dlist& dli); // to be implemented

private:

dnode* head_;

dnode* tail_;

size_t size_;

};

Answer 3

You said DOUBLY linked... so there must be two pointers, one for the NEXT node and one to the PREVIOUS node.

To make a doubly circular list:

For the first node in the list, or the HEAD, the next pointer points to the second node while the "previous pointer points to the last node.

FOr the last node in the list, or the TAIL, the next pointer points to the first node while the "previous pointer points to the next-to-last

Some programmers use a MID pointer that points to the MIDDLE of the list

Answer 4

General Theory:

The definition of a double-linked list is

A list composed of nodes where in each node you have a link to the previous node in the list and another link to the next node in the list. So, it is easy to go backwards or forward on the list by following the links You have two links, hence the name double-linked.

Double-linked lists could be circular or linear.

1. In circular lists the two pointers always point to another node. If there is only one node, the two pointers point to itself. If ou have two nodes, both pointers point to the other node. If you have more than two nodes, then they point to the next node and the previous node in the circle.

1. In a linear double linked list, the first item in the list has the previous pointer pointing to NULL and the last node has the next pointer pointing to NULL.

Your case:

In the structure you propose:

struct node { char[10] tag; struct node *next; };

you only have one link going forward. You are missing a link to go backwards, so the answer to your question is:

No, you can not build a double linked list with that structure as you defined it.

With that structure you build a single linked list.

In order to build a double linked list you would need your structure to have two ponters like this:

struct node { char[10] tag; struct node *next; struct node *previous;};

with the additional pointer to the previous node.