# Linked Lists/Java/Reverse

### From charlesreid1

## Contents

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

## Flags

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |