Skip to main content

Introduction

Definition​

A data structure is a way of organizing and storing data to perform operations efficiently. It defines the relationship between data elements and the operations that can be performed on them.

Operations​

  • Access: retrieve data from a specific location. Accessing an array element or a node in a linked list.
  • Search: find a specific piece of data. Binary search for sorted arrays, linear search for unsorted arrays.
  • Insertion: add data to a specific location. Inserting at the end of a linked list or at the top of a stack.
  • Deletion: remove data from a specific location. Deleting a node from a linked list or popping from a stack.
  • Traversal: visit every data element in a data structure. Common techniques include in-order, pre-order, and post-order traversal for trees.
  • Sorting: arrange data elements in a specific order. QuickSort, MergeSort, and HeapSort are common sorting algorithms.
  • Merging: combine two data structures into one. Merging two sorted arrays into a single sorted array.

Complexity​

Time complexity​

Describes the amount of time an algorithm takes concerning its input size. Big O notation is commonly used to express time complexity.

Space complexity​

Describes the amount of memory an algorithm uses concerning its input size. Also expressed using Big O notation.

Trade-offs​

  • Different data structures have trade-offs in terms of time and space complexity.
  • Choosing the right structure depends on the specific requirements of the problem at hand.

Considerations​

  • Understand the access patterns, insertion/deletion frequencies, and the size of the dataset.
  • Consider the operations that need to be performed efficiently.