Confused about doubly linked lists

[benbalach]

I am reading "Programming Principles and Practice Using C++" by Bjarne Stroustrup. I am currently on chapter 17.9.3 (just informing those of you who by any chance have read the book). I understand how to use pointers. I know how allocation and deallocation of memory works. But I don't understand the following class. Please explain it to me in the simplest possible way, because if I don't understand it I won't be able to continue reading the book.

The following class is a double-linked list (given a link you can find both the predecessor and the successor).

#include "std_lib_facilities.h" // comes with the book

struct Link
{
public:
	string value;
	Link* prev; // I don't understand how this works
	Link* succ; // I don't understand how this works
	Link(const string& v, Link* p = 0, Link* s = 0)
			   // default arguments, I know how they work
	: value(v), prev(p), succ(s) { }
};

Link* insert(Link* old_obj_p, Link* new_obj_p) // I don't understand how this works
{
	if(old_obj_p == 0) return new_obj_p;
	if(new_obj_p == 0) return old_obj_p;
	new_obj_p->succ = old_obj_p;
	if(old_obj_p->prev) old_obj_p->prev->succ = new_obj_p;
	new_obj_p->prev = old_obj_p->prev;
	old_obj_p->prev = new_obj_p;
	return new_obj_p;
}

int main()
{
	Link* norse_gods = new Link("Thor", 0, 0);
	norse_gods = insert(norse_gods, new Link("Odin"));
	norse_gods = insert(norse_gods, new Link("Freia"));
	cout << norse_gods->succ->succ->value <<"\n";
	cout << norse_gods->succ->value <<"\n";
	cout << norse_gods->value <<"\n";
	keep_window_open();
	return 0;
}

[MikeyBoy]

It's called a doubly linked list. Each element in the list is a single instance of Link. Each element contains a pointer to the next element in the list - which is another instance of Link, hence it's stored as a Link* - Link* succ;. Each element also contains a pointer to the previous element in the list, also stored as a Link* - Link* prev;.

The insert function is inserting a new Link object, which new_obj_p points to, into the list. Specifically, it's inserting it at the position in the list previously occupied by the element that old_obj_p points to. In other words, it's inserted into the list immediately before the one that old_obj_p points to.

So, as you can see, it sets the pointers in the new object such that the previous object is the one that old_obj_p has recorded as its previous object, and the next object in the list is now set to be old_obj_p itself.

Similarly, the old object has its pointers set so that the one before it is now new_obj_p. The one after it is unchanged.

[kooth]

I like to think of doubly-linked lists like these simple pictures:

When the constructor is called on line 27, the object's two pointers looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

norse_gods:

value = "Thor" | NULL <---prev | succ---> NULL | ------------------------| On line 28, when the insert function is called: Line 16 is false Line 17 is false On line 18, new_obj_p->succ is assigned the address of old_obj_p, so now it looks like this: new_obj_p: -----------------------------| value = "Odin" | NULL <---prev | succ ---> old_obj_p | -----------------------------| Line 19 is false On line 20, new_obj_p->prev is assigned the address of old_obj_p->prev, so now it looks like this: new_obj_p: -----------------------------------------| value = "Odin" | old_obj_j->prev <--- prev | succ ---> old_obj_p | -----------------------------------------| On line 21 old_obj_p->prev is assigned the address of new_obj_p, so now it looks like this: old_obj_p: -----------------------------------------| value = "Thor" | new_obj_j->prev <--- prev | succ ---> old_obj_p | -----------------------------------------| Does this help?

[benbalach]

@MikeyBoy
@kooth

Thanks you very much! Now I understand everything!