Linked Lists/Java/Rotate - Revision history

Admin at 22:53, 9 March 2019

2019-03-09T22:53:10Z

← Older revision		Revision as of 22:53, 9 March 2019
Line 37:		Line 37:
	* One pointer is the temporary pointer to the rest of the list that is still being processed		* 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		Link to full implementation of TLinkedList class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

	==Profiling==		==Profiling==
Line 43:		Line 43:
	Here are the total walltime costs and per operation costs for the remove operation defined in the TLinkedList class above.		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		Code to make these figures is here: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/Timing.java

	[[Image:rotate_amortized.png\|500px]]		[[Image:rotate_amortized.png\|500px]]

Admin: /* Question */

2019-03-09T22:52:49Z

Question

← Older revision		Revision as of 22:52, 9 March 2019
Line 6:		Line 6:
	To rotate a linked list without destroying the node, we will temporarily make the link circular.		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		The rotate method is in the TLinkedList class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

	<pre>		<pre>

Admin at 07:11, 6 June 2017

2017-06-06T07:11:00Z

@@ Line 7: / Line 7: @@
 The rotate method is in the TLinkedList class: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java
 <pre>
-	/** Reverse the entire linked list in O(n) time. */
+	/** Rotate list by moving one element from front to back.
-	public void reverse() {
-		if(this.size==0 || this.size==1) {
+	 * This is implemented without creating/destroying a node.
 			return;
+		}
-		Node<E> runner = this.head;
+		// Make circular
-		Node<E> prev = null;
+		tail.setNext(this.head);
-		Node<E> next_runner = this.head.getNext();
+		tail = tail.getNext();
+	}
 </pre>
 To reverse a linked list, need to hang on to three separate pointers:
@@ Line 34: / Line 36: @@
 * 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
@@ Line 97: / Line 45: @@
 Code to make these figures is here: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/Timing.java
-[[Image:rev_amortized.png|500px]]
+[[Image:rotate_amortized.png|500px]]
-[[Image:rev_walltime.png|500px]]
+[[Image:rotate_walltime.png|500px]]
 ==Flags==
@@ Line 107: / Line 55: @@
 [[Category:Linked Lists]]
 [[Category:Skiena]]

Admin: Created page with " ==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 ro..."

2017-06-06T06:59:29Z

Created page with " ==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 ro..."

New page

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

<pre>
/** 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;
}
</pre>

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

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

if length is 0, do nothing

if length is 1, do nothing

<pre>
runner = head
prev = null
next runner = head.getNext()

while(nextrunner != null)
runner.setNext(prev)
prev = runner
runner = nextrunner
nextrunner = runner.getNext()
list.head = runner
</pre>

==Code==

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

<pre>
/** 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;
}
</pre>

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

[[Image:rev_amortized.png|500px]]

[[Image:rev_walltime.png|500px]]

==Flags==

{{DataStructuresFlag}}
[[Category:Java]]
[[Category:Linked Lists]]
[[Category:Skiena]]