Java Data StructuresLesson 63Free preview
Java LinkedList
This lesson is part of Java · All levels
Summary
LinkedList is a List implementation consisting of linked nodes, so adding and removing at both ends runs very fast. This class simultaneously implemented the Deque so that it could be used as a queue or stack. The drawback is that access through the index is slow because you have to trace it from the nearest end.
Key points
- Doubly linked list structure: each node stores references to the next and previous node
- AddFirst, addLast, removeFirst, removeLast is running
- Get(i) runs O(n) because the search starts from the nearest end
- Can be used as a Queue with add/remove, or Deque with push/pop
- It's suitable for data that's often inserted/deleted in the middle, not for frequent random access.
Full lesson
Code examples and quizzes
Full lessons, code examples, and quizzes are available to subscribers. 5 questions.