Lista_naprzód kontener zapewnia implementację pojedynczo połączona lista struktura danych. Przechowuje dane w pamięci nieciągłej, gdzie każdy element wskazuje na następny element w sekwencji. Dzięki temu wstawianie i usuwanie jest szybsze, gdy znane jest położenie elementu.

Składnia

Lista przesyłania dalej jest zdefiniowana jako std::forward_list szablon klasy wewnątrz< lista_do przodu > plik nagłówkowy.

lista_do przodufl;

Gdzie

• T: Typ danych elementów na liście przesyłania dalej.
• F: Nazwa przypisana do listy przesyłania dalej.

Deklaracja i inicjalizacja

Listę forward_list można zadeklarować i zainicjować na kilka sposobów, jak pokazano w poniższym przykładzie:

#include    using namespace std; void printFL(forward_list<int>& fl) {  for (auto i : fl)  cout << i << ' ';  cout << 'n'; } int main() {    // Creating an empty forward_list  forward_list<int> fl1;  // Creating a forward_list with  // default value  forward_list<int> fl2(3 4);    // Creating a forward_list from an  // initializer list  forward_list<int> fl3 = {1 5 3 4};    printFL(fl2);  printFL(fl3);  return 0; } 

4 4 4 1 5 3 4 

Przykład: W powyższym programie mamy prostą inicjalizację listy forward na trzy sposoby:

• Oświadczenie lista_do przodu FL1 tworzy pustą listę liczb całkowitych do przodu.
• Oświadczenie lista_do przodu fl2(34) tworzy listę forward o rozmiarze 3, w której każdy element ma wartość 4.
• Oświadczenie lista_do przodu fl3 = {1 5 3 4} tworzy listę forward i inicjuje elementy z listy inicjatorów.

Podstawowe operacje

Oto podstawowe operacje, które możemy wykonać na liście forward:

1. Dostęp do elementów

Do elementów listy przesyłania dalej nie można uzyskać dostępu za pomocą indeksów, takich jak tablice lub wektory. Aby uzyskać do niej dostęp, musimy sekwencyjnie przeglądać listę od początku do żądanej pozycji. Można to osiągnąć poprzez inkrementację zaczynać() iterator, ale lepiej go użyć Następny() Lub osiągnięcie() funkcjonować.

Dostęp do pierwszego elementu listy można jednak łatwo uzyskać za pomocą przód() metoda.

Przykład:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Access the first element  cout << fl.front() << endl;    // Access third element  auto it = next(fl.begin() 2);  cout << *it;  return 0; } 

1 3

Przykład: W powyższym programie pierwszy element jest drukowany za pomocą przód() metoda. Aby uzyskać dostęp do trzeciego elementu Następny() służy do przesuwania iteratora o dwie pozycje od początku i *To służy do dereferencji iteratora.

2. Wstawianie elementów

Elementy można wstawiać na listę przesyłania za pomocą wstaw_po() funkcjonować. Wymaga iteratora, po którym element ma zostać wstawiony. Jednak szybkie wkładanie z przodu jest obsługiwane przez push_front() metoda.

Przykład:

#include    using namespace std; int main() {  forward_list<int> fl = {5 4};  // Inserting Element at front  fl.push_front(1);    // Insert 3 after the second element  auto it = fl.begin();  advance(it 1);  fl.insert_after(it 3);    for (auto x: fl) cout << x << ' ';  return 0; } 

1 5 3 4 

Wyjaśnienie: W tym programie pierwszy element listy forward_list jest wstawiany z przodu za pomocą push_front() funkcjonować. Następnie tworzony jest iterator i przesuwany o jedną pozycję do przodu za pomocą metody osiągnięcie() funkcjonować. Potem element 5 jest wstawiany po drugim elemencie za pomocą wstaw_po() funkcjonować.

3. Aktualizacja elementów

Wartość istniejących elementów można zmienić po prostu uzyskując do nich dostęp i używając operator przypisania aby przypisać nową wartość.

Przykład:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Updating first element  fl.front() = 111;  cout << fl.front() << endl;    // Updating third element  auto it = next(fl.begin() 2);  *it = 333;  cout << *it;  return 0; } 

111 333

4. Znalezienie elementu

Lista forward nie udostępnia żadnej funkcji członkowskiej umożliwiającej wyszukiwanie elementu, ale możemy jej użyć znajdować() algorytm znajdowania dowolnej wartości.

Przykład :

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Finding 3  auto it = find(fl.begin() fl.end() 3);    if (it != fl.end()) cout << *it;  else cout << 'Element not Found';  return 0; } 

3

5. Przemierzanie

Listę przesyłania dalej można przeglądać za pomocą zaczynać() I koniec() iteratory z pętlą, ale możemy poruszać się tylko do przodu, a nie do tyłu.

Przykład:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};    // Traversing using range-based for loop  for(auto i : fl)  cout << i << ' ';  cout << endl;    return 0; } 

1 5 3 4 

6. Usuwanie elementów

Na liście forward możemy usunąć element na danej pozycji za pomocą usuń_po() metoda. Ta metoda przenosi iterator na jedną pozycję przed elementem docelowym. Szybkie usuwanie od przodu możliwe jest za pomocą pop_front() metoda.

Przykład:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Delete first element  fl.pop_front();    // Delete third element  auto it = fl.begin();  advance(it 1);  fl.erase_after(it);    for (auto x: fl) cout << x << ' ';  return 0; } 

5 3 

7. Rozmiar listy przesyłania

forward_list nie ma wbudowanej funkcji size(). Aby określić jego rozmiar musimy ręcznie policzyć elementy, przechodząc przez niego pętlą lub używając std:: Distance.

#include    #include  #include    using namespace std; int main() {  forward_list<int> flist={10203040};  //Calculate size by counting elements using std:: distance  int size=distance(flist.begin()flist.end());  cout<<'Size of forward_list: '<<size<<endl;  return 0; } 

Size of forward_list: 4 

8. pusty()

Służy do sprawdzania, czy lista forward_list jest pusta.
Zwraca true jeśli lista jest pusta i false w przeciwnym razie pozwala na szybkie sprawdzenie czy kontener nie zawiera danych.

#include    #include  using namespace std; int main() {  forward_list<int> flist;  if (flist.empty()) {  cout << 'The forward_list is empty.' << endl;  }  flist.push_front(10);  if (!flist.empty()) {  cout << 'The forward_list is not empty.' << endl;  }  return 0; } 

The forward_list is empty. The forward_list is not empty. 

Złożoność czasu

Poniższa tabela przedstawia złożoność czasową powyższych operacji na liście forwardów:

mapy Javy

Lista dalej kontra lista