Durchlaufen einer Liste in C++

1. Liste in C++
2. Durchlaufen einer Liste in C++

Dieses kurze Programmier-Tutorial behandelt eine weit verbreitete Datenstruktur in C++, nämlich List. In der C++ Standard Template Library (STL) steht für diese Datenstruktur eine Klasse List zur Verfügung.

Es ist ein Bündel von Funktionen enthalten, mit denen mehrere Operationen auf der Liste ausgeführt werden können. Später in diesem Artikel werden wir erörtern, wie wir die Liste durchlaufen und eine Liste anzeigen oder bearbeiten können.

Liste in C++

Liste oder verknüpfte Liste ist eine lineare Datenstruktur, die als Datencontainer dienen und die Daten im Speicher speichern kann. Im Gegensatz zu Vektoren und Arrays werden Daten in der Liste nicht an zusammenhängenden Speicherorten gespeichert.

Stattdessen werden Daten an zufälligen Speicherorten gespeichert. Jedes in die Liste eingefügte Element wird als Knoten bezeichnet.

Jeder Knoten in einer Liste enthält einen Zeiger, der auf das nächste Element der Liste zeigt. Aus diesem Grund werden Elemente der Liste nicht an zusammenhängenden Stellen gespeichert; daher wird sie auch als verkettete Liste bezeichnet.

Listen können in zwei Typen eingeteilt werden:

1. Einfach verkettete Liste
2. Doppelt verkettete Liste

Einfach verkettete Liste

Bei dieser Art von Verbindungsliste haben alle Knoten 2 Teile, einen für Daten und einen zum Speichern des Zeigers, der auf den nächsten Knoten zeigt. Der zweite Teil speichert die Adresse des nächsten Knotens der Liste.

Doppelt verkettete Liste

Bei dieser Art von Linkliste haben alle Knoten 3 Teile, der erste Teil ist für den Zeiger auf den vorherigen Knoten, der zweite für die Speicherung von Daten und der dritte enthält den Zeiger, der auf das nächste Element der Liste verweist.

Die Klasse List in STL enthält eine doppelt verkettete Liste. Wie bei Arrays dauert das Einfügen und Löschen in diesem Listentyp linear.

Listen benötigen jedoch keine ansteckenden Gedächtnisblöcke. Darüber hinaus ist das Erweitern einer Liste durch Anhängen jeweils eines einzelnen Listenknotens einfacher und rationeller als die Neuzuweisung des gesamten dynamischen Arrays (wie dies von den Vektoren getan wird).

Daher wird es als eine flexiblere Datenstruktur angesehen als andere Datenstrukturen wie Arrays und Vektoren.

Eine andere Datenstruktur, forward_list, kann nur in eine Richtung iterieren und ist eine einfach verknüpfte Liste. Im Vergleich zu anderen Datenstrukturen besteht der große Nachteil von Listen und Vorwärtslisten darin, dass wir nicht direkt auf jedes Listenelement zugreifen können, indem wir seine Position wie in Arrays angeben.

Um beispielsweise auf das 5. Element in einer Liste zuzugreifen, muss man an einem Endpunkt beginnen, entweder am Anfang oder am Ende dieser Position, und es dauert linear. Listen verwenden auch zusätzlichen RAM, um die Verbindungsinformationen für jedes Element zu speichern.

Durchlaufen einer Liste in C++

Wir können die Klasse iterator der Standard Template Library C++ verwenden, um die Listenelemente zu durchlaufen. Die Syntax dafür lautet wie folgt:

std::list<int>::iterator itr;

Es gibt verschiedene Methoden zur Iteration in der Liste:

Schauen wir uns den folgenden Code an, der verschiedene Funktionen der Listenklasse verwendet.

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

void displaylist(list<int> l)  // print function to show list
{
  list<int>::iterator myitr;
  for (myitr = l.begin(); myitr != l.end(); ++myitr) cout << "  " << *myitr;
  cout << endl;
}
int main() {
  list<int> mylist1;
  for (int a = 0; a < 10; ++a) {
    int r = 1 + (rand() % 50);
    mylist1.push_back(r);
  }
  cout << "\nData of List 1 : ";
  displaylist(mylist1);
  cout << "\nList first element : " << mylist1.front();
  cout << "\nAfter we pop first element: ";
  mylist1.pop_front();
  displaylist(mylist1);

  cout << "\nWhen we sort the list: ";
  mylist1.sort();
  displaylist(mylist1);

  return 0;
}

Ausgabe:

Data of List 1 :   34  37  28  16  44  36  37  43  50  22

List first element : 34
After we pop first element:   37  28  16  44  36  37  43  50  22

When we sort the list:   16  22  28  36  37  37  43  44  50