Implementing an add method that adds an item at the end of a linked list

[Naziru Gelajo]

Greetings all, I'm attempting to create a method that adds a node of a generic object type to a Doubly Linked List. I have run into a minor connundrum. The issue mainly stems from the fact that when adding an item to the end of a Linked List, I don't know where to connect the head sentinel node. Currently, I understand how the tail sentinel node relates to the new added node. But I'm a bit stuck with my code currently. This is what I have typed up so far.

/**
	 * Appends an element to the end of the list
	 * @param element The element to add
	 */
	public boolean add(E element) 
	{
		// TODO: Implement this method
		LLNode<E> newNode = new LLNode<E> (element);
		if (element == null) {
			throw new NullPointerException("Element can not store a null reference!");
			
		} else {
			newNode.next = tail;
			newNode.prev = tail.prev;
			tail.prev = newNode;
			head.next = newNode;
			
		}
		size++;
		return true;
	}

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]

What are the links that control the list?  What's in the head and tail objects?

[Naziru Gelajo]

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!

[Norm Radder]

 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.

[Stefan Evans]

You are adding something to the tail of the list.
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...

[Naziru Gelajo]

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]

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?

[Naziru Gelajo]

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.

[Stefan Evans]

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?

[Winston Gutkowski]

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

[Naziru Gelajo]

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 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

This particular method requests for that my friend

[Naziru Gelajo]

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

[Naziru Gelajo]

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.

[Naziru Gelajo]

I forgot to mention earlier that my constructor looks like the following:

/** Create a new empty LinkedList */
	public MyLinkedList() {
		// TODO: Implement this method
		size = 0;
		/*create two empty nodes at the head and the tail of the linked list*/
		head = new LLNode<E> (null);
		tail = new LLNode<E> (null);
		head.next = tail;
		tail.prev = head;
		head.prev = null;
		tail.next = null;
	}

This possibly could be affecting the functionality of my add method.