Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Operacje na listach jednokierunkowych

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Uwaga:

Podane tutaj procedury obsługi list nie uwzględniają sytuacji błędnych – np. braku pamięci dla tworzonych elementów czy nieprawidłowych danych. Można je zatem stosować tylko wtedy, gdy jesteśmy w 100% pewni, że nie dojdzie do żadnych błędów. W przeciwnym razie należałoby zaimplementować obsługę wyjątków, a to jest temat na osobny artykuł.

Typy dla list jedno-kierunkowych

Pascal
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : typ_danych;
  end;
C++
struct slistEl
{
  slistEl * next;
  typ_danych data;
};
Basic
Type slistEl
  next As slistEl Ptr
  data As typ_danych
End Type
Python (dodatek)
# klasa elementu listy jednokierunkowej
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data
# klasa listy jednokierunkowej
class slistVar:
    def __init__(self):
        self.head = None

Przejście przez listę

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 ← (pnext) ; 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 

Liczba elementów listy

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:   cc + 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 : PslistEl) : 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(slistEl * 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 slistEl 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 slistEl:

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

# klasa listy jednokierunkowej
class slistVar:

    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 

Dodawanie elementu na początku listy

obrazek
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:
obrazek
Tworzymy dynamicznie w pamięci nowy element listy (na rysunku w kolorze zielonym). Wprowadzamy do niego dane dla pola data.
obrazek
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.
obrazek
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: (pdata) ← v ; umieszczamy dane w elemencie
K03: (pnext) ← head ; następnikiem będzie bieżący
                     ; pierwszy element listy
K04: headp ; 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 : PslistEl;
                       v : char);
var
  p : PslistEl;
begin
  new(p);       // tworzymy nowy element
  p^.data := v; // inicjujemy element
  p^.next := head;
  head := p;
end;
C++
void l_push_front(slistEl * & head,
char v)
{
  slistEl * p = new slistEl;

  p->data = v; // inicjujemy element
  p->next = head;
  head = p;
}
Basic
Sub l_push_front(ByRef head As slistEl Ptr,_
                 v As String)

  Dim p As slistEl Ptr

  p = new slistEl  ' tworzymy nowy element
  p->data = v      ' inicjujemy element
  p->next = head
  head = p
End Sub
Python (dodatek)
class slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    def __init__(self):
        self.head = None

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

Na początek:  podrozdziału   strony 

Usuwanie elementu z początku listy

obrazek
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.
obrazek
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.
obrazek
Odłączony element usuwamy z pamięci.
obrazek
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 ← (pnext) ; 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 : PslistEl);
var
  p : PslistEl;
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(slistEl * & head)
{
  slistEl * 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 slistEl Ptr)

  Dim p As slistEl 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 slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    def __init__(self):
        self.head = None

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

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
  PslistEl = ^slistEl;

  slistEl = record
    next  : PslistEl;
    data  : char;
  end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function l_len(p : PslistEl) : 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 : PslistEl);
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 : PslistEl;
                           v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.data := v;
  p^.next := head;
  head := p;
end;

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

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

var
  L : PslistEl;   // zawiera 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 slistEl
{
  slistEl * next;
  char data;
};

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

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

