From charlesreid1


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:

	/** 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) { 
		// Make circular
		tail = tail.getNext();
		// Circular
		head = tail.getNext();

		// Break circle


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:


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:

Rotate amortized.png

Rotate walltime.png