LinkedList: Doubly-linked list implementation

In Java, a LinkedList is a data structure that represents a doubly-linked list. It is an ordered collection of elements where each element points to both its previous and next element, allowing for efficient insertion, removal, and traversal operations.

Creating a LinkedList

To create a LinkedList, you can simply instantiate the class without providing any initial elements:

LinkedList<String> linkedList = new LinkedList<>();

Alternatively, you can initialize a LinkedList with an existing collection:

List<String> initialElements = Arrays.asList("apple", "banana", "cherry");
LinkedList<String> linkedList = new LinkedList<>(initialElements);

Adding Elements

Elements can be added to the LinkedList using various methods:

• add(element): Appends the specified element to the end of the list.
• add(index, element): Inserts the specified element at the specified position.
• addAll(collection): Appends all elements in the specified collection to the end of the list.

For example:

linkedList.add("date");
linkedList.add(1, "grape");
linkedList.addAll(Arrays.asList("fig", "kiwi"));

The LinkedList will now contain: ["apple", "grape", "banana", "cherry", "date", "fig", "kiwi"].

Removing Elements

Elements can be removed from the LinkedList using various methods:

• remove(): Removes and returns the first element in the list.
• remove(index): Removes and returns the element at the specified position.
• remove(element): Removes the first occurrence of the specified element in the list.

For example:

String firstElement = linkedList.remove();
String removedElement = linkedList.remove(2);
boolean removed = linkedList.remove("banana");

After removing, the LinkedList will be: ["grape", "cherry", "date", "fig", "kiwi"].

Accessing Elements

You can access elements in the LinkedList using methods like get(index) or peek():

String grape = linkedList.get(0);
String cherry = linkedList.peek();

Both invocations will return "grape", as it is the first element in the list.

Iterating over Elements

The LinkedList provides several ways to iterate over its elements:

• Using an enhanced for loop:

for (String element : linkedList) {
    // Perform operations with element
}

• Using an iterator:

Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    // Perform operations with element
}

• Using functional-style operations (Java 8+):

linkedList.forEach(element -> {
    // Perform operations with element
});

Advantages of LinkedList

• Insertion and deletion operations are efficient since it only requires adjusting the adjacent pointers.
• LinkedLists can dynamically grow or shrink as elements are added or removed.

Disadvantages of LinkedList

• Random access to elements is slower compared to indexed collections like ArrayList, as it requires traversing the linked nodes from the head or tail.
• LinkedLists consume slightly more memory than arrays due to the additional pointers.

Overall, LinkedList is a versatile data structure with efficient insertion and removal operations, making it well-suited for scenarios where elements are frequently modified or reordered.