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, wykonuj kroki K02...K03	w pętli przechodzimy przez 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

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

Lista kroków:

K01:	c ← 0	zerujemy licznik
K02:	Dopóki p ≠ nil, wykonuj kroki K03...K04	w pętli przechodzimy przez 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_size ( 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_size := c;
end;

C++

unsigned l_size ( slistEl * p )
{
  unsigned c = 0; // zerujemy licznik

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

  return c;
}

Basic

Function l_size ( 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_size = c
End Function

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.

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:	Utwórz nowy element listy
K02:	p ← adres nowego elementu
K03:	( p→data ) ← v	umieszczamy dane w elemencie
K04:	( p→next ) ← head	następnikiem będzie bieżący pierwszy element listy
K05:	head ← p	ustawiamy początek listy na nowy element
K06:	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

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, to zakończ	zakończ, jeśli lista jest pusta
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 : 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

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_size ( p : PslistEl ) : cardinal;
var
  c : cardinal;
begin
  c := 0;
  while p <> nil do
  begin
    inc ( c );
    p := p^.next;
  end;
  l_size := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure l_printl ( p : PslistEl );
var
  i : cardinal;
begin
  writeln ( 'Number of elements : ', l_size ( 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_printl ( L );
  l_pop_front ( L );
  l_pop_front ( L );
  l_printl ( 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_size ( slistEl * p )
{
  unsigned c = 0;

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

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

  cout << "Number of elements : " << l_size ( 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_printl ( L );
  l_pop_front ( L );
  l_pop_front ( L );
  l_printl ( 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_size ( p As slistEl Ptr ) As UInteger

  Dim c As UInteger

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

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub l_printl ( p As slistEl Ptr )
  
  Dim i As UInteger
  
  Print "Number of elements : ";l_size ( 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_printl ( L )

l_pop_front ( L )
l_pop_front ( L )
l_printl ( 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

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 ).
	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:	Utwórz nowy element
K02:	e ← adres nowego elementu
K03:	( e→next ) ← nil	inicjujemy pola nowego elementu
K04:	( e→data ) ← v
K05;	p ← head	w p ustawiamy początek listy
K06:	Jeśli p ≠ nil, to idź do kroku K09	czy lista jest pusta?
K07:	head ← e	jeśli tak, to nowy element będzie pierwszym elementem listy
K08:	Zakończ
K09:	Dopóki ( p→next ) ≠ nil, wykonuj p ← ( p→next )	inaczej przechodzimy do ostatniego elementu listy
K10:	( p→next ) ← e	dołączamy nowy element za ostatnim na liście
K11:	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

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! )..
	Odłączony element usuwamy z listy. Lista pozostaje pusta. 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, to zakończ	jeśli lista jest pusta, kończymy
K03:	Jeśli ( p→next ) ≠ nil, to idź do kroku K07	sprawdzamy, czy lista 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, wykonuj p ← ( p→next )	idziemy do przedostatniego elementu
K08:	Usuń z pamięci element wskazywany przez ( p→next )	usuwamy następny element, czyli ostatni
K09:	( p→next ) ← 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

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.
	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 poprzednika elementu wybranego. W ten sposób nowy element stanie się elementem następnym poprzednika. Lista chwilowo zostanie rozdzielona.
	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

–

wskazania elementu listy

Lista kroków:

K01:	p ← head	pobieramy do p adres początku listy
K02:	Jeśli p ≠ e, to idź do kroku K05	sprawdzamy, czy e nie jest pierwszym elementem listy
K03:	Wstaw nowy element na początku listy
K04:	Zakończ
K05;	Dopóki ( p→next ) ≠ e, wykonuj p ← ( p→next )	przechodzimy do elementu poprzedzającego e
K06:	Utwórz nowy element
K07:	( p→next ) ← adres nowego elementu	nowy element wstawiamy za element poprzedzający
K08:	( ( p→next )→next ) ← e	inicjujemy nowy element
K09:	( ( p→next )→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

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.
	Tworzymy dynamicznie w pamięci nowy element.
	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:	Utwórz nowy element
K02:	p ← adres nowego elementu
K03:	( p→next ) ← ( e→next )	następnym elementem za nowym będzie następny element za e
K04:	( p→data ) ← v
K05;	( e→next ) ← p	nowy element wstawiamy za e
K06:	Zakończ

Pascal

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

C++

void l_insert_after ( slistEl * e, char v )
{
  slistEl * p = new slistEl;

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

Basic

Sub 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

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.

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

Lista kroków:

K01:	Jeśli head ≠ e, to idź do kroku K04	sprawdzamy, czy usuwany element jest pierwszym na liście
K02:	Usuń pierwszy element listy	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, wykonuj p ← ( p→next )	w p ustawiamy adres elementu 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 : 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

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 końcu 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_size ( 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_size := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure l_printl ( p : PslistEl );
var
  i : integer;  // licznik elementów
begin
  writeln ( 'Number of elements : ', l_size ( p ) );

  i := 1;       // licznik ustawiamy na 1

  // W petli przechodzimy przez kolejne elementy listy
  // i wyświetlamy zawartość ich pola danych

  while p <> nil do
  begin
    writeln ( 'Element #', i, '  data = ', p^.data );
    inc ( i );  // Zwiększamy licznik elementów o 1
    p := p^.next; // Przechodzimy do następnego elementu listy
  end;
  writeln;      // Odstęp
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
  new ( p );
  p^.next := e^.next;
  p^.data := v;
  e^.next := p;
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; // zawiera adres początku listy
  e : PslistEl; // do wskazywania elementów listy
  i : char;

begin
  L := nil;

  for i := 'A' to 'G' do l_push_back ( L, i );
  l_printl ( 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_printl ( L );

  // Usuwamy element D oraz element pierwszy i ostatni

  l_remove ( L, e );
  l_pop_front ( L );
  l_pop_back ( L );
  l_printl ( 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_size ( 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_printl ( slistEl * p )
{
  unsigned i;    // licznik elementów

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

  // W petli przechodzimy przez kolejne elementy listy
  // i wyświetlamy zawartość ich pola danych

  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 = new slistEl;

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

// 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; // 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 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_printl ( 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_printl ( L );

  // Usuwamy element D oraz element pierwszy i ostatni

  l_remove ( L, e );
  l_pop_front ( L );
  l_pop_back ( L );
  l_printl ( 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_size ( 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_size = c
End Function

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

  i = 1 ' licznik ustawiamy na 1

  ' W pętli przechodzimy przez kolejne elementy listy
  ' i wyświetlamy zawartość ich pola danych

  While p
    Print "Element #";i;"  data = ";p->data
    i += 1       ' zwiększamy licznik elementów o 1
    p = p->next  ' przechodzimy do następnego elementu listy
  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  ' 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

' 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 = new slistEl
  p->next = e->next
  p->data = v
  e->next = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
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

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

L = 0

For i = Asc ( "A" ) To Asc ( "G" )
  l_push_back ( L, Chr ( i ) )
Next
l_printl ( 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_printl ( L )

' Usuwamy element D oraz element pierwszy i ostatni

l_remove ( L, e )
l_pop_front ( L )
l_pop_back ( L )
l_printl ( 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

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++ i Basic, 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 slist
//---------------------------------
  slist = object
    public
      head : PslistEl;  // początek listy

      constructor init;
      destructor destroy;
      function size : cardinal;
      procedure printl;
      procedure push_front ( v : char );
      procedure push_back ( v : char );
      procedure insert_before ( e : PslistEl; v : char );
      procedure insert_after ( e : PslistEl; v : char );
      procedure pop_front;
      procedure pop_back;
      procedure remove ( e : PslistEl );
  end;

//---------------------
// Metody obiektu slist
//---------------------

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

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure slist.printl;
var
  i : integer;
  p : PslistEl;
begin
  writeln ( 'Number of elements : ', size );
  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 slist.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 slist.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 slist.insert_before ( e : PslistEl; v : char );
var
  p : PslistEl;
begin
  p := head;
  if p = e then 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 slist.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 slist.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 slist.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 slist.remove ( e : PslistEl );
var
  p : PslistEl;
begin
  if head = e then 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 : slist;    // obiekt listy jednokierunkowej
  e : PslistEl; // do wskazywania elementów listy
  i : char;

begin
  L.init;  // inicjujemy obiekt

  for i := 'A' to 'G' do L.push_back ( i );
  L.printl;

  // Przechodzimy do elementu o wartości D

  e := L.head;

  for i := 'A' to 'C' do e := e^.next;

  // Przed elementem D umieszczamy +

  L.insert_before ( e, '+' );

  // Za elementem D umieszczamy *

  L.insert_after ( e, '*' );
  L.printl;

  // Usuwamy element D oraz element pierwszy i ostatni

  L.remove ( e );
  L.pop_front;
  L.pop_back;
  L.printl;

  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 slist
//---------------------------------
class slist
{
  public:
    slistEl * head;

    slist( );  // konstruktor
    ~slist( ); // destruktor
    unsigned size( );
    void printl( );
    void push_front ( char v );
    void push_back ( char v );
    void insert_before ( slistEl * e, char v );
    void insert_after ( slistEl * e, char v );
    void pop_front( );
    void pop_back( );
    void remove ( slistEl * e );
};

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

// Destruktor listy
//-----------------
slist::~slist( )
{
  while( head ) pop_front( );
}

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

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

  cout << "Number of elements : " << size( ) << 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 slist::push_front ( char v )
{
  slistEl * p;

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

// Procedura dołączania na koniec listy
//---------------------------------------
void slist::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 slist::insert_before ( slistEl * e, char v )
{
  slistEl * p = head;

  if( p == e ) 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 slist::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 slist::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 slist::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 slist::remove ( slistEl * e )
{
  slistEl * p;

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

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

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

  for( i = 'A'; i <= 'G'; i++ ) L.push_back ( i );
  L.printl( );

  // Przechodzimy do elementu o wartości D

  e = L.head;

  for( i = 'A'; i <= 'C'; i++ ) e = e->next;

  // Przed elementem D umieszczamy +

  L.insert_before ( e, '+' );

  // Za elementem D umieszczamy *

  L.insert_after ( e, '*' );

  L.printl( );

  // Usuwamy element D oraz element pierwszy i ostatni

  L.remove ( e );
  L.pop_front( );
  L.pop_back( );
  L.printl( );

  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 slist
'------------------------------
Type slist
  head As slistEl Ptr
  
  Declare Constructor( )
  Declare Destructor( )
  Declare Sub printl( )
  Declare Function size( ) As UInteger
  Declare Sub push_front ( v As String )
  Declare Sub push_back ( v As String )
  Declare Sub insert_before ( e As slistEl Ptr, v As String )
  Declare Sub insert_after ( e As slistEl Ptr, v As String )
  Declare Sub pop_front( )
  Declare Sub pop_back( )
  Declare Sub remove ( e As slistEl Ptr )
End Type

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

Dim L As slist       ' 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.push_back ( Chr ( i ) )
Next

L.printl( )

' Przechodzimy do elementu o wartości D

e = L.head
For i = 1 To 3
  e = e->next
Next

' Przed elementem D umieszczamy +

L.insert_before ( e, "+" )

' Za elementem D umieszczamy *

L.insert_after ( e, "*" )
L.printl( )

' Usuwamy element D oraz element pierwszy i ostatni

L.remove ( e )
L.pop_front( )
L.pop_back( )
L.printl( )

End

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

' Destruktor listy
'-----------------
Destructor slist( )
  While head
    pop_front( )
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slist.printl( )
  
  Dim i As UInteger
  Dim p As slistEl Ptr = head
  
  Print "Number of elements : ";size( )
  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 slist.size( ) As UInteger

  Dim c As UInteger
  Dim p As slistEl Ptr = head

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

' Procedura dołączania na początek listy
'---------------------------------------
Sub slist.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 slist.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 slist.insert_before ( e As slistEl Ptr, v As String )

  Dim p As slistEl Ptr

  p = head
  If p = e Then
    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 slist.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 slist.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 slist.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 slist.remove ( e As slistEl Ptr )

  Dim p As slistEl Ptr

  If head = e Then
    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:

Typ elementu listy

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