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

	/** Reverse the entire linked list in O(n) time. */
	public void reverse() { 
		if(this.size==0 || this.size==1) {
			return;
		}
		Node<E> runner = this.head;
		Node<E> prev = null;
		Node<E> next_runner = this.head.getNext();

		while(next_runner!=null){
			runner.setNext(prev);
			prev = runner;
			runner = next_runner;
			next_runner = next_runner.getNext();
		}
		this.head = runner;
	}

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

if(size=0):
  return
if(size==1)
  return
if size=2) 
    runner = head
    prior = null
    temp = runner.getNext()
    runner.setNext(prior)

if length is 0, do nothing

if length is 1, do nothing

runner = head
prev = null
next runner = head.getNext()

while(nextrunner != null) 
    runner.setNext(prev)
    prev = runner
    runner = nextrunner
    nextrunner = runner.getNext()
list.head = runner

Code

This was implemented in the TLinkedList<T> class, the templated generic linked list type:

	/** Reverse the entire linked list in O(n) time. */
	public void reverse() {
		if(this.size==0 || this.size==1) {
			return;
		}
		Node<E> runner = this.head;
		Node<E> prev = null;
		Node<E> next_runner = this.head.getNext();

		while(next_runner!=null){
			runner.setNext(prev);
			prev = runner;
			runner = next_runner;
			next_runner = next_runner.getNext();
		}
		this.head = runner;
	}

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