LinkedList Doubly Linked List Features

In Java, LinkedList is a collection class implemented based on a doubly linked list. It can store elements of any type, including primitive data types and object references. LinkedList supports dynamic addition or removal of elements and offers fast insertion and deletion operations; therefore, it is widely used within the Java Collections Framework.

The implementation principle of LinkedList involves storing elements in a doubly linked structure where each node contains references to both its predecessor (previous) node and successor (next) node. When adding or removing elements, LinkedList only needs to modify the references between adjacent nodes to complete the operation. Unlike arrays that require copying and shifting elements during insertion or deletion operations, this approach makes insertions and deletions very fast in terms of performance. However, accessing specific elements requires traversing the linked list starting from either the head node or the tail node, resulting in a time complexity of typically O(n).

The primary methods associated with LinkedList include:

  • add(E e): Adds the specified element to the end of this LinkedList.
  • add(int index, E element): Inserts the specified element at the specified position in this LinkedList.
  • remove(Object o): Removes the first occurrence of the specified element from this LinkedList.
  • remove(int index): Removes and returns the element at the specified position in this LinkedList.
  • get(int index): Returns the element at the specified position in this LinkedList.
  • set(int index, E element): Replaces the element at the specified position in this LinkedList with the specified element.
  • size(): Returns the number of elements in this LinkedList.
  • clear(): Removes all elements from this LinkedList.
  • indexOf(Object o): Returns the index of the first occurrence of the specified element in this LinkedList, or -1 if it is not contained in this LinkedList.
  • lastIndexOf(Object o): Returns the index of the last occurrence of the specified element in this LinkedList, or -1 if it is not contained in this LinkedList.
  • subList(int fromIndex, int toIndex): Creates and returns a view (subset) of the portion of this LinkedList between the indices fromIndex inclusive and toIndex exclusive.

It should be noted that because LinkedList is implemented based on a doubly linked list, its insertion and deletion operations are relatively fast with a time complexity typically of O(1). However, element access and traversal speeds are slower due to the need to traverse the linked list starting from either the head or tail node, resulting in a typical time complexity of O(n). Furthermore, since LinkedList stores references for both predecessor and successor nodes within each node structure, it incurs significant space overhead. In practical applications, suitable data structures should be selected based on specific scenarios to meet requirements effectively.