How to Recursively Traverse in a Linked List
The Linked List data structure is a powerful alternative to simple arrays. Unlike arrays, data can be quickly added to and removed from a linked list without recreating the list one element at a time. However, unlike arrays, data in a linked list can only be accessed in order. You can do this with a simple loop or with a recursive (or self-calling) function. This will be written in Java, but the code can be implemented in any language with only minor modifications to suit the syntax differences.
Other People Are Reading
Instructions
-
-
1
Open a text editor.
-
2
Paste the following Java code:
public class RecursiveLLTraverser {
public static void traverseList(LinkedList l) {
}
}
All the code will go within the "traverseList" method.
-
-
3
Paste the following inside the "traverseList" method:
if (l.size() == 0) return;
if (l.size() > 0) {
LinkedList n = l.clone();
Object o = n.removeFirst();
o.doSomething();
traverseList(n);
}
This takes a Linked List and makes a shallow clone of it with the first element removed (and some processing performed upon it.) That clone is then run through the traverse List itself. Eventually, the clone will be empty, in which case the traverse List method will simply return.
-
1
Tips & Warnings
All recursive algorithms require at least two cases: a base case, which must return, and a recursive case, which reduces the data size to something more easily managed. One common bug in recursive methods is forgetting the base case. This causes an infinite loop that eventually crashes when the computer runs out of stack space.
Recursive methods depend a system setting called "stack size" which changes with the operating system and language. This section of memory keeps track of all currently running methods. Attempting a recursive algorithm on an extremely large list can produce stack errors.