// Procedura wyświetla zawartość elementów
//----------------------------------------
void l_print(slistEl * 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(slistEl * & head, char v)
{
  slistEl * p;

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

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

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

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

int main()
{
  slistEl * 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function l_len(p As slistEl 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 slistEl 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 slistEl Ptr,_
                       v As String)

  Dim p As slistEl Ptr

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

' Procedura usuwa pierwszy element
'---------------------------------
Sub l_pop_front(ByRef head As slistEl Ptr)

  Dim p As slistEl Ptr

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

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

Dim L As slistEl 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)
sleep
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 slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:
    
    # 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 = slistEl(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
            del p

    # 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
#---------------

L = slistVar() # lista
L.l_push_front('A')
L.l_push_front('B')
L.l_push_front('C')
L.l_print()
L.l_pop_front()
L.l_pop_front()
L.l_print()
del L
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 

Dodawanie elementu na koniec listy

obrazek
Tworzymy nowy element. W polu next umieszczamy adres zero – ostatni element listy nie posiada następnika.
obrazek
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.
obrazek
Jeśli lista zawiera elementy, to przechodzimy do ostatniego z nich (za pomocą podanego wcześniej algorytmu przejścia listy).
obrazek
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.
obrazek
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: (enext) ← nil ; inicjujemy pola nowego elementu
K03: (edata) ← 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: heade ; jeśli tak, to nowy element będzie
              ; pierwszym elementem listy
K07: Zakończ
K08: Dopóki (pnext) ≠ nil, ; inaczej przechodzimy
     wykonuj p ← (pnext)   ; do ostatniego elementu listy
K09: (pnext) ← e ; dołączamy nowy element
                  ; za ostatnim na liście
K10: Zakończ
Pascal
procedure l_push_back(var head : PslistEl;
                          v : char);
var
  p,e : PslistEl;
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(slistEl * & head, char v)
{
  slistEl * p, * e;

  e = new slistEl; // 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 slistEl Ptr,_
                      v As String)

  Dim As slistEl Ptr p,e

  e = New slistEl ' 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 slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    def __init__(self):
        self.head = None

    def l_push_back(self,v):
        e = slistEl(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 

Usuwanie ostatniego elementu listy

obrazek
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.
obrazek
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.
obrazek
Odłączony element usuwamy z pamięci i kończymy.
obrazek
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.
obrazek
Usuwamy z pamięci element wskazywany przez pole next przedostatniego elementu listy.
obrazek
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: phead ; 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 (pnext) ≠ 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 ((pnext)→next) ≠ nil, ; idziemy do
     wykonuj p ← (pnext) ; przedostatniego elementu
K08: Usuń z pamięci element ; usuwamy następny element,
     wskazywany przez (pnext) ; czyli ostatni
K09: (pnext) ← nil ; przedostatni element nie ma
                    ; już następnika
K10: Zakończ
Pascal
procedure l_pop_back(var head : PslistEl);
var
  p : PslistEl;
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(slistEl * & head)
{
  slistEl * 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 slistEl Ptr)

  Dim p As slistEl 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 slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    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
                del p.next
                p.next = None
            else:
                del p            # lista jednoelementowa
                self.head = None # staje się listą pustą

Na początek:  podrozdziału   strony 

Dodawanie nowego elementu przed wybranym elementem listy

obrazek
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.
obrazek
Załóżmy, że wybranym elementem nie jest pierwszy element na liście, lecz dowolny z następnych. Na rysunku zaznaczono go kolorem jasnoniebieskim.
obrazek
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.
obrazek
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: phead ; pobieramy do p adres początku listy
K02: Jeśli pe, ;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 (pnext) ≠ e, ; przechodzimy do elementu
     wykonuj p ← (pnext) ; poprzedzającego e
K06: (pnext) ← nowy element  ; tworzymy nowy element listy
     ; i jego adres umieszczany w następniku p
K07: ((pnext)→next) ← e ; inicjujemy pola nowego elementu
K08: ((pnext)→data) ← v
K10: Zakończ
Pascal
procedure l_insert_before(var head : PslistEl;
                          e : PslistEl;
                          v : char);
var
  p : PslistEl;
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(slistEl * & head,
                     slistEl * e,
                     char v)
{
  slistEl * p = head;

  if(p == e) l_push_front(head,v);
  else
  {
    while(p->next != e)
      p = p->next;
    p->next = new slistEl;
    p->next->next = e;
    p->next->data = v;
  }
}
Basic
Sub l_insert_before(ByRef head As slistEl Ptr,_
                          e As slistEl Ptr,_
                          v As String)

  Dim p As slistEl Ptr

  p = head
  If p = e Then
  	 l_push_front(head,v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New slistEl
    p->next->next = e
    p->next->data = v
  End If
End Sub
Python (dodatek)
class slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    def __init__(self):
        self.head = None

    def l_push_front(self,v):
        p = slistEl(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 = slistEl(v)
            p.next.next = e

Na początek:  podrozdziału   strony 

Dodawanie nowego elementu za elementem wybranym

obrazek
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).
obrazek
Tworzymy dynamicznie w pamięci nowy element (na rysunku w kolorze jasnozielonym).
obrazek
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.
obrazek
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 ← (enext)            ; adres elementu następnego
K02: (enext) ← Nowy element ; jako następny za wybranym
                             ; będzie nowy element
K03: ((enext)→next) ← p     ; następnik nowego elementu
K04: ((enext)→data) ← v
K06: Zakończ
Pascal
procedure l_insert_after(e : PslistEl;
                         v : char);
var
  p : PslistEl;
begin
  p := e^.next;
  new(e^.next);
  (e^.next)^.next := p;
  (e^.next)^.data := v;
end;
C++
void l_insert_after(slistEl * e,
                    char v)
{
  slistEl * p = e->next;

  e->next = new slistEl;
  e->next->next = p;
  e->next->data = v;
}
Basic
Sub l_insert_after(e As slistEl Ptr,_
                   v As String)

  Dim p As slistEl Ptr

  p = e->next
  e->next = new slistEl
  e->next->next = p
  e->next->data = v
End Sub
Python (dodatek)
class slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    def __init__(self):
        self.head = None

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

Na początek:  podrozdziału   strony 

Usuwanie wybranego elementu listy

obrazek
Jeśli wybranym do usunięcia elementem jest pierwszy na liście, to wykorzystujemy podany wcześniej algorytm usuwania pierwszego elementu listy.
obrazek
Załóżmy, że usuwany element nie jest pierwszym elementem listy.
obrazek
Skoro tak, to posiada on poprzedniki. Znajdujemy poprzednik wybranego elementu – na rysunku zaznaczyliśmy go na zielono.
obrazek
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ą.
obrazek
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 heade, ; 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: phead ; w p ustawiamy początek listy
K05: Dopóki (pnext) ≠ e, ; w p ustawiamy adres elementu
     wykonuj p ← (pnext) ; poprzedzającego e
K06: (pnext) ← (enext)  ; odłączamy e od listy
K07: Usuń z pamięci element
     wskazywany przez e
K08: Zakończ
Pascal
procedure l_remove(var head : PslistEl;
                       e : PslistEl);
var
  p : PslistEl;
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(slistEl * & head,
              slistEl * e)
{
  slistEl * 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 slistEl Ptr,
                   e As slistEl Ptr)

  Dim p As slistEl 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 slistEl:
    
    def __init__(self,data):
        self.next = None
        self.data = data

class slistVar:
    
    def __init__(self):
        self.head = None

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

    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
            del e

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
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function l_len(p : PslistEl) : 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 : PslistEl);
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 : PslistEl;
                           v : char);
var
  p : PslistEl;
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 : PslistEl;
                          v : char);
var
  p,e : PslistEl;
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 : PslistEl;
                              e : PslistEl;
                              v : char);
