Linked Lists/Java/Rotate

Question

Write a method that will rotate a Linked list, with similar result as the command addLast(removeFirst()), but that would not create and destroy any node.

To rotate a linked list without destroying the node, we will temporarily make the link circular.

The rotate method is in the TLinkedList class: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java

	/** Rotate list by moving one element from front to back.
	 *
	 * This is implemented without creating/destroying a node.
	 */
	public void rotate() { 
		if(this.size==0 || this.size==1) { 
			return;
		}
		// Make circular
		tail.setNext(this.head);
		tail = tail.getNext();
		
		// Circular
		head = tail.getNext();

		// Break circle
		tail.setNext(null);

	}

To do this, need to connect head to tail, advance tail by one,

To reverse a linked list, need to hang on to three separate pointers:

• One pointer is the runner, which points to the current node being "fixed" (reversed in place).
• One pointer is the prior, which points to the node that will be behind the runner in the list
• One pointer is the temporary pointer to the rest of the list that is still being processed

Link to full implementation of TLinkedList class: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java

Profiling

Here are the total walltime costs and per operation costs for the remove operation defined in the TLinkedList class above.

Code to make these figures is here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/Timing.java