# Doubly-linked lists using references rather than pointers (C++)

This topic is 3565 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Just a thought; how would I implement a doubly-linked list where each node stores its previous and next nodes by reference? Since the references must be set in the node constructor, there is a two-way dependency between one node and the next, so the list's creator would need to construct all nodes simultaneously! I guess I'm barking up the wrong tree and that you nice people will tell me to use pointers or smart pointers instead, but I shall ask anyway, just in case everything I know is wrong :)

##### Share on other sites
Considering references can't be reassigned, this doesn't seem like a great idea.

##### Share on other sites
You couldn't implement a terminal value either - because a reference has to be valid.

##### Share on other sites
Here you go..

template <class T>struct Reference {  T &value;  Reference(T &v) : value(v) {}};template <class T>struct LinkedListNode {  Reference<T> *left;  Reference<T> *right;  LinkedListNode() : left(NULL), right(NULL) {}  void setLeft(T &v) {    delete left;    left = new Reference<T>(v);  }  void setRight(T &v) {    delete right;    right = new Reference<T>(v);  } };

Yes, this is a silly post.

##### Share on other sites
Quote:
 Original post by rip-offYou couldn't implement a terminal value either - because a reference has to be valid.
Use a polymorphic node type [smile]

##### Share on other sites
Quote:
Original post by ToohrVyk
Quote:
 Original post by rip-offYou couldn't implement a terminal value either - because a reference has to be valid.
Use a polymorphic node type [smile]

Or a singleton....

struct Node {	explicit Node(const Node & n) : next_(n) {}	static const Node & null_node() {		static Node instance;		return instance;	}	bool has_next()     const { return !(next_ == null_node().next_); }	const Node & next() const { return next_; }private:	friend bool operator==(const Node & lhs, const Node & rhs);	Node() : next_(null_node()) {}	const Node & next_;};bool operator==(const Node & lhs, const Node & rhs) {	return (&lhs.next_ == &rhs.next_);}int count(const Node & n) {	return n.has_next() ? (count(n.next()) + 1) : 1;}int main(int argv, char **){		Node a(Node::null_node());	Node b(a);	Node c(b);	Node d(c);	std::cout << count(d) << std::endl;}

##### Share on other sites
Quote:
 Original post by hymermanhow would I implement a doubly-linked list where each node stores its previous and next nodes by reference?

Storing things by reference is very seldomly a good idea. You aren't meant to hold on to references. Use pointers.

References were introduced into the language to support operator overloading for user-defined types better, so you could write expressions like b + c instead of *b + *c.

##### Share on other sites
Arg... that looks dangerously close to undefined behaviour Antheus. It seems like you are using a reference before it is initialised, because we are still in the process of initialising it.

I am probably wrong though.
struct Node {	explicit Node(const Node & n) : next_(n) {}	static const Node & null_node() {		static Node instance;		if(!finished)		{			std::cout << "returning a reference to an uninitialised value\n";		}		return instance; 	}	bool has_next()     const { return !(next_ == null_node().next_); }	const Node & next() const { return next_; }private:	friend bool operator==(const Node & lhs, const Node & rhs);	Node() : next_(null_node())	{		finished = true;	}	const Node & next_;	static bool finished;};bool Node::finished = false;bool operator==(const Node & lhs, const Node & rhs) {	return (&lhs.next_ == &rhs.next_);}int count(const Node & n) {	return n.has_next() ? (count(n.next()) + 1) : 1;}int main(int argv, char **){		Node a(Node::null_node());	Node b(a);	Node c(b);	Node d(c);	std::cout << count(d) << std::endl;}

But I will concede that it is a beautiful method, undefined behaviour or not!

##### Share on other sites
Fair enough, I figured that was probably the case! I'll stick to pointers in this case.

Quote:
 Original post by DevFredStoring things by reference is very seldomly a good idea. You aren't meant to hold on to references. Use pointers.

Why is that, exactly? Holding on to either is dangerous in exactly the same way (can point to invalid object), what makes references worse? I prefer references since they can't be NULL and are guaranteed to be initialised.

##### Share on other sites
I would guess it depends. If the code guarantees that the reference stays valid for the lifetime of the object it might be OK (e.g a member of a class has a reference to the instance that contains it).

Be warned, though, that through programmer errors it is perfectly possible to obtain invalid and uninitialized references.

int& a = a;

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
JoeJ
14

• 14
• 10
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632631
• Total Posts
3007534
• ### Who's Online (See full list)

There are no registered users currently online

×