• Internally implemented as doubly linked list
  • Duplicates are allowed
  • Heterogeneous methods are allowed
  • Null insertion is possible
  • Implements Serializable and Clonable Interface but not Random Acces
  • Best Chose – Frequent Operation is insertion in the middle
  • Worst Chose – Frequent Operation is retrieval from middle

LinkedList Class-specific methods :

  • Usually, we can use linkedlist to develop stack and queues, to provide support for this requirement linked list provides following methods :
    • void addFirst(Object o)
    • void addLast(Object o)
    • Object getFirst()
    • Object getLast()
    • Object removeFirst()
    • Object removeLast()

The Problem of Linked-List

Unlike array, which is a cache-friendly data structure because its elements are placed right next to each other, elements of linked-list can be placed anywhere in the memory. So when iterating through linked-list, it will cause a lot of cache miss (since we can’t make use of locality of reference), and introduce lots of performance overheads.

Complexity of Linked List

Linked ListTime ComplexitySpace Complexity
Adding ElementO(1)
Removing ElementO(n/2), from start or end would be O(1)
Iterating ElementsO(n)
Retreving Element at PositionO(n/2)

Leave a Comment