Algorytmy i Struktury Danych - Operacje na listach jednokierunkowych

Przechodzenie listy – ma na celu przejście kolejno przez wszystkie elementy listy, począwszy od pierwszego, a skończywszy na ostatnim. Operacja ta jest częścią składową wielu innych operacji, gdzie algorytm musi coś wyszukać na liście. W przypadku listy jednokierunkowej możemy się po niej poruszać tylko w jednym kierunku: od początku do końca. Z uwagi na sposób powiązania ze sobą elementów listy, do jej przechodzenia potrzebna jest zmienna typu wskaźnik, która będzie wskazywała na kolejne elementy. Na początku algorytmu zmienna ta powinna wskazywać pierwszy element na liście. W pętli przetwarzamy element wskazywany przez tą zmienną, po czym za nową wartość zmiennej przyjmuje się adres następnego elementu listy. Adres ten jest przechowywany w polu next elementu bieżącego. Listę przechodzimy do momentu, aż zmienna wskazująca przyjmie wartość 0. Stanie się tak po wyjściu z ostatniego elementu listy, w którego polu next przechowywany jest adres 0.

Algorytm przechodzenia przez listę jednokierunkową

Wejście:

p : wskazanie początku listy jednokierunkowej, czyli adres pierwszego elementu na liście

Wyjście:

Przejście przez wszystkie elementy listy

Lista kroków:

K01: Dopóki p ≠ nil, ; w pętli przechodzimy przez
     wykonuj kroki K02…K03 ; kolejne elementy listy
K02:   Przetwarzaj element wskazywany przez p
K03:   p ← p→next ; w p umieść zawartość pola next
       ; elementu wskazywanego przez p
K04: Zakończ

Pascal

while p <> nil do
begin
  …
  p := p^.next;
end;

C++

while(p)
{
  …
  p = p->next;
}

Basic

While p
  …
  p = p->next
Wend

Python (dodatek)

while p:
    …
    p = p.next

Na początek: podrozdziału strony

Problem liczby elementów listy rozwiązujemy za pomocą algorytmu przejścia przez listę. Tworzymy licznik, któremu na początku nadajemy wartość 0. Następnie przechodzimy kolejno przez wszystkie elementy na liście. Przy każdym mijanym elemencie zwiększamy licznik o 1. Po przejściu całej listy w liczniku będzie liczba elementów.

Algorytm wyznaczania liczby elementów na liście jednokierunkowej

Wejście:

p : wskazanie listy jednokierunkowej

Wyjście:

c : liczba elementów; c ∈ C.

Lista kroków:

K01: c ← 0 ; zeruj licznik
K02: Dopóki p ≠ nil, ; w pętli przechodzimy przez
     wykonuj kroki K03…K04 ; kolejne elementy listy
K03:   c ← c+1 ; zwiększ licznik
K04:   p ← p→next ; w p umieść zawartość pola next
       ; elementu wskazywanego przez p
K05: Zakończ z wynikiem c ; koniec, wynik w c

Pascal

function l_len(p : PSLel) : cardinal;
var
  c : cardinal;
begin
  c := 0; // zerujemy licznik

  while p <> nil do
  begin
    inc(c); // zwiększamy licznik o 1
    p := p^.next; // następny element
  end;

  l_len := c;
end;

C++

unsigned l_len(SLel * p)
{
  unsigned c = 0; // zerujemy licznik

  while(p)
  {
    c++; // zwiększamy licznik o 1
    p = p->next; // następny element
  }

  return c;
}

Basic

Function l_len(p As SLel Ptr) _
               As UInteger

  Dim c As UInteger

  c = 0 ' zerujemy licznik

  While p
    c += 1 ' zwiększamy licznik o 1
    p = p->next ' następny element
  Wend

  l_len = c
End Function

Python (dodatek)

# klasa elementu listy jednokierunkowej
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
class SLvar:


    def __init__(self):
        self.head = None


    def l_len(self):
        c = 0
        p = self.head
        while p:
            c += 1
            p = p.next
        return c

Na początek: podrozdziału strony

Załóżmy, iż mamy daną listę trójelementową. Naszym zadaniem jest dodanie nowego elementu na początku tej listy. Postępujemy wg następującego schematu:

Tworzymy dynamicznie w pamięci nowy element listy (na rysunku w kolorze zielonym). Wprowadzamy do niego dane dla pola data.

W polu next nowego elementu umieszczamy adres przechowywany przez zmienną head. W ten sposób następnikiem nowego elementu stanie się obecny pierwszy element listy.

W zmiennej head umieszczamy adres nowego elementu. Po tej operacji początkiem listy staje się nowo utworzony element. Reszta elementów listy znajduje się za nowowprowadzonym elementem. Zwróć uwagę, iż elementy listy nie muszą być przesuwane jak w przypadku tablic. Jest to dużą zaletą list. Operacja dołączania nowego elementu wykonywana jest w czasie stałym, zatem jej złożoność obliczeniowa ma klasę O(1).

Algorytm dołączania nowego elementu na początek listy jednokierunkowej

Wejście:

head : zmienna wskazująca początek listy.
v : wartość wprowadzana do elementu.

Wyjście:

Lista z dołączonym na początku elementem o wartości v.

Dane pomocnicze:

p : wskazanie elementu listy.

Lista kroków:

K01: p ← nowy element ; tworzymy nowy element listy
     ; i jego adres umieszczany w p
K02: p→data ← v ; umieszczamy dane w elemencie
K03: p→next ← head ; następnikiem będzie bieżący
     ; pierwszy element listy
K04: head ← p ; ustawiamy początek listy
     ; na nowy element
K05: Zakończ

Uwaga:

Elementy są umieszczone na liście w kierunku odwrotnym do kolejności ich wstawiania – ostatnio wstawiony element jest pierwszym elementem listy. Taka struktura pozwala prosto realizować stos.

Pascal

procedure l_push_front(var head : PSLel;
                       v : char);
var
  p : PSLel;
begin
  new(p); // tworzymy nowy element
  p^.data := v; // inicjujemy element
  p^.next := head;
  head := p;
end;

C++

void l_push_front(SLel * & head, 
char v)
{
  SLel * p = new SLel;

  p->data = v; // inicjujemy element
  p->next = head;
  head = p;
}

Basic

Sub l_push_front(ByRef head As SLel Ptr, _
                 v As String)
  Dim p As SLel Ptr

  p = new SLel ' tworzymy nowy element
  p->data = v ' inicjujemy element
  p->next = head
  head = p
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p

Na początek: podrozdziału strony

Jeśli lista jest pusta, to nic nie robimy. Załóżmy, że mamy daną listę, z której początku należy usunąć element zaznaczony na rysunku kolorem czerwonym.

W zmiennej head umieszczamy zawartość pola next usuwanego elementu. W ten sposób początek listy rozpocznie się w następniku, a usuwany element zostanie wyłączony z listy.

Odłączony element usuwamy z pamięci.

Otrzymujemy listę bez pierwszego elementu.

Algorytm usuwania elementu z początku listy jednokierunkowej

Wejście:

head : zmienna wskazująca początek listy.

Wyjście:

Lista bez pierwszego elementu.

Dane pomocnicze:

p : wskazanie elementu listy.

