循环链表是一种数据结构，其中最后一个节点的next连接回到第一个节点，形成一个循环。此结构允许连续遍历而不会中断。
循环链表对于日程安排和音乐播放列表等任务特别有用，这允许播放完毕后回到第一首继续播放。
在这小节中，我们将介绍循环链表的基础知识、如何使用它们、它们的优点和缺点以及它们的应用。

什么是循环链表？

循环链表是一种特殊类型的链表，其中所有节点都连接起来形成一个环。
与我们前面讲到的链表不同的是，循环链表中的最后一个节点的next指向第一个节点。这意味着当遍历到尾部时可以继续向头部遍历。

循环链表是从单链表和双链表扩展出来的，因此，循环链表基本只有这两种类型。

循环单链表

在循环单链表中，每个节点只有一个指针，称为next指针。最后一个节点的next指针指向第一个节点，这样就形成了一个环。在循环单链表中，我们只能沿一个方向遍历链表。

循环单链表结构

数据结构

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

data：数据域，也是节点的值
next：指针域，指向下一个结点的指针

在上面的定义中，每个节点都有data数据域和next指针域，和普通的单链表结构一模一样，唯一区别就是当我们为循环链表创建多个节点时，我们只需要将最后一个节点连接回第一个节点即可。

循环单链表的基本操作实现

创建循环单链表

插入是链表中的基本操作。和普通单链表的唯一区别是将最后一个节点的next连接到第头结点。
插入大概可以分为以下三种情况

1.在空链表中插入新结点

在空链表中插入新结点

这里使用的是带头结点的单链表来实现循环链表，所以链表空的条件是头结点的next指向头结点，即头结点自己指向自己。
在空的循环链表中插入一个节点，需要创建一个新结点，将其next指针指向头结点，以达到循环的目的。

2.在链表中部插入新结点

在链表中部插入新结点

和普通单链表操作一样，在中部插入结点并没有改变尾结点next的指向。

3.在链表尾部插入新结点

在链表尾部插入新结点

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

上面三种情况，都可以统一为同一操作：
1.找到待插入位置的前驱结点，即p；
2.创建新结点pTemp；
3.使pTemp的next指向p的next；
（如果是空链表，那么p的next指向头结点本身。如果是在末尾插入，p的next同样也是指向头结点）
4.使p的next指向pTemp；

按位序插入结点 | 可视化完整可视化

2.4 Detaillierte Erklärung der zirkulären einfach verknüpften Liste – Tutorial zur linearen Liste Visualisiere deinen Code mit Animationen

