YouTipData Search
## Java LinkedList: Searching for Elements
In Java, the `LinkedList` class provides built-in methods to search for elements within a list. This tutorial demonstrates how to find the first and last occurrences of a specific element in a `LinkedList` using the `indexOf()` and `lastIndexOf()` methods.
---
### Introduction to Search Methods
When working with a `LinkedList` in Java, you often need to determine whether an element exists in the list and retrieve its position (index). The `java.util.LinkedList` class provides two highly efficient methods for this purpose:
* **`indexOf(Object o)`**: Returns the index of the **first occurrence** of the specified element in this list, or `-1` if the list does not contain the element.
* **`lastIndexOf(Object o)`**: Returns the index of the **last occurrence** of the specified element in this list, or `-1` if the list does not contain the element.
Both methods use zero-based indexing, meaning the first element of the list is at index `0`.
---
### Method Syntax
```java
public int indexOf(Object o)
public int lastIndexOf(Object o)
```
#### Parameters
* `o`: The element to search for in the list.
#### Return Value
* Returns the `int` index of the element if found.
* Returns `-1` if the element is not present in the list.
---
### Code Example
The following example demonstrates how to initialize a `LinkedList`, populate it with duplicate elements, and find the first and last occurrences of a specific value.
```java
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Create a LinkedList of Strings
LinkedList lList = new LinkedList<>();
// Add elements to the LinkedList
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
lList.add("2"); // Duplicate element to demonstrate lastIndexOf
// Find the first occurrence of "2"
System.out.println("First occurrence of element '2' is at index: " + lList.indexOf("2"));
// Find the last occurrence of "2"
System.out.println("Last occurrence of element '2' is at index: " + lList.lastIndexOf("2"));
}
}
```
### Output
When you run the program, it will produce the following output:
```text
First occurrence of element '2' is at index: 1
Last occurrence of element '2' is at index: 5
```
---
### Key Considerations
1. **Zero-Based Indexing**: Always remember that Java collections use `0` as the starting index. In the example above, `"1"` is at index `0`, and the first `"2"` is at index `1`.
2. **Performance**:
* `indexOf()` traverses the list from head to tail (index `0` to `size - 1`).
* `lastIndexOf()` traverses the list from tail to head (index `size - 1` down to `0`).
* In the worst-case scenario (where the element is not in the list), both methods have a time complexity of **$O(n)$**, where $n$ is the number of elements in the list.
3. **Null Values**: If the `LinkedList` allows null elements, both methods can search for `null` without throwing a `NullPointerException`. Calling `lList.indexOf(null)` will return the index of the first null element.