Linked List in Java

After several years of not using Java, I wanted to apply a linked list and was surprised how non-intuitive it is. The interface provides functions like
add(int index, E element) for adding an element at the position index,
get(int index) for retreiving the element at the position index,
remove(int index) for removing at the position index.
These operations traverse the list to find the position and use O(n) time.

It is no surprise then that the examples on the Internet use mostly these functions to operate on the list. For example, the list traversal is explained using get(i) and results in a quadratic operation instead of a linear one.

In my opinion, the operations that are based on the index should not be provided at all, because they contradict the idea of a linked list. If a programmer wants to access a collection using an index he should either program it by himself or use an ArrayList.

The correct way to process the LinkedList is to use an iterator. Because the Java iterator is not very intuitive I present here simple use cases.

import java.util.LinkedList;
import java.util.ListIterator;

static void listTest() {
    LinkedList<Integer> list = new LinkedList<>();
    for (int i = 1; i <= 4; ++i) list.add(i); // add at the end
    printList("List", list);
    // => List: 1 2 3 4
    
    // Replace 2 by 8
    ListIterator<Integer> iter = list.listIterator();
    while (iter.hasNext()) {
        int el = iter.next();
        if (el == 2) iter.set(8);   // replace 2 with 8
    }
    printList("Replaced 2 by 8", list);
    // => Replaced 2 by 8: 1 8 3 4 
    
    // Insert 9 after 8
    iter = list.listIterator(); // reset iterator to beginning
    while (iter.hasNext()) {
        int el = iter.next();
        if (el == 8) iter.add(9);   // Insert 9 after 8
    }
    printList("Inserted 9 after 8", list);
    // => Inserted 9 after 8: 1 8 9 3 4 

    // Remove 8
    iter = list.listIterator(); // reset iterator to beginning
    while (iter.hasNext()) {
        int el = iter.next();
        if (el == 8) iter.remove(); // remove element 8 
    }
    printList("Removed 8", list);
    // => Removed 8: 1 9 3 4 

    // Remove 9 and insert it again at the same position
    iter = list.listIterator(); // reset iterator to beginning
    while (iter.hasNext()) {
        int el = iter.next();
        if (el == 9) {
            iter.remove();  // remove element 9 
            iter.add(9);    // insert 9 again
        }
    }
    printList("Remove 9 and insert again", list);
    // Removed 9 and inserted again : 1 9 3 4 
}

static <E> void printList(String title, LinkedList<E> list) {
    System.out.print(title + ": ");
    ListIterator<E> iter = list.listIterator(); // set to begin
    while (iter.hasNext()) {
        E elem = iter.next();
        System.out.print(elem + " ");
    }   
    System.out.println();
}

Notice that the list cannot be processed recursively during the traversal. I will return to this problem in another post.

Kommentare