Kokios duomenų struktūros egzistuoja?

Štai pagrindinės duomenų struktūros:

Primityvios (Primitive):

• Sveikieji skaičiai (Integer)
• Slankiojo kablelio skaičiai (Floating-point numbers)
• Boolean reikšmės (Boolean)
• Ženklai (Character)

Abstract (Abstract):

• Masivas (Array): Tvarkingas vieno tipo elementų rinkinys, prieiga per indeksą su pastovia laiko sudėtingumu.
• Sujungtas sąrašas (Linked List): Mazgų rinkinys, kiekvienas turintis duomenis ir nuorodą į kitą mazgą. Efektyvus pridėjimas/pašalinimas pradžioje/pabaigoje, prieiga per indeksą - $O(n)$.
  • Vienpusis (Singly Linked List)
  • Dviejų krypčių (Doubly Linked List)
  • Ciklinis (Circular Linked List)
• Stovas (Stack): Duomenų struktūra LIFO (Last-In, First-Out). Operacijos: push (pridėti), pop (pašalinti), peek (peržiūrėti viršutinį 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
      }
  }
  

• Eilė (Queue): Duomenų struktūra FIFO (First-In, First-Out). Operacijos: enqueue (pridėti), dequeue (pašalinti), peek (peržiūrėti pirmą 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 lentelė (Hash Table) / Žodynas (Dictionary) / Asocijuotas masyvas (Associative Array): Rinkinys porų "raktas-reikšmė", leidžiantis efektyviai ieškoti, pridėti ir ištrinti pagal raktą naudojant hash funkciją.

  var dictionary = [String: Any]() // Pavyzdys žodyno Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Rinkinys (Set): Nesutvarkytas unikalių elementų rinkinys. Palaiko operacijas: pridėjimas, ištrynimas, tikrinimas, unija, sankirta, skirtumas.

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

• Medis (Tree): Hierarchinė duomenų struktūra, sudaryta iš mazgų, susijusių briaunomis. Turi šaknies mazgą ir palikuonis:
  • Dvejetainis medis (Binary Tree)
  • Dvejetainis paieškos medis (Binary Search Tree - BST)
  • Subalansuotas dvejetainis medis (Balanced Binary Tree) - AVL, raudonas-juodas medis
  • B-medžio (B-Tree)
• Tinklas (Graph): Vertsnių (mazgų) ir briaunų (ryšių) rinkinys, jungiantis vertes. Gali būti nukreiptas arba nenukreiptas, su svoriais arba be jų.

Šių duomenų struktūrų supratimas yra labai svarbus rašant efektyvų ir mastelį turintį kodą. Tinkama duomenų struktūra pasirenkama priklausomai nuo operacijų našumo reikalavimų (paieška, įterpimas, ištrynimas) ir duomenų pobūdžio.