What data structures exist?

The following are the main data structures:

Primitive:

• Integer numbers
• Floating-point numbers
• Boolean values
• Characters

Abstract:

• Array: An ordered collection of elements of the same type, accessed by index with constant time.
• Linked List: A collection of nodes, each containing data and a reference to the next node. Efficient addition/removal at the beginning/end, access by index - $O(n)$.
  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List
• Stack: A LIFO (Last-In, First-Out) data structure. Operations: push (add), pop (remove), peek (view top element).

  struct Stack<Element> {
      private var elements: [Element] = []
  
      mutating func push(_ element: Element) {
          elements.append(element)
      }
  
      mutating func pop() -> Element? {
          return elements.popLast()
      }
  
      func peek() -> Element? {
          return elements.last
      }
  
      var isEmpty: Bool {
          return elements.isEmpty
      }
  }
  

• Queue: A FIFO (First-In, First-Out) data structure. Operations: enqueue (add), dequeue (remove), peek (view first element).

  struct Queue<Element> {
      private var elements: [Element] = []
  
      mutating func enqueue(_ element: Element) {
          elements.append(element)
      }
  
      mutating func dequeue() -> Element? {
          guard !elements.isEmpty else { return nil }
          return elements.removeFirst()
      }
  
      func peek() -> Element? {
          return elements.first
      }
  
      var isEmpty: Bool {
          return elements.isEmpty
      }
  }
  

• Hash Table / Dictionary / Associative Array: A collection of key-value pairs, allowing efficient search, addition, and removal by key using a hash function.

  var dictionary = [String: Any]() // Example of a dictionary in Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Set: An unordered collection of unique elements. Supports operations: add, remove, check existence, union, intersection, difference.

  var set: Set<Int> = [1, 2, 3] // Example of a set in Swift
  set.insert(4)
  let containsTwo = set.contains(2)
  

• Tree: A hierarchical data structure consisting of nodes connected by edges. Has a root node and child nodes.
  • Binary Tree
  • Binary Search Tree (BST)
  • Balanced Binary Tree - AVL, Red-Black Tree
  • B-Tree
• Graph: A set of vertices (nodes) and edges (connections) linking the vertices. Can be directed or undirected, weighted or unweighted.

Understanding these data structures is critical for writing efficient and scalable code. The choice of the right data structure depends on performance requirements (search, insert, delete) and data characteristics.