6 Datenstrukturen, die jeder Programmierer kennen sollte

Der Weg zum kompetenten und erfolgreichen Programmierer ist schwierig, aber durchaus machbar. Datenstrukturen sind eine Kernkomponente, die jeder Programmierstudent beherrschen muss, und wahrscheinlich haben Sie bereits einige grundlegende Datenstrukturen wie Arrays oder Listen gelernt oder damit gearbeitet.

Interviewer neigen dazu, Fragen zu Datenstrukturen zu stellen. Wenn Sie sich also auf ein Vorstellungsgespräch vorbereiten, müssen Sie Ihr Wissen über Datenstrukturen auffrischen. Lesen Sie weiter, denn wir listen die wichtigsten Datenstrukturen für Programmierer und Vorstellungsgespräche auf.

Verknüpfte Listen sind eine der grundlegendsten Datenstrukturen und oft der Ausgangspunkt für Studenten in den meisten Datenstrukturkursen. Verkettete Listen sind lineare Datenstrukturen, die einen sequentiellen Datenzugriff ermöglichen.

Elemente innerhalb der verknüpften Liste werden in einzelnen Knoten gespeichert, die über Zeiger verbunden (verknüpft) sind. Sie können sich eine verkettete Liste als eine Kette von Knoten vorstellen, die über verschiedene Zeiger miteinander verbunden sind.

Verwandt: Eine Einführung in die Verwendung von verknüpften Listen in Java

Bevor wir auf die Besonderheiten der verschiedenen Arten von Linked Lists eingehen, ist es entscheidend, die Struktur und Implementierung der einzelnen Nodes zu verstehen. Jeder Knoten in einer verknüpften Liste hat mindestens einen Zeiger (doppelt verknüpfte Listenknoten haben zwei Zeiger), der ihn mit dem nächsten Knoten in der Liste und dem Datenelement selbst verbindet.

Jede verknüpfte Liste hat einen Kopf- und einen Endknoten. Einfach verknüpfte Listenknoten haben nur einen Zeiger, der auf den nächsten Knoten in der Kette zeigt. Zusätzlich zum nächsten Zeiger haben doppelt verkettete Listenknoten einen weiteren Zeiger, der auf den vorherigen Knoten in der Kette zeigt.

Interviewfragen zu verknüpften Listen drehen sich normalerweise um das Einfügen, Suchen oder Löschen eines bestimmten Elements. Das Einfügen in eine verkettete Liste dauert O(1) Zeit, aber das Löschen und Suchen kann im schlimmsten Fall O(n) Zeit in Anspruch nehmen. Verlinkte Listen sind also nicht ideal.

2. Binärbaum

Binäre Bäume sind die beliebteste Teilmenge der Baumfamilien-Datenstruktur; Elemente in einem binären Baum sind in einer Hierarchie angeordnet. Andere Baumarten sind AVL-, Rot-Schwarz-, B-Bäume usw. Knoten des Binärbaums enthalten das Datenelement und zwei Zeiger auf jeden Kindknoten.

Jeder Elternknoten in einem binären Baum kann maximal zwei Kindknoten haben, und jeder Kindknoten kann wiederum ein Elternteil von zwei Knoten sein.

Verwandt: Ein Anfängerleitfaden für binäre Bäume

Ein binärer Suchbaum (BST) speichert Daten in einer sortierten Reihenfolge, wobei Elemente mit einem Schlüsselwert kleiner als der übergeordnete Knoten werden auf der linken Seite gespeichert, und Elemente mit einem Schlüsselwert größer als der übergeordnete Knoten werden auf der Rechts.

Binäre Bäume werden häufig in Interviews gefragt. Wenn Sie sich also auf ein Interview vorbereiten, sollten Sie wissen, wie Sie einen binären Baum glätten, ein bestimmtes Element nachschlagen und vieles mehr.

3. Hash-tabelle

Hash-Tabellen oder Hash-Maps sind eine hocheffiziente Datenstruktur, die Daten in einem Array-Format speichert. Jedem Datenelement wird in einer Hash-Tabelle ein eindeutiger Indexwert zugewiesen, der ein effizientes Suchen und Löschen ermöglicht.

Der Vorgang der Zuweisung oder Zuordnung von Schlüsseln in einer Hash-Map wird als Hashing bezeichnet. Je effizienter die Hash-Funktion, desto besser die Effizienz der Hash-Tabelle selbst.

Jede Hash-Tabelle speichert Datenelemente in einem Wert-Index-Paar.

