Data Structure and Algorithm - Linked List

• 2/3/2023
• One-minute read

This post will go through one of the most essential data structure - linked list.

 

Contiguous vs Linked Data Structures

There are many ways we can categorize data structures. One way would be to classify them as contiguous or linked data structure.

• Contiguously-Allocated Data Structures

  These data structures are composed of a single section of memory. This means that the allocated memory are all next to each other.

• Non-Contiguously-Allocated Data Structures (Linked Data Structures)

  These data structures are composed of memory chunks that are scattered all around the RAM. All of these memory space are linked together by pointers. Examples of *linked data structures are linked lists, trees, graph adjacency lists.

   

Arrays vs Linked Lists

Now we are going to compare the most common contiguous data structure (array) with the most common linked data structure (linked lists). Each of them holds their own advantages and disadvantages.

 

Array

• Constant Time Access

  The index of an element in an array maps directly to a memory address. Therefore, we can immediately access an element in an array using its index.

• Space Efficiency

  All an array stores is the data that we are interested in. We don’t need to allocate extra memory space for pointers to link the elements together.