I have done what I can in regards to plotting a diagram to see the relation and relativity of the respective nodes. This is for an Algorithms and Data Structures course. Thanks!

Norm Radder wrote:What are the links that control the list? What's in the head and tail objects?

So when there are no nodes in the Implemented Linked List, the head.next points to tail and tail.prev points to head. The way I currently have it implemented in the add method since it needs to add the node at the end is that I have to make sure that it is the last node. In order to do so, the newNode or the lastNode has to point to tail and tail.prev has to point to the last node. The problem is figuring out how head.next points to the next node in the sequence. Obviously, it can not point to the newNode because if one adds another node (or nodes) to the data structure, head.next will have to point to the previous node (first node) that came before the newNode.

I'm having a hard time thinking this through (the implementation of this). It's common sense I guess for a Computer scientist to link the newNode.next to tail and tail.prev to newNode, but after that, I personally run into a conundrum because I'm a n00b CompSci major lol (well I'm not that bad, but I have my moments of n00b behavior). I think you understand what I mean. Thanks!

when there are no nodes in the Implemented Linked List, the head.next points to tail and tail.prev points to head.

what about head.prev and tail.next?

Where do the links for head and for tail point when there are nodes in the list?

Note: I always use paper and pencil (not pen) to draw out linked lists to see where the links go. Then when changing the links, I erase the current links and draw the new ones, taking notes of the correct order to do it to preserve the linking.

The algorithm should NOT need to reference the head node directly at all.

Your algorithm as is will work for an empty list.

It won't work as soon as you have something in it...

You do need to set four links.

Tail.previous, newNode.next, newNode.previous and...

Norm Radder wrote:

when there are no nodes in the Implemented Linked List, the head.next points to tail and tail.prev points to head.

what about head.prev and tail.next?

Where do the links for head and for tail point when there are nodes in the list?

Note: I always use paper and pencil (not pen) to draw out linked lists to see where the links go. Then when changing the links, I erase the current links and draw the new ones, taking notes of the correct order to do it to preserve the linking.

head.prev and tail.next are null pointers they don't point anywhere as they act as sentinel nodes of the Doubly Linked List Data Structure. The nodes between the sentinel/dummy nodes are actually the nodes that store information and can point to other nodes in the Data structure (both previous and next).

Norm Radder wrote:Where do the links for head and for tail point when there are nodes in the list?

When are the links in the head and tail nodes updated?

Well tail.prev is always pointing to the newestNode as the node is supposed to be at the end of the list when using the add method. The newestNode also points to the tail node and the node that precedes it. I'm having a hard time thinking about where the head node (head.next) points. It will be the first node in the list, but I don't know how to implement the Data Structure to make head point to the first node.

If you are adding an item at the tail of the list, you shouldn't need to modify the head node.

The ONLY case where you actually do is where you have an empty list (and even then you never need to actually refer to it as "head").

Every other case, you shouldn't be touching it.

More hints. Consider adding E1 E2 and E3 to an empty list - you would end up with the following progression:

HEAD - TAIL

HEAD - E1 - TAIL

HEAD - E1 - E2 - TAIL

HEAD - E1 - E2 - E3 - TAIL

For that last step adding E3 to the end of the list effectively what you have to do is:

E3.next = TAIL

E3.prev = E2 (tail.prev)

tail.prev = E3 (the new element)

E2.next = E3

But how would you get the reference to E2 to set its next link?

Naziru Gelajo wrote:Well tail.prev is always pointing to the newestNode as the node is supposed to be at the end of the list when using the add method.

Really? Are you saying that you can ONLY add nodes at the end, because that kind of defeats the goal of a linked

`List`, and actually sounds more like a stack or queue. It also suggests that double-linking may be redundant.

An alternative that may be worth considering is a

`LinkedRing`, where the head and tail Nodes are the same. This has few downsides and one major upside: you

*don't*have to change logic when the ring is "empty".

BTW, such a Node is often called an "anchor".

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Winston Gutkowski wrote:

Naziru Gelajo wrote:Well tail.prev is always pointing to the newestNode as the node is supposed to be at the end of the list when using the add method.

Really? Are you saying that you can ONLY add nodes at the end, because that kind of defeats the goal of a linkedList, and actually sounds more like a stack or queue. It also suggests that double-linking may be redundant.

An alternative that may be worth considering is aLinkedRing, where the head and tail Nodes are the same. This has few downsides and one major upside: youdon'thave to change logic when the ring is "empty".

BTW, such a Node is often called an "anchor".

Winston

This particular method requests for that my friend

Stefan Evans wrote:I said it before. I'll say it again.

If you are adding an item at the tail of the list, you shouldn't need to modify the head node.

The ONLY case where you actually do is where you have an empty list (and even then you never need to actually refer to it as "head").

Every other case, you shouldn't be touching it.

More hints. Consider adding E1 E2 and E3 to an empty list - you would end up with the following progression:

HEAD - TAIL

HEAD - E1 - TAIL

HEAD - E1 - E2 - TAIL

HEAD - E1 - E2 - E3 - TAIL

For that last step adding E3 to the end of the list effectively what you have to do is:

E3.next = TAIL

E3.prev = E2 (tail.prev)

tail.prev = E3 (the new element)

E2.next = E3

But how would you get the reference to E2 to set its next link?

I'll try that thanks

Stefan Evans wrote:I said it before. I'll say it again.

If you are adding an item at the tail of the list, you shouldn't need to modify the head node.

The ONLY case where you actually do is where you have an empty list (and even then you never need to actually refer to it as "head").

Every other case, you shouldn't be touching it.

More hints. Consider adding E1 E2 and E3 to an empty list - you would end up with the following progression:

HEAD - TAIL

HEAD - E1 - TAIL

HEAD - E1 - E2 - TAIL

HEAD - E1 - E2 - E3 - TAIL

For that last step adding E3 to the end of the list effectively what you have to do is:

E3.next = TAIL

E3.prev = E2 (tail.prev)

tail.prev = E3 (the new element)

E2.next = E3

But how would you get the reference to E2 to set its next link?

This doesn't work because the way I have head.next setup in the constructor is that by default in an empty Linked List, head.next points to the tail and tail.prev points to head. That's why somehow, I need the add method to have head to point to something (or alternatively, I can redo the constructor.