Dabei sind Wert die zu speichernden Daten und Index die eindeutige ganze Zahl, die zum Zuordnen des Elements in die Tabelle verwendet wird. Hashfunktionen können sehr komplex oder sehr einfach sein, abhängig von der erforderlichen Effizienz der Hashtabelle und der Art und Weise, wie Sie Kollisionen auflösen.

Kollisionen treten häufig auf, wenn eine Hash-Funktion dieselbe Abbildung für verschiedene Elemente erzeugt; Hash-Map-Kollisionen können auf verschiedene Weise gelöst werden, indem offene Adressierung oder Verkettung verwendet wird.

Hash-Tabellen oder Hash-Maps haben eine Vielzahl unterschiedlicher Anwendungen, einschließlich Kryptographie. Sie sind die Datenstruktur der ersten Wahl, wenn eine Einfügung oder Suche in konstanter O(1)-Zeit erforderlich ist.

4. Stapel

Stacks gehören zu den einfacheren Datenstrukturen und sind ziemlich einfach zu beherrschen. Eine Stack-Datenstruktur ist im Wesentlichen jeder reale Stack (denken Sie an einen Stapel von Kisten oder Platten) und arbeitet nach dem LIFO-Prinzip (Last In First Out).

Die LIFO-Eigenschaft von Stacks bedeutet, dass zuerst auf das zuletzt eingefügte Element zugegriffen wird. Sie können nicht auf Elemente unterhalb des obersten Elements in einem Stapel zugreifen, ohne die Elemente darüber zu öffnen.

Stacks haben zwei Hauptoperationen – Push und Pop. Push wird verwendet, um ein Element in den Stack einzufügen, und pop entfernt das oberste Element aus dem Stack.

Sie haben auch viele nützliche Anwendungen, daher ist es sehr üblich, dass Interviewer Fragen zu Stapeln stellen. Es ist sehr wichtig zu wissen, wie man einen Stapel umkehrt und Ausdrücke auswertet.

5. Warteschlangen

Warteschlangen ähneln Stacks, arbeiten jedoch nach dem FIFO-Prinzip (First In First Out), d. h. Sie können auf die Elemente zugreifen, die Sie zuvor eingefügt haben. Die Warteschlangen-Datenstruktur kann als jede reale Warteschlange visualisiert werden, in der die Personen entsprechend ihrer Ankunftsreihenfolge positioniert werden.

Ein Einfügen einer Warteschlange wird als Einreihen bezeichnet, und das Löschen/Entfernen eines Elements vom Anfang der Warteschlange wird als Dequeuing bezeichnet.

Verwandt: Ein Anfängerleitfaden zum Verständnis von Warteschlangen und Prioritätswarteschlangen

Prioritätswarteschlangen sind eine integrale Anwendung von Warteschlangen in vielen wichtigen Anwendungen, wie z. B. CPU-Scheduling. In einer Prioritätswarteschlange werden Elemente nach ihrer Priorität und nicht nach der Reihenfolge ihres Eintreffens geordnet.

6. Haufen

Heaps sind eine Art von Binärbaum, in dem Knoten in aufsteigender oder absteigender Reihenfolge angeordnet sind. In einem Min Heap ist der Schlüsselwert des Elternteils gleich oder kleiner als der seiner Kinder, und der Wurzelknoten enthält den Mindestwert des gesamten Heaps.

Ebenso enthält der Wurzelknoten eines Max Heap den maximalen Schlüsselwert des Heaps; Sie müssen die Min/Max-Heap-Eigenschaft im gesamten Heap beibehalten.

Verwandt: Haufen vs. Stapel: Was zeichnet sie aus?

Heaps haben aufgrund ihrer sehr effizienten Natur viele Anwendungen; In erster Linie werden Prioritätswarteschlangen oft durch Heaps implementiert. Sie sind auch eine Kernkomponente in Heapsort-Algorithmen.

Datenstrukturen lernen

Datenstrukturen können auf den ersten Blick erschütternd erscheinen, aber nehmen Sie sich genügend Zeit, und Sie werden sie kinderleicht finden.

Sie sind ein wichtiger Bestandteil der Programmierung und für fast jedes Projekt müssen Sie sie verwenden. Es ist wichtig zu wissen, welche Datenstruktur für ein bestimmtes Szenario ideal ist.

7 Algorithmen, die jeder Programmierer kennen sollte

Diese Algorithmen sind für den Arbeitsablauf jedes Programmierers unerlässlich.

Weiter lesen

Über den Autor