Lista kroków:

K01: p ← head ; zapamiętaj pierwszy element
K02: Jeśli p = nil, ; zakończ, jeśli lista jest pusta
     to zakończ
K03: head ← p→next ; początkiem listy będzie
     ; element następny
K04: Usuń z pamięci element wskazany przez p
K05: Zakończ

Pascal

procedure l_pop_front(var head : PSLel);
var
  p : PSLel;
begin
  p := head; // zapamiętujemy początek
  if p <> nil then
  begin
    head := p^.next; // nowy początek
    dispose(p); // usuń element z pamięci
  end;
end;

C++

void l_pop_front(SLel * & head)
{
  SLel * p;
  p = head; // zapamiętujemy początek
  if(p)
  {
    head = p->next; // nowy początek
    delete p; // usuń element z pamięci
  }
}

Basic

Sub l_pop_front(ByRef head As SLel Ptr)

  Dim p As SLel Ptr

  p = head ' zapamiętujemy początek
  If p Then
    head = p->next ' nowy początek
    Delete p ' usuń element z pamięci
  End If
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None

Dla prostych zastosowań podane powyżej operacje dla list jednokierunkowych zwykle wystarczają. W dalszej części artykułu rozszerzamy tę listę o kolejne operacje.

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Poniższy program implementuje listę jednokierunkową. Elementy tej listy będą przechowywały znaki. Najpierw umieszczamy na liście kolejno litery A, B i C, następnie usuwamy z początku listy dwa elementy. Za każdym razem zawartość listy jest wyświetlana.

Pascal

// Program testowy dla list jednokierunkowych
// Data: 11.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------

program slist_test1;

// Typ elementów listy
//--------------------
type
  PSLel = ^SLel;

  SLel = record
    next  : PSLel;
    data  : char;
  end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function l_len(p : PSLel) : cardinal;
var
  c : cardinal;
begin
  c := 0;
  while p <> nil do
  begin
    inc(c);
    p := p^.next;
  end;
  l_len := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure l_print(p : PSLel);
var
  i : cardinal;
begin
  writeln('Number of elements : ', l_len(p));
  i := 1;
  while p <> nil do
  begin
    writeln('Element #', i, '  data = ', p^.data);
    inc(i);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure l_push_front(var head : PSLel;
                           v : char);
var
  p : PSLel;
begin
  new(p);
  p^.data := v;
  p^.next := head;
  head := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure l_pop_front(var head : PSLel);
var
  p : PSLel;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  L : PSLel; // adres początku listy

begin
  L := nil;
  l_push_front(L, 'A');
  l_push_front(L, 'B');
  l_push_front(L, 'C');
  l_print(L);
  l_pop_front(L);
  l_pop_front(L);
  l_print(L);
end.

C++

