Review of Data Structures: The Ultimate Guide to Linked Lists!
2022, Jun 28
Characteristics of Linked Lists
A Linked List is a data structure composed of non-contiguous memory addresses, linking elements through pointers.
Advantages of Linked Lists
Compared to Arrays, Linked Lists have the following advantages:
- Linked Lists are flexible in size and do not require a pre-specified size.
- The cost of inserting and deleting elements is lower, as it only requires changing the pointer direction without needing to shift the entire structure.
- They do not require contiguous memory space, making them more flexible.
Disadvantages of Linked Lists
Compared to Arrays, Linked Lists have the following disadvantages:
- Random access efficiency is lower, as traversal must start from the first node.
- Additional memory space is needed for pointers in each node.
- Relative addressing cannot be used directly. Arrays have contiguous addresses, allowing for relative addressing, but Linked Lists do not.
Composition of Linked Lists
Each node in a Linked List contains the following two elements:
- Data
- Pointer
Below is the code for implementing a Linked List in Kotlin
Below is the code for traversing a Linked List
Besides the above code, you can also implement a Linked List using Kotlin's Data Class:
Linked List Complexity
| Time Complexity | Worst Case | Average Case |
|---|---|---|
| Search | O(n) | O(n) |
| Insert | O(1) | O(1) |
| Deletion | O(1) | O(1) |