The Big O Notation
Die Big-O-Notation wird verwendet, um die Rechenkomplexität eines Programms oder einer Datenstruktur anzugeben. Das bedeutet im Grunde: Wie viele Schritte werden benötigt, um eine bestimmte Aktion auszuführen.
Diese Seite fasst einige der wichtigsten Datenstrukturen und Algorithmen zusammen
Eine Datenstruktur dient zur Speicherung und Organisation von Daten. Diese Strukturen ordnen und verknüpfen die Daten in einer bestimmten Art und Weise, um verschiedene Aufgaben/Probleme zu bewältigen. Folgend werden einige von ihnen beleuchtet.
The Array
Arrays haben eine lineare Datenstruktur und sind Container, die eine konkrete Anzahl von Werten enthalten.
The Linked List
Linked Lists haben eine lineare Datenstruktur. Es sind Listen aus verknüpften Elementen. Jedes Element zeigt auf den nächsten Knoten in der Liste.
The Stack
Ein Stack hat eine lineare Datenstruktur. Er platziert Elemente stapelweise. Das Verhalten des Stacks wird als last-in-first-out-Prinzip (LIFO) beschrieben.
The Queue
Queues sind lineare abstrakte Datenstrukturen, die eine lange Liste von Elementen enthalten können. Sie folgen dem first-in-first-out-Prinzip (FIFO).
The Hash Table
Eine Hash Table bietet die Möglichkeit, Daten in Form eines Schlüssels(key) und eines Werts(value) darzustellen. Eine ordnungsgemäße Implementierung bietet sehr schnelle Einfüge-, Such- und Entfernungszeiten.
The Binary Tree
Bei Binary Trees handelt es sich um eine Sammlung von Knoten in einer Baumstruktur. Jeder Knoten bestizt höchstens zwei Kinder und somit insgesamt drei Attribute: value, left_child und right_child.
The AVL Tree
Der AVL-Tree ist ein sich selbstausgleichender Binary-Search-Tree (BST), bei dem der Höhenunterschied zwischen linken und rechten Teilbäumen für alle Knoten nicht größer als eins sein darf.
The Heap
Heaps sind fast wie Binary Trees, nur mit einigen zusätzlichen Regeln hinsichtlich der Form des Baumes und der Reihenfolge der Baumknoten.
The Trie
Tries haben eine baumartige Datenstruktur, deren Knoten die Buchstaben des Alphabets speichern. Durch das Strukturieren der Knoten in einer bestimmten Weise, können Wörter beim Durchlaufen eines Zweigpfads des Baums wiedergewonnen werden.
The Graph
Ein Graph ist eine flexible Datenstruktur, die verwendet werden kann, um Daten mit komplexen Beziehungen zwischen Knoten darzustellen. Er besteht aus Scheitelpunkten, die durch Kanten mit anderen Scheitelpunkten (gerichtet oder ungerichtet) verbunden sind.
Sorting Algorithms
Sortieralgorithmen sind Algorithmen, die Elemente in einer Liste in eine Reihenfolge sortieren. Neben anderen Anwendungen kann das Sortieren genutzt werden, um einen Datensatz für einen anderen Algorithmus vorzubereiten.
Searching Algorithms
Suchalgorithmen werden verwendet, um Informationen aus einer Datenstruktur abzurufen. Es gibt verschiedene Arten.