var
  p : PslistEl;
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 : PslistEl;
                         v : char);
var
  p : PslistEl;
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 : PslistEl);
var
  p : PslistEl;
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 : PslistEl);
var
  p : PslistEl;
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 : PslistEl;
                   e : PslistEl);
var
  p : PslistEl;
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 : PslistEl; // adres początku listy
  e : PslistEl; // 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 slistEl
{
  slistEl * next;
  char data;
};

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned l_len(slistEl * 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(slistEl * 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(slistEl * & head,
                  char v)
{
  slistEl * p;

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

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

  e = new slistEl; // 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(slistEl * & head,
                     slistEl * e,
                     char v)
{
  slistEl * p = head;

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

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

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

// Procedura usuwa pierwszy element
//---------------------------------
void l_pop_front(slistEl * & head)
{
  slistEl * 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(slistEl * & head)
{
  slistEl * 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(slistEl * & head,
              slistEl * e)
{
  slistEl * 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()
{
  slistEl * L = NULL; // zawiera adres początku listy
  slistEl * 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function l_len(p As slistEl 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 slistEl 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 slistEl Ptr,_
                       v As String)

  Dim p As slistEl Ptr

  p = new slistEl  ' 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 slistEl Ptr,_
                      v As String)

  Dim As slistEl Ptr p,e

  e = New slistEl
  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 slistEl Ptr,_
                          e As slistEl Ptr,_
                          v As String)

  Dim p As slistEl Ptr

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

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

  Dim p As slistEl Ptr

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

' Procedura usuwa pierwszy element
'---------------------------------
Sub l_pop_front(ByRef head As slistEl Ptr)

  Dim p As slistEl 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 slistEl Ptr)

  Dim p As slistEl 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 slistEl Ptr,_
                   e As slistEl Ptr)

  Dim p As slistEl 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 slistEl Ptr
Dim e As slistEl 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 slistEl:

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

# klasa listy jednokierunkowej
class slistVar:

    # 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 = slistEl(v)
        p.next = self.head
        self.head = p

    # wstawianie na koniec
    def l_push_back(self,v):
        e = slistEl(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 = slistEl(v)
            p.next.next = e

    # wstawianie za e
    def l_insert_after(self,e,v):
        p = e.next
        e.next = slistEl(v)
        e.next.next = p;

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

    # usuwanie z tyłu
    def l_pop_back(self):
        p = self.head
        if p:
            if p.next:
                while p.next.next:
                    p = p.next
                del p.next
                p.next = None
            else:
                del p
                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
            del e

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

L = slistVar()

for i in range(ord('A'),ord('G')+1):
    L.l_push_back(chr(i))
L.l_print()

# Przechodzimy do elementu D

e = L.head

for i in range(ord('A'),ord('C')+1):
    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()

del L
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 

Wersja obiektowa

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
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Definicja typu obiektowego slistVar
//------------------------------------
  slistVar = object
    public
      head : PslistEl;  // 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 : PslistEl;
                                v : char);
      procedure l_insert_after(e : PslistEl;
                               v : char);
      procedure l_pop_front;
      procedure l_pop_back;
      procedure l_remove(e : PslistEl);
  end;

//------------------------
// Metody obiektu slistVar
//------------------------

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

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

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function slistVar.l_len : cardinal;
var
  c : cardinal;
  p : PslistEl;
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 slistVar.l_print;
var
  i : integer;
  p : PslistEl;
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 slistVar.l_push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura dołączania na koniec listy
//-------------------------------------
procedure slistVar.l_push_back(v : char);
var
  p,e : PslistEl;
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 slistVar.l_insert_before(e : PslistEl;
                                   v : char);
var
  p : PslistEl;
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 slistVar.l_insert_after(e : PslistEl;
                                  v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := e^.next;
  p^.data := v;
  e^.next := p;
end;

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

// Procedura usuwa ostatni element
//---------------------------------
procedure slistVar.l_pop_back;
var
  p : PslistEl;
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 slistVar.l_remove (e : PslistEl);
var
  p : PslistEl;
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 : slistVar; // obiekt listy jednokierunkowej
  e : PslistEl; // do wskazywania 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 slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slistVar
//------------------------------------
class slistVar
{
  public:
    slistEl * head;

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

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

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void slistVar::l_print()
{
  unsigned i;
  slistEl * 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 slistVar::l_push_front(char v)
{
  slistEl * p;

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

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

  e = new slistEl; // 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 slistVar::l_insert_before(slistEl * e,char v)
{
  slistEl * p = head;

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

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

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

// Procedura usuwa pierwszy element
//---------------------------------
void slistVar::l_pop_front()
{
  slistEl * 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 slistVar::l_pop_back()
{
  slistEl * p = head; // zapamiętujemy 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 slistVar::l_remove(slistEl * e)
{
  slistEl * 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()
{
  slistVar L;  // zawiera adres początku listy
  slistEl * 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slistVar
'-----------------------
Type slistVar
  head As slistEl 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 slistEl Ptr,_
                              v As String)
  Declare Sub l_insert_after(e As slistEl Ptr,_
                             v As String)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
  Declare Sub l_remove(e As slistEl Ptr)
End Type

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

Dim L As slistVar    ' zawiera adres początku listy
Dim e As slistEl Ptr ' do wskazywania elementów 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 element pierwszy i ostatni

L.l_remove(e)
L.l_pop_front()
L.l_pop_back()
L.l_print()

End

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

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

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slistVar.l_print()
  
  Dim i As UInteger
  Dim p As slistEl 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 slistVar.l_len As UInteger
  Dim c As UInteger
  Dim p As slistEl 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 slistVar.l_push_front(v As String)

  Dim p As slistEl Ptr

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

' Procedura dołączania na koniec listy
'-------------------------------------
Sub slistVar.l_push_back(v As String)

  Dim As slistEl Ptr p,e

  e = New slistEl
  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 slistVar.l_insert_before(e As slistEl Ptr,_
                             v As String)

  Dim p As slistEl Ptr

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

' Procedura dołączania za elementem e
'------------------------------------
Sub slistVar.l_insert_after(e As slistEl Ptr,_
                            v As String)

  Dim p As slistEl Ptr

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

' Procedura usuwa pierwszy element
'---------------------------------
Sub slistVar.l_pop_front()

  Dim p As slistEl 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

' Procedura usuwa ostatni element
'--------------------------------
Sub slistVar.l_pop_back()

  Dim p As slistEl 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 slistVar.l_remove(e As slistEl Ptr)

  Dim p As slistEl 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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.