Linked Lists/Java/Reverse

Question

Skiena Chapter 3: Data Structures

Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.

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://git.charlesreid1.com/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://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/Timing.java

X Axis: N (number of elements in linked list)

Y Axis: Amortized wall time, microseconds (total walltime / N)

X Axis: N (number of elements in linked list)

Y Axis: Total walltime, ms