Linked Lists and Array Lists Vocabulary

Linked List Overview

  • Definition: A linked list is a linear data structure where elements (nodes) are not stored at contiguous memory locations. Each element points to the next, forming a sequence.

Differences Between Array List and Linked List

  • Array List:

  • Frequently used when the size of the dataset is known.

  • Backed by an array, allowing easy insertion at the end without complex operation.

  • Removal from the middle creates holes, thus requires shifting of elements, which is an expensive operation.

  • Initialization can be pre-defined (e.g., new ArrayList<>(100)).

  • Linked List:

  • Ideal for situations where elements are frequently inserted or removed.

  • Easier to remove elements (especially from the beginning), as it only involves pointer updates.

  • Maintains a head (first element) and a tail (last element) for easier access.

Key Features of Linked Lists

  • Nodes: Composed of several properties.

  • Data: The value stored in the node.

  • Next Pointer: Points to the next node in the list.

  • Previous Pointer: (in a doubly linked list) points to the previous node.

  • Head: Boolean flag indicating if it is the first node.

  • Tail: Boolean flag indicating if it is the last node.

  • Diamond Operator: Introduced in Java 6/7 to avoid redundant typing in generics. Example: List<Integer> numbers = new LinkedList<>();

Operations on Linked Lists

  • Adding Elements: Easy to insert at any point in the list.
  • Removing Elements:
  • Removing the first element involves:
    1. Accessing the head of the list.
    2. Make the next node the new head.
    3. Remove references to the old head (garbage collectible).
  • Removing from the middle involves finding the node and adjusting pointers accordingly.

Performance Comparisons

  • Removing an Element:
  • Array List:
    • Removing the first element in a long list requires multiple operations proportional to the length of the list (e.g., a million items means a million operations).
  • Linked List:
    • Regardless of list length, removing the head only involves a few pointer adjustments (constant time operation).

When To Use Each

  • Array Lists:
  • Best for datasets of a known size or scenarios requiring indexed access and storage.
  • Linked Lists:
  • Best for applications where frequent insertion and deletion of elements are needed.

Conclusion

  • Arrays (and Array Lists) are more straightforward and familiar for most operations.
  • Linked Lists excel in scenarios involving a high frequency of additions/removals. Understanding the internal workings can help in making informed choices between these two data structures.