// Program testowy dla list jednokierunkowych
// Data: 11.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typ elementów listy
//--------------------
struct SLel
{
  SLel * next;
  char data;
};

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned l_len(SLel * p)
{
  unsigned c = 0;

  while(p)
  {
    c++;
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość elementów
//----------------------------------------
void l_print(SLel * p)
{
  unsigned i;

  cout << "Number of elements : "
       << l_len(p) << endl;

  for(i = 1; p; p = p->next)
    cout << "Element #" << i++
         << "  data = " << p->data
         << endl;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void l_push_front(SLel * & head, char v)
{
  SLel * p;

  p = new SLel;
  p->data = v;
  p->next = head;
  head = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void l_pop_front(SLel * & head)
{
  SLel * p = head;

  if(p)
  {
    head = p->next;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  SLel * L = NULL;

  l_push_front(L, 'A');
  l_push_front(L, 'B');
  l_push_front(L, 'C');
  l_print(L);
  l_pop_front(L);
  l_pop_front(L);
  l_print(L);

  return 0;
}

Basic

' Program testowy dla list jednokierunkowych
' Data: 11.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------

' Typ elementów listy
'--------------------
Type SLel
  next As SLel Ptr
  data As String * 1
End Type

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function l_len(p As SLel Ptr) As UInteger
  Dim c As UInteger

  c = 0
  While p
    c += 1
    p = p->next
  Wend
  l_len = c
End Function

' Procedura wyświetla zawartość listy
'-----------------------------------
Sub l_print(p As SLel Ptr)
  Dim i As UInteger
  
  Print "Number of elements : ";l_len (p)
  i = 1
  While p
    Print "Element #";i;"  data = ";p->data
    i += 1
    p = p->next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub l_push_front(ByRef head As SLel Ptr, _
                       v As String)
  Dim p As SLel Ptr

  p = new SLel
  p->data = v
  p->next = head
  Head = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub l_pop_front(ByRef head As SLel Ptr)
  Dim p As SLel Ptr

  p = head
  If p Then
    head = p->next
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim L As SLel Ptr

L = 0

l_push_front(L, "A")
l_push_front(L, "B")
l_push_front(L, "C")
l_print(L)

l_pop_front(L)
l_pop_front(L)
l_print(L)
End

Wynik:

Number of elements : 3
Element #1 data = C
Element #2 data = B
Element #3 data = A

Number of elements : 1
Element #1 data = A

Python (dodatek)

# Program testowy dla list jednokierunkowych
# Data: 1.05.2024
# (C)2024 mgr Jerzy Wałaszek
# -------------------------------------------


# klasa elementu listy
# ---------------------
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
# -----------------------------
class SLvar:


    # Konstruktor
    def __init__(self):
        self.head = None


    # liczba elementów
    def l_len(self):
        c = 0
        p = self.head
        while p:
            c += 1
            p = p.next
        return c


    # wstawianie na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    # usuwanie z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next


    # wyświetlenie listy
    def l_print(self):
        print("Liczba elementów :", self.l_len())
        i = 1
        p = self.head
        while p:
            print("Element nr", i, "dane =", p.data)
            i += 1
            p = p.next
        print()


    # destruktor
    def __del__(self):
        while self.head:
            self.l_pop_front()
        print("Lista usunięta z pamięci")


# ---------------
# Program główny
# ---------------

sl = SLvar()  # lista jednokierunkowa
sl.l_push_front('A')
sl.l_push_front('B')
sl.l_push_front('C')
sl.l_print()
sl.l_pop_front()
sl.l_pop_front()
sl.l_print()
sl = None

Wynik:

Liczba elementów : 3
Element nr 1 dane = C
Element nr 2 dane = B
Element nr 3 dane = A

Liczba elementów : 1
Element nr 1 dane = A

Lista usunięta z pamięci

Na początek: podrozdziału strony

Tworzymy nowy element. W polu next umieszczamy adres zero – ostatni element listy nie posiada następnika.

Jeśli lista jest pusta, to head zawiera adres zero. W takim przypadku adres nowego elementu umieszczamy w zmiennej head. Nowy element staje się jednocześnie pierwszym i ostatnim elementem listy.

Jeśli lista zawiera elementy, to przechodzimy do ostatniego z nich (za pomocą podanego wcześniej algorytmu przejścia listy).

W polu next ostatniego elementu umieszczamy adres nowego elementu. W ten sposób nowy element staje się częścią listy i jest umieszczony na jej końcu.

Lista zostaje wydłużona o nowy element.

Algorytm dołączania nowego elementu do końca listy jednokierunkowej

Wejście:

head : zmienna wskazująca początek listy.
v : wartość umieszczana w elemencie listy.

Wyjście:

Lista z dołączonym na końcu nowym elementem o wartości v.

Dane pomocnicze:

p, e : wskazania elementu listy.

Lista kroków:

K01: p ← nowy element ; tworzymy nowy element listy
     ; i jego adres umieszczany w p
K02: e→next ← nil ; inicjujemy pola nowego elementu
K03: e→data ← v
K04: p ← head ; w p ustawiamy początek listy
K06: Jeśli p ≠ nil, ; czy lista jest pusta?
     to idź do kroku K09
K06: head ← e ; jeśli tak, to nowy element będzie
     ; pierwszym elementem listy
K07: Zakończ
K08: Dopóki p→next ≠ nil, ; inaczej przechodzimy
     wykonuj p ← p→next   ; do ostatniego elementu listy
K09: p→next ← e ; dołączamy nowy element
     ; za ostatnim na liście
K10: Zakończ

Pascal

procedure l_push_back(var head : PSLel;
                          v : char);
var
  p, e : PSLel;
begin
  new(e); // tworzymy nowy element
  e^.next := nil; // inicjujemy element
  e^.data := v;
  p := head;
  if p = nil then
    head := e
  else
  begin
    while p^.next <> nil do
      p := p^.next;
    p^.next := e;
  end;
end;

C++

void l_push_back(SLel * & head, char v)
{
  SLel * p, * e;

  e = new SLel; // tworzymy nowy element
  e->next = NULL; // inicjujemy element
  e->data = v;
  p = head;
  if(p)
  {
     while(p->next)
       p = p->next;
     p->next = e;
  }
  else
    head = e;
}

Basic

Sub l_push_back(ByRef head As SLel Ptr, _
                      v As String)
  Dim As SLel Ptr p, e

  e = New SLel ' tworzymy nowy element
  e->next = 0 ' inicjujemy element
  e->data = v
  p = head
  If p = 0 Then
    head = e
  Else
    While p->next
      p = p->next
    Wend
    p->next = e
  End If
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_push_back(self, v):
        e = SLel(v)
        p = self.head
        if p:
            while p.next:
                p = p.next
            p.next = e
        else:
            self.head = e

Na początek: podrozdziału strony

Jeśli lista jest pusta, nic nie robimy. W przeciwnym razie sprawdzamy, czy lista zawiera tylko jeden element. Rozpoznamy to po tym, iż pole next pierwszego elementu zawiera adres zero.

Jeśli tak, to w zmiennej head umieszczamy adres zero. Spowoduje to odłączenie elementu od listy (oczywiście adres tego elementu musimy wcześniej zapamiętać, gdyż inaczej stracimy do niego dostęp!), a lista staje się pusta.

Odłączony element usuwamy z pamięci i kończymy.

Jeśli lista nie jest pusta, to naszym zadaniem staje się usunięcie ostatniego jej elementu, który zaznaczyliśmy na rysunku kolorem czerwonym. Przechodzimy na liście do przedostatniego elementu – przedostatni element rozpoznamy po tym, iż pole next jego następnika zawiera adres zero.

Usuwamy z pamięci element wskazywany przez pole next przedostatniego elementu listy.

W polu next elementu przedostatniego (który teraz staje się elementem ostatnim listy) umieszczamy adres zero. W ten sposób lista staje się krótsza o jeden element.

Algorytm usuwania elementu z końca listy jednokierunkowej

Wejście:

head : zmienna wskazująca początek listy.

Wyjście:

Lista z usuniętym ostatnim elementem.

Dane pomocnicze:

p : wskazania elementu listy.

Lista kroków:

K01: p ← head ; pobieramy do p adres początku listy
K02: Jeśli p = nil, ; jeśli lista jest pusta, kończymy
     to zakończ
K03: Jeśli p→next ≠ nil, ; sprawdzamy, czy lista
     to idź do kroku K07 ; jest jednoelementowa
K04: Usuń z pamięci element wskazywany przez p
K05; head ← nil ; lista jednoelementowa staje się
     ; listą pustą
K06: Zakończ
K07: Dopóki p→next→next ≠ nil, ; idziemy do
     wykonuj p ← p→next ; przedostatniego elementu
K08: Usuń z pamięci element ; usuwamy następny element, 
     wskazywany przez p→next ; czyli ostatni
K09: p→next ← nil ; przedostatni element nie ma
     ; już następnika
K10: Zakończ

Pascal

procedure l_pop_back(var head : PSLel);
var
  p : PSLel;
begin
  p := head;
  if p <> nil then
  begin
    if p^.next <> nil then
    begin
      while p^.next^.next <> nil do
        p := p^.next;
      dispose(p^.next);
      p^.next := nil;
    end
    else
    begin
      dispose(p); // lista jednoelementowa
      head := nil; // staje się listą pustą
    end
  end;
end;

C++

void l_pop_back(SLel * & head)
{
  SLel * p = head;
  if(p)
  {
    if(p->next)
    {
      while(p->next->next)
        p = p->next;
      delete p->next;
      p->next = NULL;
    }
    else
    {
      delete p; // lista jednoelementowa
      head = NULL; // staje się listą pustą
    }
  }
}

Basic

Sub l_pop_back(ByRef head As SLel Ptr)
  Dim p As SLel Ptr

  p = head
  If p Then
    If p->next Then
      While p->next->next
        p = p->next
      Wend
      Delete p->next
      p->next = 0
    Else
      Delete p
      head = 0
    End If
  End If
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_pop_back(self):
        p = self.head
        if p:
            if p.next:
                while p.next.next:
                    p = p.next
                p.next = None
                p.next = None
            else:
                p = None # lista jednoelementowa staje się
                self.head = None # listą pustą

Na początek: podrozdziału strony

Jeśli wybranym elementem jest pierwszy element listy, to operacja sprowadza się do opisanej wcześniej operacji dodawania elementu na początku listy. Pierwszy element rozpoznajemy po tym, iż wskazuje go pole head.

Załóżmy, że wybranym elementem nie jest pierwszy element na liście, lecz dowolny z następnych. Na rysunku zaznaczono go kolorem jasnoniebieskim.

Znajdujemy poprzednik elementu wybranego – listę przechodzimy dotąd, aż pole next przetwarzanego elementu będzie zawierało adres elementu wybranego. Poprzednik elementu wybranego zaznaczyliśmy kolorem żółtym.

Tworzymy dynamicznie nowy element (na rysunku zaznaczony kolorem zielonym) i jego adres umieszczamy w polu next elementu poprzedzającego, a w polu next nowego elementu umieszczamy adres elementu wybranego. W ten sposób nowy element zostanie umieszczony na liście przed elementem wybranym.

Algorytm dołączania nowego elementu przed wybranym elementem listy jednokierunkowej

Wejście:

head : zmienna wskazująca początek listy.
e : wskazanie elementu listy, przed którym ma zostać wstawiony nowy element.
v : dane dla nowego elementu.

Wyjście:

Lista z nowym elementem wstawionym przed element wskazywany przez e.

Dane pomocnicze:

p: wskazanie elementu listy.
l_push_front(head, v) : umieszcza nowy element o wartości v na początku listy.

Lista kroków:

K01: p ← head ; pobieramy do p adres początku listy
K02: Jeśli p ≠ e, ;sprawdzamy, czy e nie jest
     to idź do kroku K05 ; pierwszym elementem listy
K03: l_push_front(head, v) ; nowy element umieść
     ; na początku listy
K04: Zakończ
K05: Dopóki p→next ≠ e, ; przechodzimy do elementu
     wykonuj p ← p→next ; poprzedzającego e
K06: p→next ← nowy element  ; tworzymy nowy element listy
     ; i jego adres umieszczany w następniku p
K07: p→next→next ← e ; inicjujemy pola nowego elementu
K08: p→next→data ← v
K10: Zakończ

Pascal

procedure l_insert_before(var head : PSLel;
                          e : PSLel;
                          v : char);
var
  p : PSLel;
begin
  p := head;
  if p = e then
    l_push_front(head, v)
  else
  begin
    while p^.next <> e do
      p := p^.next;
    new(p^.next);
    p^.next^.next := e;
    p^.next^.data := v;
  end;
end;

C++

void l_insert_before(SLel * & head, 
                     SLel * e, 
                     char v)
{
  SLel * p = head;

  if(p == e)
    l_push_front(head, v);
  else
  {
    while(p->next != e)
      p = p->next;
    p->next = new SLel;
    p->next->next = e;
    p->next->data = v;
  }
}

Basic

Sub l_insert_before(ByRef head As SLel Ptr, _
                          e As SLel Ptr, _
                          v As String)
  Dim p As SLel Ptr

  p = head
  If p = e Then
  	 l_push_front(head, v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New SLel
    p->next->next = e
    p->next->data = v
  End If
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    def l_insert_before(self, e, v):
        p = self.head
        if p is e:
            self.l_push_front(v)
        else:
            while(p.next is not e):
                p = p.next
            p.next = SLel(v)
            p.next.next = e

Na początek: podrozdziału strony

Zadanie mamy znacznie uproszczone w porównaniu z poprzednim. Załóżmy, że wybrany element jest dowolnym elementem listy, nieważne którym (na rysunku oznaczony został kolorem jasnoniebieskim).

Tworzymy dynamicznie w pamięci nowy element (na rysunku w kolorze jasnozielonym).

W polu next nowego elementu umieszczamy zawartość pola next elementu wybranego. W ten sposób następnikiem nowego elementu będzie następnik elementu wybranego.

W polu next elementu wybranego umieszczamy adres nowego elementu. Nowy element zostaje umieszczony na liście za elementem wybranym.

Algorytm dołączania nowego elementu za wybranym elementem listy jednokierunkowej

Wejście:

e : wskazanie elementu listy, za którym ma zostać wstawiony nowy element.
v : dane dla nowego elementu.

Wyjście:

Lista z nowym elementem wstawionym za elementem wskazywanym przez e.

Dane pomocnicze:

p : wskazania elementu listy.

Lista kroków:

K01: p ← e→next ; adres elementu następnego
K02: e→next ← Nowy element ; jako następny za wybranym
     ; będzie nowy element
K03: e→next→next ← p ; następnik nowego elementu
K04: e→next→data ← v
K06: Zakończ

Pascal

procedure l_insert_after(e : PSLel;
                         v : char);
var
  p : PSLel;
begin
  p := e^.next;
  new(e^.next);
  (e^.next)^.next := p;
  (e^.next)^.data := v;
end;

C++

void l_insert_after(SLel * e, 
                    char v)
{
  SLel * p = e->next;

  e->next = new SLel;
  e->next->next = p;
  e->next->data = v;
}

Basic

Sub l_insert_after(e As SLel Ptr, _
                   v As String)
  Dim p As SLel Ptr

  p = e->next
  e->next = new SLel
  e->next->next = p
  e->next->data = v
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_insert_after(self, e, v):
        p = e.next
        e.next = SLel(v)
        e.next.next = p;

Na początek: podrozdziału strony

Jeśli wybranym do usunięcia elementem jest pierwszy na liście, to wykorzystujemy podany wcześniej algorytm usuwania pierwszego elementu listy.

Załóżmy, że usuwany element nie jest pierwszym elementem listy.

Skoro tak, to posiada on poprzedniki. Znajdujemy poprzednik wybranego elementu – na rysunku zaznaczyliśmy go na zielono.

W polu next poprzednika umieszczamy zawartość pola next usuwanego elementu. W ten sposób poprzednik będzie wskazywał na następnik wybranego elementu, a sam element wybrany znajdzie się poza listą.

Wybrany element można usunąć z pamięci. Lista staje się krótsza o jeden element.

Algorytm usuwania wybranego elementu listy jednokierunkowej

Wejście:

head : zmienna wskazująca początek listy.
e : wskazanie elementu listy do usunięcia.

Wyjście:

Lista bez elementu wskazywanego przez e.

Dane pomocnicze:

p : wskazania elementu listy.
l_pop_front(head) : usuwa pierwszy element listy.

Lista kroków:

K01: Jeśli head ≠ e, ; sprawdzamy, czy usuwany element
     to idź do kroku K04 ; jest pierwszym na liście
K02: l_pop_front(head) ; jeśli tak, usuwamy go z listy
K03: Zakończ
K04: p ← head ; w p ustawiamy początek listy
K05: Dopóki p→next ≠ e, ; w p ustawiamy adres elementu
     wykonuj p ← p→next ; poprzedzającego e
K06: p→next ← e→next ; odłączamy e od listy
K07: Usuń z pamięci element
     wskazywany przez e
K08: Zakończ

Pascal

procedure l_remove(var head : PSLel;
                       e : PSLel);
var
  p : PSLel;
begin
  if head = e then
    l_pop_front(head)
  else
  begin
    p := head;
    while p^.next <> e do
      p := p^.next;
    p^.next := e^.next;
    dispose(e);
  end;
end;

C++

void l_remove(SLel * & head, 
              SLel * e)
{
  SLel * p;

  if(head == e)
    l_pop_front(head);
  else
  {
    p = head;
    while(p->next != e)
      p = p->next;
    p->next = e->next;
    delete e;
  }
}

Basic

Sub l_remove(ByRef head As SLel Ptr, _
                   e As SLel Ptr)
  Dim p As SLel Ptr

  If head = e Then
    l_pop_front(head)
  Else
    p = head
    While p->next <> e
      p = p->next
    Wend
    p->next = e->next
    Delete e
  End If
End Sub

Python (dodatek)

class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


class SLvar:


    def __init__(self):
        self.head = None


    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None


    def l_remove(self, e):
        if self.head is e:
            self.l_pop_front()
        else:
            p = self.head
            while p.next is not e:
                p = p.next
            p.next = e.next
            e = None

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Poniższy program demonstruje opisane operacje na liście jednokierunkowej. Tworzy on listę kolejnych liter od A do G (7 elementów). Następnie wybiera element z literą D i wstawia przed nim + a za nim *. Na zakończenie z listy jest usuwany element D, pierwszy i ostatni. Po każdej operacji zawartość listy zostaje wyświetlona.

Pascal

// Program testowy dla list jednokierunkowych
// Data: 7.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------

program slist_test2;

// Typ elementów listy
//--------------------
type
  PSLel = ^SLel;

  SLel =  record
    next  : PSLel;
    data  : char;
  end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function l_len(p : PSLel) : cardinal;
var
  c : cardinal;
begin
  c := 0; // zerujemy licznik
  while p <> nil do
  begin
    inc(c); // zwiększamy licznik o 1
    p := p^.next;
  end;
  l_len := c;
end;

// Procedura wyświetla zawartość
// elementów listy
//------------------------------
procedure l_print(p : PSLel);
var
  i : cardinal;
begin
  writeln('Number of elements : ', l_len(p));
  i := 1;
  while p <> nil do
  begin
    writeln('Element #', i, '  data = ', p^.data);
    inc(i);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure l_push_front(var head : PSLel;
                           v : char);
var
  p : PSLel;
begin
  new(p); // tworzymy nowy element
  p^.data := v; // inicjujemy element
  p^.next := head;
  head := p;
end;

// Procedura dołączania na koniec listy
//-------------------------------------
procedure l_push_back(var head : PSLel;
                          v : char);
var
  p, e : PSLel;
begin
  new(e); // tworzymy nowy element
  e^.next := nil; // inicjujemy element
  e^.data := v;
  p := head;
  if p = nil then
    head := e
  else
  begin
    while p^.next <> nil do
      p := p^.next;
    p^.next := e;
  end;
end;

// Procedura dołączania przed elementem e
//---------------------------------------
procedure l_insert_before(var head : PSLel;
                              e : PSLel;
                              v : char);
var
  p : PSLel;
begin
  p := head;
  if p = e then
    l_push_front(head, v)
  else
  begin
    while p^.next <> e do
      p := p^.next;
    new(p^.next);
    p^.next^.next := e;
    p^.next^.data := v;
  end;
end;

// Procedura dołączania za elementem e
//------------------------------------
procedure l_insert_after(e : PSLel;
                         v : char);
var
  p : PSLel;
begin
  p := e^.next;
  new(e^.next);
  (e^.next)^.next := p;
  (e^.next)^.data := v;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure l_pop_front(var head : PSLel);
var
  p : PSLel;
begin
  p := head; // zapamiętujemy początek
  if p <> nil then
  begin
    head := p^.next; // nowy początek
    dispose(p); // usuń element z pamięci
  end;
end;

// Procedura usuwa ostatni element
//---------------------------------
procedure l_pop_back(var head : PSLel);
var
  p : PSLel;
begin
  p := head;
  if p <> nil then
  begin
    if p^.next <> nil then
    begin
      while p^.next^.next <> nil do
        p := p^.next;
      dispose(p^.next);
      p^.next := nil;
    end
    else
    begin
      dispose(p); // lista jednoelementowa
      head := nil; // staje się listą pustą
    end
  end;
end;

// Procedura usuwa wybrany element
//--------------------------------
procedure l_remove(var head : PSLel;
                   e : PSLel);
var
  p : PSLel;
begin
  if head = e then
    l_pop_front(head)
  else
  begin
    p := head;
    while p^.next <> e do
      p := p^.next;
    p^.next := e^.next;
    dispose(e);
  end;
end;

//---------------
// Program główny
//---------------

var
  L : PSLel; // adres początku listy
  e : PSLel; // wskazywanie elementów
  i : char;

begin
  L := nil;

  for i := 'A' to 'G' do
    l_push_back(L, i);
  l_print(L);

  // Przechodzimy do elementu o wartości D
  e := L;
  for i := 'A' to 'C' do
    e := e^.next;

  // Przed elementem D umieszczamy +
  l_insert_before(L, e, '+');

  // Za elementem D umieszczamy *
  l_insert_after(e, '*');
  l_print(L);

  // Usuwamy element D oraz
  // element pierwszy i ostatni
  l_remove(L, e);
  l_pop_front(L);
  l_pop_back(L);
  l_print(L);
end.

C++

// Program testowy dla list jednokierunkowych
// Data: 11.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typ elementów listy
//--------------------
struct SLel
{
  SLel * next;
  char data;
};

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned l_len(SLel * p)
{
  unsigned c = 0; // zerujemy licznik

  while(p)
  {
    c++; // zwiększamy licznik o 1
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void l_print(SLel * p)
{
  unsigned i;

  cout << "Number of elements : "
       << l_len(p) << endl;

  for(i = 1; p; p = p->next)
    cout << "Element #" << i++
         << "  data = " << p->data
         << endl;

  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void l_push_front(SLel * & head, 
                  char v)
{
  SLel * p;

  p = new SLel; // tworzymy nowy element
  p->data = v; // inicjujemy element
  p->next = head;
  head = p;
}

// Procedura dołączania na koniec listy
//---------------------------------------
void l_push_back(SLel * & head, 
                 char v)
{
  SLel * p, * e;

  e = new SLel; // tworzymy nowy element
  e->next = NULL; // inicjujemy element
  e->data = v;
  p = head;
  if(p)
  {
     while(p->next) p = p->next;
     p->next = e;
  }
  else head = e;
}

// Procedura dołączania przed elementem e
//---------------------------------------
void l_insert_before(SLel * & head, 
                     SLel * e, 
                     char v)
{
  SLel * p = head;

  if(p == e)
    l_push_front(head, v);
  else
  {
    while(p->next != e)
      p = p->next;
    p->next = new SLel;
    p->next->next = e;
    p->next->data = v;
  }
}

// Procedura dołączania za elementem e
//------------------------------------
void l_insert_after(SLel * e, 
                    char v)
{
  SLel * p = e->next;

  e->next = new SLel;
  e->next->next = p;
  e->next->data = v;
}

// Procedura usuwa pierwszy element
//---------------------------------
void l_pop_front(SLel * & head)
{
  SLel * p = head; // zapamiętujemy początek

  if(p)
  {
    head = p->next; // nowy początek
    delete p; // usuń element z pamięci
  }
}

// Procedura usuwa ostatni element
//---------------------------------
void l_pop_back(SLel * & head)
{
  SLel * p = head;
  if(p)
  {
    if(p->next)
    {
      while(p->next->next)
        p = p->next;
      delete p->next;
      p->next = NULL;
    }
    else
    {
      delete p; // lista jednoelementowa
      head = NULL; // staje się listą pustą
    }
  }
}

// Procedura usuwa wybrany element
//--------------------------------
void l_remove(SLel * & head, 
              SLel * e)
{
  SLel * p;

  if(head == e)
    l_pop_front(head);
  else
  {
    p = head;
    while(p->next != e)
      p = p->next;
    p->next = e->next;
    delete e;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  SLel * L = NULL; // adres początku listy
  SLel * e;  // do wskazywania elementów listy
  char i;

  for(i = 'A'; i <= 'G'; i++)
    l_push_back(L, i);
  l_print(L);

  // Przechodzimy do elementu o wartości D
  e = L;
  for(i = 'A'; i <= 'C'; i++)
    e = e->next;

  // Przed elementem D umieszczamy +
  l_insert_before(L, e, '+');

  // Za elementem D umieszczamy *
  l_insert_after(e, '*');
  l_print(L);

  // Usuwamy element D oraz element pierwszy i ostatni
  l_remove(L, e);
  l_pop_front(L);
  l_pop_back(L);
  l_print(L);

  return 0;
}

Basic

' Program testowy dla list jednokierunkowych
' Data: 11.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------

' Typ elementów listy
'--------------------
Type SLel
  next As SLel Ptr
  data As String * 1
End Type

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function l_len(p As SLel Ptr) _
               As UInteger
  Dim c As UInteger

  c = 0 ' zerujemy licznik
  While p
    c += 1 ' zwiększamy licznik o 1
    p = p->next
  Wend
  l_len = c
End Function

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub l_print (p As SLel Ptr)
  Dim i As UInteger
  
  Print "Number of elements : ";l_len(p)

  i = 1
  While p
    Print "Element #";i;"  data = ";p->data
    i += 1
    p = p->next
  Wend
  
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub l_push_front(ByRef head As SLel Ptr, _
                       v As String)
  Dim p As SLel Ptr

  p = new SLel ' tworzymy nowy element
  p->data = v ' inicjujemy element
  p->next = head
  head = p
End Sub

' Procedura dołączania na koniec listy
'-------------------------------------
Sub l_push_back(ByRef head As SLel Ptr, _
                      v As String)
  Dim As SLel Ptr p, e

  e = New SLel
  e->next = 0
  e->data = v
  p = head
  If p = 0 Then
    head = e
  Else
    While p->next
      p = p->next
    Wend
    p->next = e
  End If
End Sub

' Procedura dołączania przed elementem e
'---------------------------------------
Sub l_insert_before(ByRef head As SLel Ptr, _
                          e As SLel Ptr, _
                          v As String)
  Dim p As SLel Ptr

  p = head
  If p = e Then
    l_push_front(head, v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New SLel
    p->next->next = e
    p->next->data = v
  End If
End Sub

' Procedura dołączania za elementem e
'------------------------------------
Sub l_insert_after(e As SLel Ptr, _
                   v As String)
  Dim p As SLel Ptr

  p = e->next
  e->next = new SLel
  e->next->next = p
  e->next->data = v
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub l_pop_front(ByRef head As SLel Ptr)
  Dim p As SLel Ptr

  p = head
  If p Then
    head = p->next
    Delete p
  End If
End Sub

' Procedura usuwa ostatni element
'--------------------------------
Sub l_pop_back(ByRef head As SLel Ptr)
  Dim p As SLel Ptr

  p = head
  If p Then
    If p->next Then
      While p->next->next
    	  p = p->next
      Wend
      Delete p->next
      p->next = 0
    Else
      Delete p
      head = 0
    End If
  End If
End Sub

' Procedura usuwa wybrany element
'--------------------------------
Sub l_remove(ByRef head As SLel Ptr, _
                   e As SLel Ptr)
  Dim p As SLel Ptr

  If head = e Then
    l_pop_front(head)
  Else
    p = head
    While p->next <> e
      p = p->next
    Wend
    p->next = e->next
    Delete e
  End If
End Sub

'---------------
' Program główny
'---------------

Dim L As SLel Ptr
Dim e As SLel Ptr
Dim i As Integer

L = 0

For i = Asc("A") To Asc("G")
  l_push_back(L, Chr(i))
Next
l_print(L)

' Przechodzimy do elementu o wartości D
e = L
For i = 1 To 3
  e = e->next
Next

' Przed elementem D umieszczamy +
l_insert_before(L, e, "+")

' Za elementem D umieszczamy *
l_insert_after(e, "*")
l_print(L)

' Usuwamy element D oraz element pierwszy i ostatni
l_remove(L, e)
l_pop_front(L)
l_pop_back(L)
l_print(L)
End

Wynik:

Number of elements : 7
Element #1 data = A
Element #2 data = B
Element #3 data = C
Element #4 data = D
Element #5 data = E
Element #6 data = F
Element #7 data = G

Number of elements : 9
Element #1 data = A
Element #2 data = B
Element #3 data = C
Element #4 data = +
Element #5 data = D
Element #6 data = *
Element #7 data = E
Element #8 data = F
Element #9 data = G

Number of elements : 6
Element #1 data = B
Element #2 data = C
Element #3 data = +
Element #4 data = *
Element #5 data = E
Element #6 data = F

Python (dodatek)

# Program testowy dla list jednokierunkowych
# Data: 4.05.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------------------


# klasa elementu listy jednokierunkowej
class SLel:


    # Konstruktor
    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
class SLvar:


    # Konstruktor
    def __init__(self):
        self.head = None


    # destruktor
    def __del__(self):
        while self.head:
            self.l_pop_front()
        print("Lista usunięta z pamięci")


    # długość listy
    def l_len(self):
        c = 0
        p = self.head
        while p:
            c += 1
            p = p.next
        return c


    # wyświetlenie listy
    def l_print(self):
        print("Liczba elementów :", self.l_len())
        i = 1
        p = self.head
        while p:
            print("Element nr", i, "dane =", p.data)
            i += 1
            p = p.next
        print()


    # wstawianie na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    # wstawianie na koniec
    def l_push_back(self, v):
        e = SLel(v)
        p = self.head
        if p:
            while p.next:
                p = p.next
            p.next = e
        else:
            self.head = e


    #wstawianie przed e
    def l_insert_before(self, e, v):
        p = self.head
        if p is e:
            self.l_push_front(v)
        else:
            while p.next is not e:
                p = p.next
            p.next = SLel(v)
            p.next.next = e


    # usuwanie z przodu
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next


    # usuwanie z tyłu
    def l_pop_back(self):
        p = self.head
        if p:
            if p.next:
                while p.next.next:
                    p = p.next
                p.next = None
            else:
                self.head = None


    # usuwanie e
    def l_remove(self, e):
        if self.head is e:
            self.l_pop_front()
        else:
            p = self.head
            while p.next is not e:
                p = p.next
            p.next = e.next


# wstawianie za e
def l_insert_after(e, v):
        p = e.next
        e.next = SLel(v)
        e.next.next = p


#---------------
# Program główny
#---------------

sl = SLvar()
for i in range(ord('A'), ord('G')+1):
    sl.l_push_back(chr(i))
sl.l_print()
# Przechodzimy do elementu D
e = sl.head
for i in range(ord('A'), ord('C')+1):
    e = e.next
# Przed elementem D umieszczamy +
sl.l_insert_before(e, '+')
# Za elementem D umieszczamy *
l_insert_after(e, '*')
sl.l_print()
# Usuwamy element D oraz
# element pierwszy i ostatni
sl.l_remove(e)
sl.l_pop_front()
sl.l_pop_back()
sl.l_print()
sl = None

Wynik:

Liczba elementów : 7
Element nr 1 dane = A
Element nr 2 dane = B
Element nr 3 dane = C
Element nr 4 dane = D
Element nr 5 dane = E
Element nr 6 dane = F
Element nr 7 dane = G

Liczba elementów : 9
Element nr 1 dane = A
Element nr 2 dane = B
Element nr 3 dane = C
Element nr 4 dane = +
Element nr 5 dane = D
Element nr 6 dane = *
Element nr 7 dane = E
Element nr 8 dane = F
Element nr 9 dane = G

Liczba elementów : 6
Element nr 1 dane = B
Element nr 2 dane = C
Element nr 3 dane = +
Element nr 4 dane = *
Element nr 5 dane = E
Element nr 6 dane = F

Lista usunięta z pamięci

Na początek: podrozdziału strony

W dalszych rozdziałach będziemy używali list jako obiektów ze względu na wygodę programowania. Obiekt jest strukturą danych, która posiada pola danych oraz funkcje i procedury obsługujące te pola. Do funkcji i procedur obiektu odwołujemy się identycznie jak do pól struktury. Każdy z wybranych przez nas języków programowania, tj. Pascal, C++, Basic i Python pozwala bezproblemowo tworzyć obiekty. Poniższy program jest obiektową wersją ostatniego programu.

Pascal

// Obiekt listy jednokierunkowej
// Data: 12.02.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

program slist_object;

// Typ elementów listy
//--------------------
type
  PSLel = ^SLel;

  SLel =  record
    next  : PSLel;
    data  : char;
  end;

// Definicja typu obiektowego SLvar
//------------------------------------
  SLvar = object
    public
      head : PSLel;  // początek listy

      constructor init;
      destructor destroy;
      function  l_len : cardinal;
      procedure l_print;
      procedure l_push_front(v : char);
      procedure l_push_back(v : char);
      procedure l_insert_before(e : PSLel;
                                v : char);
      procedure l_insert_after(e : PSLel;
                               v : char);
      procedure l_pop_front;
      procedure l_pop_back;
      procedure l_remove(e : PSLel);
  end;

//------------------------
// Metody obiektu SLvar
//------------------------

// Konstruktor-inicjuje pole head
//---------------------------------
constructor SLvar.init;
begin
  head := nil;
end;

// Destruktor-usuwa listę z pamięci
//-----------------------------------
destructor SLvar.destroy;
begin
  while head <> nil do l_pop_front;
end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function SLvar.l_len : cardinal;
var
  c : cardinal;
  p : PSLel;
begin
  c := 0;
  p := head;
  while p <> nil do
  begin
    inc(c);
    p := p^.next;
  end;
  l_len := c;
end;

// Procedura wyświetla zawartość
// elementów listy
//------------------------------
procedure SLvar.l_print;
var
  i : integer;
  p : PSLel;
begin
  writeln('Number of elements : ', l_len);
  p := head;
  i := 1;
  while p <> nil do
  begin
    writeln('Element #', i, '  data = ', p^.data);
    inc(i);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure SLvar.l_push_front(v : char);
var
  p : PSLel;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura dołączania na koniec listy
//-------------------------------------
procedure SLvar.l_push_back(v : char);
var
  p, e : PSLel;
begin
  new(e);
  e^.next := nil;
  e^.data := v;
  p := head;
  if p = nil then
    head := e
  else
  begin
    while p^.next <> nil do p := p^.next;
    p^.next := e;
  end;
end;

// Procedura dołączania przed elementem e
//---------------------------------------
procedure SLvar.l_insert_before(e : PSLel;
                                   v : char);
var
  p : PSLel;
begin
  p := head;
  if p = e then
    l_push_front(v)
  else
  begin
    while p^.next <> e do
      p := p^.next;
    new(p^.next);
    p^.next^.next := e;
    p^.next^.data := v;
  end;
end;

// Procedura dołączania za elementem e
//------------------------------------
procedure SLvar.l_insert_after(e : PSLel;
                                  v : char);
var
  p : PSLel;
begin
  new(p);
  p^.next := e^.next;
  p^.data := v;
  e^.next := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure SLvar.l_pop_front;
var
  p : PSLel;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose(p);
  end;
end;

// Procedura usuwa ostatni element
//---------------------------------
procedure SLvar.l_pop_back;
var
  p : PSLel;
begin
  p := head;
  if p <> nil then
  begin
    if p^.next <> nil then
    begin
      while p^.next^.next <> nil do
        p := p^.next;
      dispose(p^.next);
      p^.next := nil;
    end
    else
    begin
      dispose(p);
      head := nil;
    end
  end;
end;

// Procedura usuwa wybrany element
//--------------------------------
procedure SLvar.l_remove (e : PSLel);
var
  p : PSLel;
begin
  if head = e then
    l_pop_front
  else
  begin
    p := head;
    while p^.next <> e do
      p := p^.next;
    p^.next := e^.next;
    dispose(e);
  end;
end;

//---------------
// Program główny
//---------------

var
  L : SLvar; // lista jednokierunkowa
  e : PSLel; // wskazywanie elementów listy
  i : char;

begin
  L.init; // inicjujemy obiekt

  for i := 'A' to 'G' do
    L.l_push_back(i);
  L.l_print;

  // Przechodzimy do elementu o wartości D
  e := L.head;
  for i := 'A' to 'C' do
    e := e^.next;

  // Przed elementem D umieszczamy +
  L.l_insert_before(e, '+');

  // Za elementem D umieszczamy *
  L.l_insert_after(e, '*');
  L.l_print;

  // Usuwamy element D oraz
  // element pierwszy i ostatni
  L.l_remove(e);
  L.l_pop_front;
  L.l_pop_back;
  L.l_print;
  L.destroy;

end.

C++

// Obiekt listy jednokierunkowej
// Data: 12.02.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Typ elementów listy
//--------------------
struct SLel
{
  SLel * next;
  char data;
};

// Definicja typu obiektowego SLvar
//------------------------------------
class SLvar
{
  public:
    SLel * head;

    SLvar();  // konstruktor
    ~SLvar(); // destruktor
    unsigned l_len();
    void l_print();
    void l_push_front(char v);
    void l_push_back(char v);
    void l_insert_before(SLel * e, 
                         char v);
    void l_insert_after(SLel * e, 
                        char v);
    void l_pop_front();
    void l_pop_back();
    void l_remove(SLel * e);
};

// Konstruktor listy
//------------------
SLvar::SLvar()
{
  head = NULL;
}

// Destruktor listy
//-----------------
SLvar::~SLvar()
{
  while(head)
    l_pop_front();
}

// Funkcja oblicza liczbę
// elementów listy
//-----------------------
unsigned SLvar::l_len()
{
  unsigned c = 0;
  SLel * p = head;
  while(p)
  {
    c++;
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość
// elementów listy
//------------------------------
void SLvar::l_print()
{
  unsigned i;
  SLel * p = head;

  cout << "Number of elements : "
       << l_len() << endl;
  for(i = 1; p; p = p->next)
    cout << "Element #" << i++
         << "  data = " << p->data
         << endl;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void SLvar::l_push_front(char v)
{
  SLel * p;

  p = new SLel;
  p->next = head;
  p->data = v;
  head = p;
}

// Procedura dołączania na koniec listy
//---------------------------------------
void SLvar::l_push_back(char v)
{
  SLel * p, * e;

  e = new SLel; // tworzymy nowy element
  e->next = NULL;  // inicjujemy element
  e->data = v;
  p = head;
  if(p)
  {
     while(p->next) p = p->next;
     p->next = e;
  }
  else head = e;
}

// Procedura dołączania przed elementem e
//---------------------------------------
void SLvar::l_insert_before(SLel * e, 
                               char v)
{
  SLel * p = head;

  if(p == e)
    l_push_front(v);
  else
  {
    while(p->next != e)
      p = p->next;
    p->next = new SLel;
    p->next->next = e;
    p->next->data = v;
  }
}

// Procedura dołączania za elementem e
//------------------------------------
void SLvar::l_insert_after(SLel * e, 
                              char v)
{
  SLel * p = new SLel;

  p->next = e->next;
  p->data = v;
  e->next = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void SLvar::l_pop_front()
{
  SLel * p = head; // początek

  if(p)
  {
    head = p->next;   // nowy początek
    delete p;         // usuń element
  }
}

// Procedura usuwa ostatni element
//---------------------------------
void SLvar::l_pop_back()
{
  SLel * p = head; // początek

  if(p)
  {
    if(p->next)
    {
      while(p->next->next)
        p = p->next;
      delete p->next;
      p->next = NULL;
    }
    else
    {
      delete p;
      head = NULL;
    }
  }
}

// Procedura usuwa wybrany element
//--------------------------------
void SLvar::l_remove(SLel * e)
{
  SLel * p;

  if(head == e)
    l_pop_front();
  else
  {
    p = head;
    while(p->next != e)
      p = p->next;
    p->next = e->next;
    delete e;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  SLvar L; // zawiera adres początku listy
  SLel * e; // do wskazywania elementów listy
  char i;

  for(i = 'A'; i <= 'G'; i++)
    L.l_push_back(i);
  L.l_print();

  // Przechodzimy do elementu o wartości D
  e = L.head;
  for(i = 'A'; i <= 'C'; i++)
    e = e->next;

  // Przed elementem D umieszczamy +
  L.l_insert_before(e, '+');

  // Za elementem D umieszczamy *
  L.l_insert_after(e, '*');
  L.l_print();

  // Usuwamy element D oraz element pierwszy i ostatni
  L.l_remove(e);
  L.l_pop_front();
  L.l_pop_back();
  L.l_print();

  return 0;
}

Basic

' Program testowy dla list jednokierunkowych
' Data: 11.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------

' Typ elementów listy
'--------------------
Type SLel
  next As SLel Ptr
  data As String * 1
End Type

' Typ obiektowy SLvar
'-----------------------
Type SLvar
  head As SLel Ptr
  
  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Function l_len() As UInteger
  Declare Sub l_push_front(v As String)
  Declare Sub l_push_back(v As String)
  Declare Sub l_insert_before(e As SLel Ptr, _
                              v As String)
  Declare Sub l_insert_after(e As SLel Ptr, _
                             v As String)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
  Declare Sub l_remove(e As SLel Ptr)
End Type

'---------------
' Program główny
'---------------

Dim L As SLvar    ' adres początku listy
Dim e As SLel Ptr ' elementy listy  
Dim i As Integer

For i = Asc ("A") To Asc ("G")
  L.l_push_back(Chr(i))
Next
L.l_print()

' Przechodzimy do elementu o wartości D
e = L.head
For i = 1 To 3
  e = e->next
Next

' Przed elementem D umieszczamy +
L.l_insert_before(e, "+")

' Za elementem D umieszczamy *
L.l_insert_after(e, "*")
L.l_print()

' Usuwamy element D oraz
' elementy pierwszy i ostatni
L.l_remove(e)
L.l_pop_front()
L.l_pop_back()
L.l_print()

End

' Konstruktor listy
'-------------------
Constructor SLvar()
  head = 0
End Constructor

' Destruktor listy
'-----------------
Destructor SLvar()
  While head
    l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość
' elementów listy
'------------------------------
Sub SLvar.l_print()
  
  Dim i As UInteger
  Dim p As SLel Ptr = head
  
  Print "Number of elements : ";l_len()
  i = 1
  While p
    Print "Element #";i;"  data = ";p->data
    i += 1
    p = p->next
  Wend
  Print
End Sub

' Funkcja oblicza liczbę
' elementów listy
'-----------------------
Function SLvar.l_len As UInteger
  Dim c As UInteger
  Dim p As SLel Ptr = head

  c = 0
  While p
    c += 1
    p = p->next
  Wend
  l_len = c
End Function

' Procedura dołączania
' na początek listy
'---------------------
Sub SLvar.l_push_front(v As String)
  Dim p As SLel Ptr

  p = new SLel
  p->next = head
  p->data = v
  head = p
End Sub

' Procedura dołączania
' na koniec listy
'---------------------
Sub SLvar.l_push_back(v As String)
  Dim As SLel Ptr p, e

  e = New SLel
  e->next = 0
  e->data = v
  p = head
  If p = 0 Then
    head = e
  Else
    While p->next
      p = p->next
    Wend
    p->next = e
  End If
End Sub

' Procedura dołączania
' przed elementem e
'---------------------
Sub SLvar.l_insert_before(e As SLel Ptr, _
                             v As String)
  Dim p As SLel Ptr

  p = head
  If p = e Then
    l_push_front(v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New SLel
    p->next->next = e
    p->next->data = v
  End If
End Sub

' Procedura dołączania
' za elementem e
'---------------------
Sub SLvar.l_insert_after(e As SLel Ptr, _
                            v As String)
  Dim p As SLel Ptr

  p = new SLel
  p->next = e->next
  p->data = v
  e->next = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub SLvar.l_pop_front()
  Dim p As SLel Ptr

  p = head ' początek
  If p Then
    head = p->next ' nowy początek
    Delete p ' usuń element
  End If
End Sub

' Procedura usuwa ostatni element
'--------------------------------
Sub SLvar.l_pop_back()
  Dim p As SLel Ptr

  p = head
  If p Then
    If p->next Then
      While p->next->next
        p = p->next
      Wend
      Delete p->next
      p->next = 0
    Else
      Delete p
      head = 0
    End If
  End If
End Sub

' Procedura usuwa wybrany element
'--------------------------------
Sub SLvar.l_remove(e As SLel Ptr)
  Dim p As SLel Ptr

  If head = e Then
    l_pop_front()
  Else
    p = head
    While p->next <> e
      p = p->next
    Wend
    p->next = e->next
    Delete e
  End If
End Sub

Na początek: podrozdziału strony

Operacje na listach jednokierunkowych

Uwaga:

Typy dla list jedno-kierunkowych

Przejście przez listę

Algorytm przechodzenia przez listę jednokierunkową

Wejście:

Wyjście:

Liczba elementów listy

Algorytm wyznaczania liczby elementów na liście jednokierunkowej

Wejście:

Wyjście:

Dodawanie elementu na początku listy

Algorytm dołączania nowego elementu na początek listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Usuwanie elementu z początku listy

Algorytm usuwania elementu z początku listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Przykładowe programy

Dodawanie elementu na koniec listy

Algorytm dołączania nowego elementu do końca listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Usuwanie ostatniego elementu listy

Algorytm usuwania elementu z końca listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Dodawanie nowego elementu przed wybranym elementem listy

Algorytm dołączania nowego elementu przed wybranym elementem listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Dodawanie nowego elementu za elementem wybranym

Algorytm dołączania nowego elementu za wybranym elementem listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Usuwanie wybranego elementu listy

Algorytm usuwania wybranego elementu listy jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Przykładowe programy

Wersja obiektowa