KC Blog

Review of Data Structures: The Ultimate Guide to Linked Lists!

2 min read
Others#algorithm#data structure

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:

  1. Linked Lists are flexible in size and do not require a pre-specified size.

  2. The cost of inserting and deleting elements is lower, as it only requires changing the pointer direction without needing to shift the entire structure.

  3. They do not require contiguous memory space, making them more flexible.

Disadvantages of Linked Lists

Compared to Arrays, Linked Lists have the following disadvantages:

  1. Random access efficiency is lower, as traversal must start from the first node.

  2. Additional memory space is needed for pointers in each node.

  3. 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:

  1. Data

  2. 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)