Java Collection, LinkedList Exercises: Iterate through all elements in a linked list starting at the specified position
Last update on December 14 2021 10:52:35 [UTC/GMT +8 hours]Java Collection, LinkedList Exercises: Iterate a linked list in reverse order.
Last update on December 14 2021 10:52:36 [UTC/GMT +8 hours]1. Using ListIterator
The List interface provides a special iterator, called ListIterator, that allows bidirectional access. We can call the List.listIterator[index] method to get a ListIterator over the list elements starting from the specified position in the list. Since we need to start from the last element, the starting index would be equal to the list’s size.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | import java.util.Arrays; import java.util.List; import java.util.ListIterator; class Main { // Java program to iterate list in reverse order public static void main[String[] args] { List list = Arrays.asList["C", "C++", "Java"]; // use `ListIterator` to iterate list in reverse order ListIterator itr = list.listIterator[list.size[]]; // `hasPrevious[]` returns true if the list has a previous element while [itr.hasPrevious[]] { System.out.println[itr.previous[]]; } } } |
DownloadRun Code
Iterate List in Reverse Order in Java
The List interface provides a way to store the ordered collection. It is a child interface of Collection. It is an ordered collection of objects in which duplicate values can be stored. Since List preserves the insertion order, it allows positional access and insertion of elements.
Example
Input: ["geeks", "for", "Geeks"] Output: ["Geeks", "for", "geeks"] Input: [ 1, 2, 3, 4, 5] output: [5, 4, 3, 2, 1]We can iterate the list in reverse order in two ways:
- Using List.listIterator[] and Using for loop method.
- Using IntStream range[int startInclusive, int endExclusive].
Approach 1: Using List.listIterator[] and Using for loop method.
Syntax:
public ListIterator listIterator[]
Return Value: This method returns a list iterator over the elements in this list [in proper sequence].
- This allows bidirectional access.
- List.listIterator[] method is used to get a ListIterator over the elements in a list starting from specified position in the list. If we need to start from the last element, the starting Index would be equal to the size of the list.
Syntax:
ListIterator listIterator[ Index ] Index = Index from where list element will reverse till index = 0.
|
// Java program to iterate List in Reverse Order
import java.util.*;
class GFG {
public static void main[String[] args]
{
// For ArrayList
List list = new ArrayList[];
// Add elements to list
list.add["GEEKS"];
list.add["for"];
list.add["geeks"];
// Generate an iterator to iterate List in reverse
// order
ListIterator gfg_itr
= list.listIterator[list.size[]];
// hasPrevious[] returns true if the list has
// previous element
while [gfg_itr.hasPrevious[]]
{
// Iterate in reverse
System.out.println[gfg_itr.previous[]];
}
// print list in Reverse using for loop
for [int i = list.size[] - 1; i >= 0; i--]
{
// access elements by their index [position]
System.out.println[list.get[i]];
}
}
}
|
Approach 2: Using IntStream range[int startInclusive, int endExclusive]
- This returns a sequential ordered IntStream from startInclusive [inclusive] to endExclusive [exclusive] by an incremental step of 1. It correctly handles overflow.
Syntax :
static IntStream range[int startInclusive, int endExclusive]Parameters :
- IntStream : A sequence of primitive int-valued elements.
- startInclusive : The inclusive initial value.
- endExclusive : The exclusive upper bound.
|
// Java Program to iterate List in reverse order
import java.util.*;
import java.util.stream.IntStream;
class GFG {
public static void main[String[] args]
{
// For ArrayList
List list_li = new ArrayList[];
// Add elements to list
list_li.add[1];
list_li.add[2];
list_li.add[3];
list_li.add[4];
list_li.add[5];
// Creating an IntStream
IntStream stream = IntStream.range[0, list_li.size[]];
// Displaying the elements in range
// including the lower bound but
// excluding the upper bound
stream.map[i -> list_li.size[] - i - 1].map[list_li::get]
.forEach[System.out::println];
}
}
|
Note: IntStream range[int startInclusive, int endExclusive] basically works like a for loop. An equivalent sequence of increasing values can be produced sequentially as :
for [int i = startInclusive; i < endExclusive ; i++] { ... ... ... }Reverse a LinkedList in Java
Assuming you have gone through LinkedList in java and know about linked list. This post contains different examples for reversing a linked list which are given below:
1. By writing our own function[Using additional space]: reverseLinkedList[] method contains logic for reversing string objects in a linked list. This method takes a linked list as a parameter, traverses all the elements in reverse order and adds it to the newly created linked list.
Algorithm:
Step 1. Create a linked list with n elements
Step 2. Create an empty linked list which will be used to store reversed elements
Step 3. Start traversing the list from ‘n’ to ‘0’ and store the elements in the newly created list.
Step 4. The elements will be stored in the following order: n, n-1, n-2, ……0
Step 5. Return the list to the caller and print it
|
// Java program for reversing linked list using additional space
import java.util.*;
public class LinkedListTest1 {
public static void main[String[] args]
{
// Declaring linkedlist without any initial size
LinkedList linkedli = new LinkedList[];
// Appending elements at the end of the list
linkedli.add["Cherry"];
linkedli.add["Chennai"];
linkedli.add["Bullet"];
System.out.print["Elements before reversing: " + linkedli];
linkedli = reverseLinkedList[linkedli];
System.out.print["\nElements after reversing: " + linkedli];
}
// Takes a linkedlist as a parameter and returns a reversed linkedlist
public static LinkedList reverseLinkedList[LinkedList llist]
{
LinkedList revLinkedList = new LinkedList[];
for [int i = llist.size[] - 1; i >= 0; i--] {
// Append the elements in reverse order
revLinkedList.add[llist.get[i]];
}
// Return the reversed arraylist
return revLinkedList;
}
}
|
Time Complexity: O[n]
Space Complexity: O[n]
NOTE: As we are using additional memory space for storing all the reversed ‘n’ elements, the space complexity is O[n].
2. By writing our own function[Without using additional space]: In the previous example, a linked list is used additionally for storing all the reversed elements which takes more space. To avoid that, same linked list can be used for reversing.
Algorithm:
1. Create a linked list with n elements
1. Run the loop for n/2 times where ‘n’ is the number of elements in the linkedlist.
2. In the first pass, Swap the first and nth element
3. In the second pass, Swap the second and [n-1]th element and so on till you reach the mid of the linked list.
4. Return the linked list after loop termination.
|
// Java program for reversing an arraylist without
// using any additional space
import java.util.*;
public class LinkedListTest2 {
public static void main[String[] args]
{
// Declaring linkedlist without any initial size
LinkedList linkedli = new LinkedList[];
// Appending elements at the end of the list
linkedli.add[new Integer[1]];
linkedli.add[new Integer[2]];
linkedli.add[new Integer[3]];
linkedli.add[new Integer[4]];
linkedli.add[new Integer[5]];
System.out.print["Elements before reversing: " + linkedli];
// Calling user defined function for reversing
linkedli = reverseLinkedList[linkedli];
System.out.print["\nElements after reversing: " + linkedli];
}
// Takes a linkedlist as a parameter and returns a reversed linkedlist
public static LinkedList reverseLinkedList[LinkedList llist]
{
for [int i = 0; i < llist.size[] / 2; i++] {
Integer temp = llist.get[i];
llist.set[i, llist.get[llist.size[] - i - 1]];
llist.set[llist.size[] - i - 1, temp];
}
// Return the reversed arraylist
return llist;
}
}
|
Time Complexity: O[n/2]
Space Complexity: O[1]
3. By using Collections class: Collections is a class in java.util package which contains various static methods for searching, sorting, reversing, finding max, min….etc. We can make use of the In-built Collections.reverse[] method for reversing an linked list. It takes a list as an input parameter and returns the reversed list.
NOTE: Collections.reverse[] method uses the same algorithm as “By writing our own function[Without using additional space]”
|
// Java program for reversing a linked list using
// In-built collections class
import java.util.*;
public class LinkedListTest3 {
public static void main[String[] args]
{
// Declaring linkedlist without any initial size
LinkedList linkedli = new LinkedList[];
// Appending elements at the end of the list
linkedli.add[new Integer[1]];
linkedli.add[new Integer[2]];
linkedli.add[new Integer[3]];
linkedli.add[new Integer[4]];
linkedli.add[new Integer[5]];
System.out.print["Elements before reversing: " + linkedli];
// Collections.reverse method takes a list as a
// parameter and returns the reversed list
Collections.reverse[linkedli];
System.out.print["\nElements after reversing: " + linkedli];
}
}
|
Time Complexity: O[n/2]
Space Complexity: O[1]
4.Reversing a linked list of user defined objects: An Employee class is created for creating user defined objects with employeeID, employeeName, departmentName as class variables which are initialized in the constructor. An linked list is created that takes only Employee[user defined] Objects. These objects are added to the linked list using add[] method. The linked list is reversed using In-built reverse[] method of Collections class.
printElements[] method is used to iterate through all the user defined objects in the linked list and print the employee ID, name and department name for every object.
|
// Java program for reversing a inkedlist of user defined objects
import java.util.*;
class Employee {
int empID;
String empName;
String deptName;
// Constructor for initializing the class variables
public Employee[int empID, String empName, String deptName]
{
this.empID = empID;
this.empName = empName;
this.deptName = deptName;
}
}
public class LinkedListTest4 {
public static void main[String[] args]
{
// Declaring linkedList without any initial size
LinkedList linkedli = new LinkedList[];
// Creating user defined objects
Employee emp1 = new Employee[123, "Cherry", "Fashionist"];
Employee emp2 = new Employee[124, "muppala", "Development"];
Employee emp3 = new Employee[125, "Bullet", "Police"];
// Appending all the objects to linkedList
linkedli.add[emp1];
linkedli.add[emp2];
linkedli.add[emp3];
System.out.print["Elements before reversing: "];
printElements[linkedli];
// Collections.reverse method takes a list as a parameter
// and returns the reversed list
Collections.reverse[linkedli];
System.out.print["\nElements after reversing: "];
printElements[linkedli];
}
// Iterate through all the elements and print
public static void printElements[LinkedList llist]
{
for [int i = 0; i < llist.size[]; i++] {
System.out.print["\n EmpID:" + llist.get[i].empID + ", EmpName:"
+ llist.get[i].empName + ", Department:" + llist.get[i].deptName];
}
}
}
|
Time Complexity: O[n/2]
Space Complexity: O[1]
See reverse a linked list for reversing a user defined linked list.