Hello! Sometimes, you don't have to implement the linked list yourself. Java has a built-in LinkedList class — a fundamental tool for implementing data structures. We have even used it a bit for initializing queues and stacks. In this lesson, you will learn to use Java's LinkedList, understand its methods, and see them in action.

Java's LinkedList is part of the Java Collections Framework. It represents a doubly-linked list and provides numerous methods for performing operations like adding and removing elements, searching elements, and iterating through the list.

A doubly-linked list is similar to a singly-linked list, but with one key difference. While a singly-linked list has nodes containing a reference to the next node in the sequence, in a doubly-linked list, each node contains a reference to both the next node and the previous node in the sequence. This gives more flexibility in navigating through the list, allowing both forward and backward traversals, but at the cost of increased complexity and resource usage for maintaining references in both directions.

Let’s begin by creating a LinkedList in Java. You start by instantiating the LinkedList class, as shown below:

Java
Copy to clipboard
1import java.util.LinkedList;
2
3public class Main {
4  public static void main(String[] args) {
5    LinkedList<String> students = new LinkedList<>();
6  }
7}

In the above code, we create a LinkedList called students that will store String type data. However, it's currently empty. Let's see how we can operate on this LinkedList.

Java's LinkedList class comes loaded with many powerful methods. We'll focus on some basic yet very important ones:

• add(E element): This method appends the specified element to the end of the list.
• add(int index, E element): This method inserts the specified element at the specified position in the list.
• remove(): This method retrieves and removes the list's head (the first element).
• get(int index): Returns the element at the specified position in the list.

These methods are demonstrated in the following code:

Java
Copy to clipboard
1import java.util.LinkedList;
2
3public class Main {
4    public static void main(String[] args) {
5        LinkedList<String> students = new LinkedList<>();
6
7        students.add("John");
8        students.add(0, "Alice");
9        System.out.println(students.get(0));  // prints Alice
10        students.remove();
11        System.out.println(students.get(0));  // prints John
12    }
13}

To visit each element in the LinkedList, we must traverse from the start node to the end node. Java's ListIterator interface helps with this and provides the methods for such iterations. Let's look at an example:

Java
Copy to clipboard
1import java.util.LinkedList;
2import java.util.ListIterator;
3
4public class Main {
5    public static void main(String[] args) {
6        LinkedList<String> students = new LinkedList<>();
7
8        students.add("John");
9        students.add("Alice");
10
11        ListIterator li = students.listIterator();
12
13        while(li.hasNext()){
14            System.out.println(li.next());
15        }
16        /*
17        Output:
18        John
19        Alice
20         */
21    }
22}

Now, let's learn a few more exciting methods of Java's LinkedList:

• addFirst(E e): This method inserts the specified element at the beginning of the list.
• addLast(E e): This method appends the specified element at the end of the list.
• clear(): This method removes all elements from the list.
• contains(Object obj): This method returns true if the list contains the specified element.
• isEmpty(): This method returns true if the list contains no elements.

Here is an instance where we use these methods:

Java
Copy to clipboard
1import java.util.LinkedList;
2
3public class Main {
4    public static void main(String[] args) {
5        LinkedList<String> students = new LinkedList<>();
6
7        students.addFirst("John");
8        students.addLast("Alice");
9        System.out.println(students.contains("Alice"));  // prints true
10        System.out.println(students.isEmpty());  // prints false
11        students.clear();
12        System.out.println(students.isEmpty());  // prints true
13    }
14}

Understanding the time complexities involved in LinkedList operations becomes critical as we journey further. We'll discuss these complexities using Big O notation:

• add(int index, E element): The worst-case time complexity is O(n) as it needs to traverse the list.
• add(E element): The time complexity is O(1) as it adds an element at the end of the list.
• remove(): It is also O(1) as it removes the first element of the list.

Congratulations! We've covered Java's' LinkedList' creation, operations, traversal, and complexities. To encourage practice, which is central to mastering these operations and understanding their utility, this lesson is followed by several exercises that will take you one step closer to becoming a pro in using LinkedList. So, get ready, and happy coding!