How to treat previous/tail on doubly linked lists?

[An Integer]

I am having some troubles on logic for implementing both previous and tail on a doubly linked list with nodes. Could someone help me with this?

My node setup:

  struct node {
	node(node* w, int x, node* y) {
		left = w;
		data = x;
		right = y;
	}
	int data;
	node* right;
	node* left;
  };

The linkedlist:

class LinkedList {
public:
	void addFront(int x) {
		node* new_node = new node(previous, x, head);
		new_node->left = tail;
		new_node->right = new_node;
		head = new_node;
		size++;
	}
	void display_front() {
		std::cout << "Head is: " << head->data << std::endl;
	}
	void display_back() {
		std::cout << "Back is: " << tail->data << std::endl;
	}
private:
	node* tail;
	node* previous;
	node* head;
	int size;
};

I just don't quite see how I can implement the previous and tail function into this

[jonnin]

it works just like a singly linked list, except in reverse, which isnt helpful lol, but think about it.

.. if its the head of the list, previous is null, just like if its the end of the list, next is null.
.. if its in the middle, previous is the one before your current, so you have to have a way to get to that, often that means a bunch of next->next junk or a temporary holding onto it. You can do it either way, if you do the double next thing, its hard to read and adds an extra case (next.next exists checks to handle end of list before you get there, and the true end of list too, not too bad) and its a lot of pointer manipulation. If you save it in a temporary, its more straightforward but you must track that correctly.

so like add front, previous is null on your new node
new -> next is old head.
old head -> previous is the new node

does that make sense?

[An Integer]

I'm sorry, I just can't see it in recursion. Manually it's easier to get going

[icy1]

I think maybe confusion from the variable names.

Each "node" should have just a value and "prev", "next" pointers.
The manager of the nodes only needs "head" and "tail" pointers.

node constructor needs only the value. The manager will set each node's "prev" and "next" where needed, or they should be nullptr by default, which is fine.

[An Integer]

Thanks icy!

So I am guessing;

struct node {
	node(node* w, int x, node* y) : previous(w), data(x), next(y){}
	int data;
	node* previous;
	node* next;
};

void add_front(int x) {
		node* new_node = new node(tail, x, head);
		tail = ? ;
		head = new_node;
		size++;
	}

Kinda uncertain about how to set tail, so that it keeps to the first node created tho?

[jonnin]

tail does not usually change when you insert in front.

empty
insert 1 node, head = tail, ok. (if empty, set tail, is the logic)
insert 2nd node, tail = tail, unchanged, head changes.
insert 3rd node, tail = tail, unchanged, head changes.
...
if you insert at the tail, it will change (and head remains the same unless empty list).

[keskiverto]

void append( int x ) {
  node* new_node = new node( tail, x, nullptr );
  assert( tail == new_node->previous );
  if ( size < 1 ) {
    // list was empty and new_node becomes its first node
    // ...
  }
  else {
    // regular append
    tail->next = new_node;
  }
  tail = new_node;
  ++size;
  assert( head != nullptr );
  assert( tail != nullptr );
  assert( tail->next == nullptr );
}

[icy1]

An Integer, write a main() with some test code and you'll see that simpler is better. With your 3-param constructor instead of simpler 1-param constructor as I suggested, how are you creating the very first node?

head is the start of the list
tail is the end of it

An Integer wrote:

Kinda uncertain about how to set tail, so that it keeps to the first node created tho?

You have it kinda backwards. If you keep adding to the front, then it's the head that will be changing, not the tail. It's not about "creation time" -- it's about keeping track of the whole list if you were to spread it out in one line, front to back. You could have methods to delete nodes, too (preferably from front or back, since arbitrary "indices" are expensive)

head->foo->bar->baz->qux->quux->corge->uier->grault->garply->waldo->fred->tail
... add to front; new node becomes head ...
head->oldhead->foo->bar->baz->qux->quux->corge->uier->grault->garply->waldo->fred->tail

[An Integer]

@keskiverto & @jonnin thanks!!

For @icy1: you're right. I got that backwards, even though I didn't meant to do formulate it that way. It was just a bit late. What I meant is that I had a problem with being able to create a node with both a tail and head through the 3 parameter constructor. Which you are pointing out, and that makes sense now.

I'll try to do it with the good suggestions here from all of you. Thank you very much. I might come back and comment though.