```html

Lineare Liste und verkettete Liste: Grundlagen für dein Datenstrukturen-Verständnis

Wenn du mit dem Lernen von Datenstrukturen und Algorithmen beginnst, wirst du schnell auf zwei fundamentale Konzepte stoßen: die lineare Liste (auch Array oder sequenzielle Liste genannt) und die verkettete Liste (Linked List). Beide sind grundlegende Bausteine der Informatik und bilden die Basis für komplexe Datenstrukturen wie Stapel, Warteschlangen oder Graphen. In diesem Artikel erklären wir dir die Prinzipien, Eigenschaften und typischen Anwendungen beider Listen – verständlich und direkt für Lernende wie dich. Außerdem zeigen wir dir, wie ein Datenstruktur-Visualisierungsplattform dir helfen kann, diese Konzepte intuitiv zu erfassen.

Was ist eine lineare Liste? – Die sequenzielle Speicherung

Eine lineare Liste ist eine geordnete Sammlung von Elementen, bei der jedes Element einen Vorgänger (außer das erste) und einen Nachfolger (außer das letzte) hat. Die einfachste Form ist das Array (Feld). Hier werden alle Elemente hintereinander im Speicher abgelegt. Du kannst auf jedes Element direkt über seinen Index zugreifen – das nennt man wahlfreien Zugriff (Random Access). Beispiel: Das dritte Element eines Arrays hat den Index 2 (bei nullbasierter Zählung) und ist sofort adressierbar.

Eigenschaften der linearen Liste (Array):

Feste Größe: Ein Array hat eine bei der Erstellung festgelegte Länge. Wenn du mehr Elemente speichern willst, musst du ein neues, größeres Array anlegen und die Daten kopieren.
Wahlfreier Zugriff (O(1)): Du kannst auf jedes Element in konstanter Zeit zugreifen, unabhängig von der Position.
Ineffizientes Einfügen und Löschen: Wenn du ein Element in der Mitte einfügen oder löschen willst, musst du alle nachfolgenden Elemente verschieben. Das kostet Zeit – im Durchschnitt O(n).
Speicherlokation: Alle Elemente liegen physikalisch nahe beieinander, was Cache-Effizienz begünstigt.

Typische Anwendungen: Arrays werden überall dort eingesetzt, wo die Größe der Datenmenge bekannt ist und du oft auf Elemente zugreifen musst – z. B. in Tabellenkalkulationen, Bildverarbeitung (Pixel-Arrays) oder als Basis für Matrizen.

Was ist eine verkettete Liste? – Dynamische Verbindungen

Eine verkettete Liste (Linked List) besteht aus Knoten, die über Zeiger (Pointer) miteinander verbunden sind. Jeder Knoten enthält zwei Teile: die Nutzdaten und einen Zeiger auf den nächsten Knoten. Bei einer einfach verketteten Liste zeigt jeder Knoten nur auf den Nachfolger. Bei einer doppelt verketteten Liste gibt es zusätzlich einen Zeiger auf den Vorgänger. Der erste Knoten heißt Kopf (Head), der letzte Knoten zeigt auf null (None).

Eigenschaften der verketteten Liste:

Dynamische Größe: Eine verkettete Liste kann während der Laufzeit wachsen oder schrumpfen, ohne dass eine Neuzuweisung des gesamten Speichers nötig ist.
Sequenzieller Zugriff (O(n)): Um auf ein Element zuzugreifen, musst du die Liste vom Kopf aus durchlaufen. Es gibt keinen Index.
Effizientes Einfügen und Löschen (O(1) an bekannter Position): Wenn du bereits einen Zeiger auf den Vorgängerknoten hast, kannst du ein neues Element in konstanter Zeit einfügen oder löschen – ohne Verschieben.
Zusätzlicher Speicher für Zeiger: Jeder Knoten benötigt Platz für einen oder zwei Zeiger, was den Speicherverbrauch erhöht.

Typische Anwendungen: Verkettete Listen kommen zum Einsatz, wenn du viele Einfüge- und Löschoperationen hast, z. B. in Texteditoren (Undo-Funktion), in Warteschlangen (Queue) oder in Hash-Tabellen zur Kollisionsbehandlung (Chaining). Auch in Betriebssystemen werden sie für die Verwaltung von Speicherblöcken genutzt.

Lineare Liste vs. verkettete Liste – ein direkter Vergleich

Für deine Algorithmen-Kenntnisse ist es entscheidend, die Unterschiede zu verstehen. Hier eine Gegenüberstellung:

Zugriffszeit: Array O(1) – verkettete Liste O(n).
Einfügen/ Löschen am Ende: Array amortisiert O(1) (wenn Platz) – verkettete Liste O(1) (mit Tail-Zeiger).
Einfügen/ Löschen in der Mitte: Array O(n) – verkettete Liste O(1) nach Positionierung.
Speicher: Array kompakt – verkettete Liste fragmentiert mit Zeiger-Overhead.
Größenänderung: Array aufwändig (Kopie) – verkettete Liste trivial.

Die Wahl hängt immer von deinem Anwendungsfall ab: Brauchst du schnellen Zugriff? Nimm ein Array. Musst du oft Elemente einfügen oder löschen? Dann ist eine verkettete Liste besser geeignet.

Wie eine Visualisierungsplattform dein Lernen revolutioniert

Viele Lernende haben anfangs Schwierigkeiten, sich die abstrakten Konzepte hinter Zeigern und Speicherlayout vorzustellen. Eine Datenstruktur-Visualisierungsplattform macht genau diese Prozesse sichtbar. Statt nur Code zu lesen, siehst du live, wie Knoten verknüpft werden, wie Zeiger springen und wie sich Listen verändern. Das ist besonders hilfreich für visuelle Lerntypen.

Funktionen einer guten Visualisierungsplattform:

Schritt-für-Schritt-Animation: Du kannst Algorithmen wie das Einfügen eines Knotens an einer bestimmten Position in Zeitlupe verfolgen. Jeder Schritt wird farblich hervorgehoben.
Interaktive Steuerung: Du kannst selbst Daten eingeben, Knoten hinzufügen oder löschen und siehst sofort die Auswirkungen auf die Struktur.
Code-Synchronisation: Neben der Visualisierung wird der entsprechende Code (z. B. in Python oder Java) angezeigt. So verstehst du, wie die Theorie im Code umgesetzt wird.
Vergleichsansicht: Du kannst Array und verkettete Liste nebeneinander darstellen und die Unterschiede bei Einfügeoperationen direkt beobachten.
Fehleranalyse: Wenn du einen falschen Zeiger setzt, zeigt die Plattform, warum die Liste zyklisch wird oder ein Element verloren geht.

Stell dir vor, du lernst, wie man eine doppelt verkettete Liste rückwärts durchläuft. In der Visualisierung siehst du die Zeiger von rechts nach links wandern – das verankert das Verständnis tiefer als tausend Worte.

Praktische Anwendungsszenarien für verkettete Listen

Um das Gelernte zu festigen, hier drei konkrete Beispiele aus der Praxis:

Musikplayer (Playlist): Eine Playlist ist oft als doppelt verkettete Liste realisiert. Du kannst zum nächsten oder vorherigen Lied springen, und das Einfügen eines neuen Songs an beliebiger Stelle ist effizient.
Undo-Funktion in Editoren: Jeder Zustand des Dokuments wird als Knoten gespeichert. Mit einer verketteten Liste kannst du rückgängig (undo) und wiederherstellen (redo) – das ist genau das Prinzip einer doppelt verketteten Liste.
Speicherverwaltung in Betriebssystemen: Freie Speicherblöcke werden häufig in einer verketteten Liste (Free List) verwaltet, um Speicheranfragen schnell zu bedienen.

Diese Beispiele zeigen dir, dass verkettete Listen keine theoretischen Konstrukte sind, sondern täglich in Software verwendet werden.

Häufige Fehler und wie du sie mit Visualisierung vermeidest

Anfänger machen oft typische Fehler: Sie verlieren den Kopf der Liste, vergessen, den Zeiger des letzten Knotens auf null zu setzen, oder erzeugen unbeabsichtigt eine zyklische Liste. Eine Visualisierungsplattform kann dich hier gezielt unterstützen:

Live-Überwachung: Du siehst sofort, wenn ein Zeiger ins Leere zeigt oder ein Knoten nicht erreichbar ist.
Schrittweises Debugging: Du kannst deinen eigenen Code in der Plattform ausführen und beobachten, wie sich die Liste bei jedem Befehl verändert.
Übungsaufgaben: Viele Plattformen bieten Aufgaben wie „Füge einen Knoten nach dem dritten Element ein“ oder „Lösche den Knoten mit dem Wert 5“. Du bekommst sofort Rückmeldung, ob deine Lösung korrekt ist.

So entwickelst du ein sicheres Verständnis für Zeigeroperationen, ohne Frustration durch unsichtbare Fehler.

Wie du die Plattform optimal nutzt – ein Leitfaden für Lernende

Um das Beste aus einer Visualisierungsplattform herauszuholen, empfehlen wir dir diese Schritt-für-Schritt-Strategie:

Grundlagen verstehen: Lies zuerst die Theorie zu linearen und verketteten Listen (wie in diesem Artikel).
Visualisierung starten: Öffne die Plattform und wähle die Datenstruktur „Verkettete Liste“ aus. Starte eine Demo, um einen ersten Eindruck zu bekommen.
Selbst experimentieren: Erstelle deine eigene Liste mit 5 Knoten. Füge Knoten am Anfang, in der Mitte und am Ende hinzu. Beobachte die Zeigeränderungen.
Code parallel lesen: Zeige den Code an und versuche, die Visualisierung mit den Codezeilen zu verknüpfen. Frage dich: „Welche Zeile bewirkt, dass der Zeiger jetzt umspringt?“
Übungsaufgaben lösen: Nutze die eingebauten Aufgaben. Versuche, sie erst selbst zu lösen, und lass dir dann die Lösung visualisieren.
Komplexe Algorithmen: Wenn du dich sicher fühlst, visualisiere Algorithmen wie das Umkehren einer Liste oder das Erkennen von Zyklen (Floyd's Algorithm).

Diese Methode stellt sicher, dass du nicht nur auswendig lernst, sondern ein echtes, intuitives Verständnis entwickelst.

Warum dieses Wissen für deine Karriere als Entwickler wichtig ist

Datenstrukturen und Algorithmen sind das Herzstück von technischen Interviews bei Top-Unternehmen wie Google, Amazon oder Facebook. Die Fähigkeit, zwischen Array und verketteter Liste zu wählen und die Vor- und Nachteile zu argumentieren, wird oft geprüft. Darüber hinaus hilft dir das Verständnis von Zeigern und Speicherverwaltung dabei, effizienteren Code zu schreiben und Speicherlecks zu vermeiden. Eine Visualisierungsplattform gibt dir hier einen entscheidenden Vorteil, weil du die Konzepte nicht nur abstrakt lernst, sondern sie „in Aktion“ siehst.

Fazit: Starte noch heute mit der Visualisierung

Lineare Listen und verkettete Listen sind die ersten wichtigen Meilensteine auf deinem Weg zum Algorithmen-Profi. Mit einer guten Visualisierungsplattform kannst du diese Konzepte schnell und nachhaltig lernen. Du wirst sehen, wie Zeiger tanzen, Knoten sich verketten und Listen sich dynamisch verändern. Das macht nicht nur Spaß, sondern vertieft dein Verständnis auf eine Weise, die reines Textbuchlernen nicht bieten kann. Probiere es aus: Suche dir eine Plattform, erstelle deine erste verkettete Liste und beobachte, wie die Elemente ihre Verbindungen knüpfen. Dein zukünftiges Ich – und deine Interviewer – werden es dir danken!

```

为什么要使用头插法创建，而不是尾插法创建？
如果我们要在链表末尾进行插入，那么需要先遍历整个链表找到尾结点，或者使用一个变量记录尾结点的。
而且每次都需要改变尾结点的next指向头结点，以达到循环。
而我们使用头插法，无论链表是否为空，代码都是统一不变，不需要做其他判断。

按位序删除结点

删除操作和普通单链表相同。主要区别在于我们需要确保删除后链表保持循环。

要从循环链表中删除特定的结点，首先需要检查删除的位序是否满足条件。
找到待删除结点的前驱结点即p结点
找到前驱结点p后，使用q记录为待删除结点
修改前驱结点p的next指向待删除结点q的next，即跳过q结点并将其删除

仅有一个结点时，循环指向头结点

删除尾部结点，更新链表循环

删除中间结点

💡 提示
对于带头结点的链表，上面三种情况都可以统一为同一种操作代码

按位序删除结点 | 可视化完整可视化