Java.util.LinkedList.get(), getFirst(), getLast() in Java

Java.util.LinkedList是Java集合框架中的一个非常常用的类，它实现了List接口，同时也实现了Deque接口，也就意味着它既是一个线性结构，又是一个双向队列。其中，get(index)、getFirst()和getLast()是LinkedList中最常用的三个方法之一。在本篇文章中，我们将探讨它们的用法和实现原理。

get(int index)

get(int index)方法接收一个整型参数index，返回LinkedList中在index处的元素。在使用get方法时，需要保证index在[0, size)范围内，否则会抛出IndexOutOfBoundsException异常。下面是get方法的示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("C++");
list.add("Python");
String element = list.get(0);
System.out.println(element); // Output: Java

在这个例子中，我们创建了一个LinkedList并添加了3个元素。然后使用get方法获取了第一个元素，并将其输出。输出的结果为”Java”。

getFirst()和getLast()

getFirst()和getLast()方法分别用于获取LinkedList的第一个和最后一个元素。如果LinkedList为空，它们都会抛出NoSuchElementException异常。下面是两个方法的示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("C++");
list.add("Python");
String firstElement = list.getFirst();
String lastElement = list.getLast();
System.out.println(firstElement); // Output: Java
System.out.println(lastElement);  // Output: Python

在这个例子中，我们创建了一个LinkedList并添加了3个元素。然后使用getFirst和getLast方法获取了第一个和最后一个元素，并将它们输出。输出的结果分别为”Java”和”Python”。

实现原理

get(int index)、getFirst()和getLast()方法的实现原理都十分简单粗暴，它们都是直接使用循环遍历LinkedList中的元素，找到相应索引或第一个和最后一个元素。在LinkedList的源代码中，get方法的实现如下：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

在这个源代码中，我们可以看到get方法中调用了node方法，node方法返回LinkedList中在index处的元素所在的节点。当index大于size的一半时，从后往前查找会比从前往后查找更快。

getFirst()和getLast()方法的实现和get方法类似，唯一的区别就是获取的索引不同。getFirst方法直接返回first节点中的元素即可，而getLast方法则返回last节点中的元素。它们的源代码如下：

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

在这两个源代码中，我们可以看到在获取节点元素之前，都需要判断first和last是否为空。如果其中任一个为空，则抛出NoSuchElementException异常。

结论

Java.util.LinkedList的get(int index)、getFirst()和getLast()方法都是使用循环遍历的方式来获取LinkedList中的元素，时间复杂度为O(n)，其中n为LinkedList的大小。因此，在使用这三个方法时要特别注意元素位置和LinkedList的大小，以避免索引越界或查找失败等问题。同时，在操作LinkedList时也需要注意该类的缺点，例如在随机访问时性能较差，可能会影响程序效率。