Operacje na listach dwukierunkowych


Tematy pokrewne   Podrozdziały
Listy
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Operacje na listach cyklicznych jednokierunkowych
Liniowe przeszukiwanie listy
Przeszukiwanie liniowe z wartownikiem listy dwukierunkowej
Wyszukiwanie największego/najmniejszego elementu listy
Zliczanie elementów listy
Usuwanie z listy duplikatów
Odwracanie listy jednokierunkowej
Podział listy jednokierunkowej na dwie listy
Scalanie dwóch list posortowanych
Sortowanie listy jednokierunkowej przez scalanie
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej
Sortowanie szybkie listy dwukierunkowej
Samoorganizujące się listy
Haszowanie z wykorzystaniem list jednokierunkowych
Zbiory rozłączne – implementacja listowa
  Przejście przez listę
Liczba elementów listy
Dodawanie elementu na początku listy
Dodawanie elementu na koniec listy
Dodawanie nowego elementu przed wybranym elementem listy
Dodawanie nowego elementu za elementem wybranym
Usuwanie wybranego elementu listy
Usuwanie elementu z początku listy
Usuwanie elementu z końca listy
Wersja obiektowa

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 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ł.

 

Typ elementu listy oraz zmiennej obsługującej listę

 

Lazarus Code::Blocks Free Basic
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : typ_danych;
  end;

  dlistVar = record
    head  : PdlistEl;
    tail  : PdlistEl;
    count : cardinal;
  end;
struct dlistEl
{
  dlistEl * next, * prev;
  typ_danych data;
};

struct dlistVar
{
  dlistEl * head, * tail;
  unsigned count;
};
Type dlistEl
  next As dlistEl Ptr
  prev As dlistEl Ptr
  data As typ_danych
End Type

Type dlistVar
  head  As dlistEl Ptr
  tail  As dlistEl Ptr
  count As UInteger
End Type

 

Przejście przez listę

W porównaniu z listami jednokierunkowymi, opisanymi w poprzednim rozdziale, listy dwukierunkowe są bardziej skomplikowane, ponieważ każdy ich element posiada dodatkowe pole prev. Pole to wskazuje element poprzedni na liście. Zatem listy tego typu można przechodzić w obu kierunkach. Z drugiej strony ta możliwość skraca czas wykonania wielu operacji na liście, gdzie wymagany jest element poprzedzający w stosunku do danego. W przypadku listy jednokierunkowej element ten znajdowany był za pomocą przejścia od początku listy – w liście dwukierunkowej mamy go danego bezpośrednio poprzez pole prev.

Zasada przechodzenia listy dwukierunkowej jest identyczna jak przy listach jednokierunkowych. Potrzebujemy wskaźnika, który będzie wskazywał poszczególne elementy listy. Wskazywany element przetwarzamy, po czym przechodzimy do następnego poprzez pole next lub do poprzedniego poprzez pole prev. Operację przejścia kontynuujemy dotąd, aż wskaźnik przyjmie wartość 0 (ostatni element listy ma w polu next wartość 0, pierwszy element listy ma w polu prev wartość 0 – zatem wyjście z ostatniego lub z pierwszego elementu poprzez next/prev skutkuje adresem zerowym).

 

Algorytm przechodzenia przez listę dwukierunkową

Wejście
L  –  zmienna obsługująca listę
Wyjście:

Przejście przez wszystkie elementy listy od pierwszego do ostatniego lub od ostatniego do pierwszego

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków : przejście w przód
K01: p L.head ; w p ustawiamy adres pierwszego elementu listy
K02: Dopóki p ≠ nil, wykonuj kroki K03...K05 ; w pętli przechodzimy przez kolejne elementy listy
K03:     Przetwarzaj element wskazywany przez p  
K04:     p ← (pnext) ; w p umieść zawartość pola next elementu wskazywanego przez p
K05: Zakończ  
Lista kroków : przejście wstecz
K01: p L.tail ; w p ustawiamy adres ostatniego elementu listy
K02: Dopóki p ≠ nil, wykonuj kroki K03...K05 ; w pętli przechodzimy przez kolejne elementy listy
K03:     Przetwarzaj element wskazywany przez p  
K04:     p ← (pprev) ; w p umieść zawartość pola prev elementu wskazywanego przez p
K05: Zakończ  

 

 

Lazarus
p := L.head;
while p <> nil do
begin
  ...
  p := p^.next;
end;
p := L.tail;
while p <> nil do
begin
  ...
  p := p^.prev;
end;
Code::Blocks
p = L.head;
while(p)
{
  ...
  p = p->next;
}
p = L.tail;
while(p)
{
  ...
  p = p->prev;
}
Free Basic
p = L.head
While p
  ...
  p = p->next
Wend
p = L.tail
While p
  ...
  p = p->prev
Wend

 

Liczba elementów listy

Dla listy dwukierunkowej nie musimy posiadać osobnego algorytmy wyznaczania liczby elementów, ponieważ pole count zmiennej obsługującej listę przechowuje bezpośrednio tę informację.

 

Dodawanie elementu na początku listy

 

Naszym zadaniem jest dodanie nowego elementu na początku listy dwukierunkowej.

Tworzymy nowy element dynamicznie w pamięci (na rysunku w kolorze zielonym), umieszczamy w nim dane, a w polu prev zapisujemy adres zerowy, ponieważ pierwszy element listy nie posiada poprzednika.

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

W polu head umieszczamy adres nowego elementu, który teraz staje się pierwszym elementem listy.

Zwiększamy pole count o 1.

Teraz musimy zapewnić komunikację w drugą stronę. Jeśli istnieje następnik dodanego elementu, to w polu prev następnika umieszczamy adres nowego elementu. Pozwoli to przejść z następnika do pierwszego elementu. Lista staje się kompletna.

Jeśli następnik nie istnieje, to dodawaliśmy element do pustej listy. W takim przypadku w polu tail należy również wprowadzić adres nowego elementu – lista stanie się listą jednoelementową.

 

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

Wejście
L  –  zmienna obsługująca listę
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  
K02: p ← adres nowego elementu  
K03: (pdata) ← v ; umieszczamy dane w nowym elemencie
K04: (pprev) ← nil '; pierwszy element nie posiada poprzednika
K05: (pnext) ← L.head ; następnikiem będzie obecny pierwszy element listy
K06: L.headp ; dołączamy element do początku listy
K07 L.countL.count + 1 ; zwiększamy licznik elementów o 1
K08: Jeśli (pnext) ≠ nil, to ((pnext)→prev) ← p
inaczej L.tailp
; jeśli istnieje następnik, to jego poprzednikiem czynimy nowy element
; inaczej adres nowego elementu umieszczamy w polu tail
K09: Zakończ  

 

Lazarus
procedure l_push_front(var L : dlistVar; v : char);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data := v;
  p^.prev := nil;
  p^.next := L.head;
  L.head  := p;
  inc(L.count);
  if p^.next <> nil then p^.next^.prev := p
  else L.tail := p;
end;
Code::Blocks
void l_push_front(dlistVar & L, char v)
{
  dlistEl * p;

  p = new dlistEl;   // tworzymy nowy element
  p->data = v;
  p->prev = NULL;
  p->next = L.head;
  L.head  = p;
  L.count++;
  if(p->next) p->next->prev = p;
  else L.tail = p;
}
Free Basic
Sub l_push_front(ByRef L As dlistVar, v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl   ' tworzymy nowy element
  p->data = v
  p->prev = 0
  p->next = L.head
  L.head  = p
  L.count += 1
  If p->next Then
    p->next->prev = p
  Else
    L.tail = p
  End If
End Sub

 

Dodawanie elementu na koniec listy

Dodawanie elementu na koniec listy jest symetryczne z dodawaniem na początek. Musi tak być, ponieważ lista dwukierunkowa jest strukturą symetryczną.

Tworzymy dynamicznie w pamięci nowy element (oznaczony na rysunku kolorem zielonym) i umieszczamy w nim dane. W polu next wstawiamy adres zerowy – ostatni element nie posiada następnika.

Do pola prev kopiujemy zawartość pola tail ze zmiennej obsługującej listę. Poprzednikiem nowego elementu stanie się obecny ostatni element listy.

W polu tail umieszczamy adres nowego elementu. Nowy element staje się ostatnim elementem listy

Zwiększamy o 1 zawartość pola count.

Jeśli istnieje poprzednik nowego elementu (pole prev ma wartość różną od zera), to w poprzedniku ustawiamy pole next na adres nowego elementu – lista zostanie połączona w całość.

Jeśli poprzednik nie istnieje, to lista była pusta, a teraz zawiera jeden element – ten dodany przez nas. W takim przypadku adres nowego elementu należy wprowadzić również do pola head. Lista stanie się jednoelementowa, a dodany element będzie zarówno pierwszym jak i ostatnim jej elementem.

 

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

Wejście
L  –  zmienna obsługująca listę
v   wartość wprowadzana do elementu
Wyjście:

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

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: Utwórz nowy element  
K02: p ← adres nowego elementu  
K03: (pdata) ← v ; umieszczamy dane w nowym elemencie
K04: (pnext) ← nil ; ostatni element nie będzie posiadał następnika
K05; (pprev) ← L.tail ; poprzednikiem będzie obecny ostatni element
K06: L.tailp ; nowy element staje się ostatnim na liście
K07: L.countL.count + 1 ; zwiększamy o 1 licznik elementów listy
K08: Jeśli (pprev) ≠ nil, to ((pprev)→next) ← p
inaczej L.head ← p
; jeśli istnieje poprzednik, to nowy element będzie jego następnikiem
; inaczej adres nowego elementu umieszczamy w polu head
K09: Zakończ  

 

Lazarus
procedure l_push_back(var L : dlistVar; v : char);
var
  p : PdlistEl;
begin
  new(p);
  p^.data := v;
  p^.next := nil;
  p^.prev := L.tail;
  L.tail  := p;
  inc(L.count);
  if p^.prev <> nil then p^.prev^.next := p
  else L.head := p;
end;
Code::Blocks
void l_push_back(dlistVar & L, char v)
{
  dlistEl * p;

  p = new dlistEl;
  p->data = v;
  p->next = NULL;
  p->prev = L.tail;
  L.tail  = p;
  L.count++;
  if(p->prev) p->prev->next = p;
  else L.head = p;
}
Free Basic
Sub l_push_back(ByRef L As dlistVar, v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  p->data = v
  p->next = 0
  p->prev = L.tail
  L.tail  = p
  L.count += 1
  If p->prev Then
    p->prev->next = p
  Else
    L.head = p
  End If
End Sub

 

Dodawanie nowego elementu przed wybranym elementem listy

Jeśli wybrany element (na rysunku zaznaczony kolorem jasnoniebieskim) jest pierwszym elementem listy, to zadanie sprowadza się do dodania nowego elementu na początku listy, co opisaliśmy wcześniej w tym rozdziale.

Załóżmy, że wybrany element nie jest pierwszym elementem listy. Musi wtedy posiadać poprzednik (na rysunku zaznaczyliśmy go kolorem żółtym). Dostęp do poprzednika mamy poprzez pole prev elementu wybranego.

Tworzymy dynamicznie w pamięci nowy element (na rysunku w kolorze zielonym). Umieszczamy w nim dane, pole next ustawiamy na adres elementu wybranego, a pole prev na adres poprzednika elementu wybranego (zawartość pola prev w elemencie wybranym).

Zwiększamy o 1 licznik elementów count w zmiennej obsługującej listę.

Pola next w poprzedniku oraz prev w elemencie wybranym ustawiamy na adres nowego elementu. Teraz nowy element stanie się częścią składową listy i będzie umieszczony w niej przed elementem wybranym.

 

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

Wejście
L  –  zmienna obsługująca listę
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: Jeśli eL.head, to idź do K04 ; sprawdzamy, czy wybrany element nie jest pierwszym elementem listy
K02: Wstaw nowy element na początek listy ; jeśli jest, to wykorzystujemy algorytm wstawiania na początek listy
K03: Zakończ  
K04: Utwórz nowy element  
K05; p ← adres nowego elementu  
K06: (pdata) ← v ; umieszczamy dane w nowym elemencie
K07: (pnext) ← e ; następnikiem będzie element wybrany
K08: (pprev) ← (eprev) ; poprzednikiem będzie poprzednik elementu wybranego
K09: L.countL.count + 1 ; zwiększamy licznik elementów listy
K10: ((eprev)→next) ← p ; następnikiem poprzednika elementu wybranego będzie nowy element
K11: (eprev) ← p ; poprzednikiem elementu wybranego będzie nowy element
K12: Zakończ  

 

Lazarus
procedure l_insert_before(var L : dlistVar; e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = L.head then l_push_front(L,v)
  else
  begin
    new(p);
    p^.data := v;
    p^.next := e;
    p^.prev := e^.prev;
    inc(L.count);
    e^.prev^.next := p;
    e^.prev := p;
  end;
end;
Code::Blocks
void l_insert_before(dlistVar & L, dlistEl * e, char v)
{
  dlistEl * p;

  if(e == L.head) l_push_front(L,v);
  else
  {
    p = new dlistEl;
    p->data = v;
    p->next = e;
    p->prev = e->prev;
    L.count++;
    e->prev->next = p;
    e->prev = p;
  }
}
Free Basic
Sub l_insert_before(ByRef L As dlistVar, e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = L.head Then
    l_push_front(L,v)
  Else
    p = New dlistEl
    p->data = v
    p->next = e
    p->prev = e->prev
    L.count += 1
    e->prev->next = p
    e->prev = p
  End If
End Sub

 

Dodawanie nowego elementu za elementem wybranym

Wstawianie za wybranym elementem jest symetryczne do wstawiania przed wybranym elementem.

Jeśli wybrany element jest ostatnim elementem listy (w polu next ma adres zerowy), to wykorzystujemy opisany wcześniej algorytm wstawiania na koniec listy.

Załóżmy, że wybrany element nie jest ostatni na liście. Wtedy posiada następnik (na rysunku w kolorze żółtym).

Tworzymy nowy element (na rysunku w kolorze zielonym), wprowadzamy do niego dane, w polu next umieszczamy adres następnika z pola next elementu wybranego, a w polu prev umieszczamy adres elementu wybranego.

Zwiększamy licznik elementów count o 1.

Adres nowego elementu umieszczamy w polach prev następnika oraz next elementu wybranego. Nowy element stanie się częścią listy i będzie umieszczony w niej za elementem wybranym.

 

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

Wejście
L  –  zmienna obsługująca listę
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: Jeśli eL.tail, to idź do K04 ; sprawdzamy, czy e nie jest ostatnim elementem listy
K02: Wstaw nowy element na koniec listy ; jeśli jest ostatnim elementem listy, wykorzystujemy algorytm wstawiania na koniec listy
K03: Zakończ  
K04: Utwórz nowy element  
K05; p ← adres nowego elementu  
K06: (pdata) ← v ; umieszczamy dane w nowym elemencie
K07: (pnext) ← (enext) ; następnikiem będzie następnik elementu wybranego
K08: (pprev) ← e ; poprzednikiem będzie element wybrany
K09: L.countL.count + 1 ; zwiększamy licznik elementów
K10: ((pnext)→prev) ← p ; ustawiamy p jako poprzednik następnika
K11: (enext) ← p ; ustawiamy p jako następnik elementu wybranego
K12: Zakończ  

 

Lazarus
procedure l_insert_after(var L : dlistVar; e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = L.tail then l_push_back(L,v)
  else
  begin
    new(p);
    p^.data := v;
    p^.next := e^.next;
    p^.prev := e;
    inc(L.count);
    e^.next^.prev := p;
    e^.next := p;
  end;
end;
Code::Blocks
void l_insert_after(dlistVar & L, dlistEl * e, char v)
{
  dlistEl * p;

  if(e == L.tail) l_push_back(L,v);
  else
  {
    p = new dlistEl;
    p->data = v;
    p->next = e->next;
    p->prev = e;
    L.count++;
    e->next->prev = p;
    e->next = p;
  }
}
Free Basic
Sub l_insert_after(ByRef L As dlistVar, e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = L.tail Then
    l_push_back(L,v)
  Else
    p = New dlistEl
    p->data = v
    p->next = e->next
    p->prev = e
    L.count += 1
    e->next->prev = p
    e->next = p
  End If
End Sub

 

Usuwanie wybranego elementu listy

Zmniejszamy o 1 pole count.

Usuwany element oznaczyliśmy kolorem czerwonym na rysunku.

Element ten może znajdować się na początku listy, gdzieś w środku lub na jej końcu. Nasz algorytm sprawdzi każdą z tych trzech możliwości.

Jeśli istnieje poprzednik usuwanego elementu (kolor żółty), to w jego polu next umieszczamy zawartość pola next usuwanego elementu, czyli adres następnika.

W przeciwnym razie wybrany element jest pierwszym elementem listy. W takim przypadku w head umieszczamy zawartość pola next usuwanego elementu, czyli adres następnika. Zwróć uwagę, że w przypadku listy jednoelementowej do pola head trafi adres zerowy.

Jeśli istnieje następnik usuwanego elementu (kolor zielony), to w jego polu prev umieszczamy zawartość pola prev usuwanego elementu, czyli adres poprzednika.

W przeciwnym razie wybrany element jest ostatnim elementem listy. W polu tail umieszczamy zawartość pola prev. Zwróć uwagę, że w przypadku listy jednoelementowej do pola tail trafi adres zerowy.

W obu przypadkach usuwany element staje się odłączony od listy

Usuwamy element wybrany z pamięci.

 

Algorytm usuwania wybranego elementu listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
e  – wskazanie elementu listy do usunięcia
Wyjście:

Lista bez elementu wskazywanego przez e.

Lista kroków:
K01: L.countL.count - 1 ; zmniejszamy licznik elementów listy
K02: Jeśli (eprev) ≠ nil, to ((eprev)→next) ← (enext)
inaczej L.head ← (enext)
; następnikiem poprzednika będzie następnik usuwanego elementu
; jeśli poprzednika nie ma, modyfikujemy head
K03: Jeśli (enext) ≠ nil, to ((enext)→prev) ← (eprev)
inaczej L.tail ← (eprev)
; poprzednikiem następnika będzie poprzednik usuwanego elementu
; jeśli następnika nie ma, to modyfikujemy tail
K04: Usuń element e  
K05: Zakończ  

 

Lazarus
procedure l_remove(var L : dlistVar; e : PdlistEl);
begin
  dec(L.count);
  if e^.prev <> nil then e^.prev^.next := e^.next
  else L.head := e^.next;
  if e^.next <> nil then e^.next^.prev := e^.prev
  else L.tail := e^.prev;
  dispose(e);
end;
Code::Blocks
void l_remove(dlistVar & L, dlistEl * e)
{
  L.count--;
  if(e->prev) e->prev->next = e->next;
  else        L.head = e->next;
  if(e->next) e->next->prev = e->prev;
  else        L.tail = e->prev;
  delete e;
}
Free Basic
Sub l_remove(ByRef L As dlistVar, e As dlistEl Ptr)
  L.count -= 1
  If e->prev Then
    e->prev->next = e->next
  Else
    L.head = e->next
  End If
  If e->next Then
    e->next->prev = e->prev
  Else
    L.tail = e->prev
  End If
  Delete e
End Sub

 

Usuwanie elementu z początku listy

Nie musimy tworzyć osobnego algorytmu, wykorzystamy algorytm usuwania wybranego elementu listy.

 

Algorytm usuwania elementu z początku listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
Wyjście:

Lista bez pierwszego elementu.

Lista kroków:
K01: Jeśli L.count = 0, to zakończ ; lista jest pusta i nie ma co usuwać
K02 Usuń z listy element wskazywany przez L.head  
K03: Zakończ ; jeśli lista zawiera więcej niż 1 element, przejdź dalej

 

Lazarus
procedure l_pop_front(var L : dlistVar);
begin
  if L.count > 0 then l_remove(L,L.head);
end;
Code::Blocks
void l_pop_front(dlistVar & L)
{
  if(L.count) l_remove(L,L.head);
}
Free Basic
Sub l_pop_front(ByRef L As dlistVar)
  If L.count > 0 Then l_remove(L,L.head)
End Sub

 

Usuwanie elementu z końca listy

Tutaj również wykorzystujemy algorytm ogólny.

 

Algorytm usuwania elementu z końca listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
Wyjście:

Lista bez ostatniego elementu.

Lista kroków:
K01: Jeśli L.count = 0, to zakończ ; lista jest pusta i nie ma co usuwać
K02 Usuń element wskazywany przez L.tail  
K03: Zakończ  

 

Lazarus
procedure l_pop_back(var L : dlistVar);
begin
  if L.count > 0 then l_remove(L,L.tail);
end;
Code::Blocks
void l_pop_back(dlistVar & L)
{
  if(L.count) l_remove(L,L.tail);
}
Free Basic
Sub l_pop_back(ByRef L As dlistVar)
  If L.count > 0 Then l_remove(L,L.tail)
End Sub

 

Program

Ważne:

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.

 

To jest program testowy, który działa następująco:
  • []  – tworzy pustą listę literek alfabetu
  • [C B A] – na początku listy dołącza kolejno litery A,B,C. Na liście znajdą się one w odwrotnej kolejności (dlaczego?).
  • [C B A D E F] – na końcu listy dołącza kolejno litery D,E,F. Tym razem kolejność liter zostanie zachowana.
  • [C B A D E # F] – przed ostatnim elementem dodaje znak #.
  • [C % B A D E # F] – za pierwszym elementem dodaje znak %.
  • [% B A D E # F] – usuwa pierwszy element.
  • [% B A D E #] – usuwa ostatni element
  • [% B D E #] – usuwa trzeci element

Na wydruku pierwsza liczba oznacza ilość elementów listy.

 

Lazarus
// Program testowy dla list dwukierunkowych
// Data: 14.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------------------

program dlist_test;

// Definicje typów
//----------------
type

  PdlistEl = ^dlistEl;  // wskaźnik do elementów listy

  // Element listy
  //--------------
  dlistEl = record
    next : PdlistEl;   // następnik
    prev : PdlistEl;   // poprzednik
    data : char;
  end;

  // Zmienna obsługująca listę
  //--------------------------
  dlistVar = record
    head  : PdlistEl;  // początek listy
    tail  : PdlistEl;  // koniec listy
    count : cardinal; // licznik elementów
  end;

//-------------------------------------------------
// Procedury i funkcje obsługi listy dwukierunkowej
//-------------------------------------------------

// Procedura inicjuje pola zmiennej listy
//---------------------------------------
procedure l_init(var L : dlistVar);
begin
  L.head  := nil;
  L.tail  := nil;
  L.count := 0;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure l_printl(var L : dlistVar);
var
  p : PdlistEl;
begin
  write(L.count:3,' : [');
  p := L.head;
  while p <> NIL do
  begin
    write(' ',p^.data);
    p := p^.next;
  end;
  writeln(' ]');
  writeln;
end;

// Procedura dodaje nowy element na początek listy
//------------------------------------------------
procedure l_push_front(var L : dlistVar; v : char);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data := v;
  p^.prev := nil;
  p^.next := L.head;
  L.head  := p;
  inc(L.count);
  if p^.next <> nil then p^.next^.prev := p
  else L.tail := p;
end;

// Procedura dodaje nowy element na koniec listy
//----------------------------------------------
procedure l_push_back(var L : dlistVar; v : char);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data := v;
  p^.next := nil;
  p^.prev := L.tail;
  L.tail  := p;
  inc(L.count);
  if p^.prev <> nil then p^.prev^.next := p
  else L.head := p;
end;

// Procedura dodaje nowy element przed wybranym
//---------------------------------------------
procedure l_insert_before(var L : dlistVar; e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = L.head then l_push_front(L,v)
  else
  begin
    new(p);
    p^.data := v;
    p^.next := e;
    p^.prev := e^.prev;
    inc(L.count);
    e^.prev^.next := p;
    e^.prev := p;
  end;
end;

// Procedura dodaje nowy element za wybranym
//------------------------------------------
procedure l_insert_after(var L : dlistVar; e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = L.tail then l_push_back(L,v)
  else
  begin
    new(p);
    p^.data := v;
    p^.next := e^.next;
    p^.prev := e;
    inc(L.count);
    e^.next^.prev := p;
    e^.next := p;
  end;
end;

// Procedura usuwa wybrany element z listy
//----------------------------------------
procedure l_remove(var L : dlistVar; e : PdlistEl);
begin
  dec(L.count);
  if e^.prev <> nil then e^.prev^.next := e^.next
  else L.head := e^.next;
  if e^.next <> nil then e^.next^.prev := e^.prev
  else L.tail := e^.prev;
  dispose(e);
end;

// Procedura usuwa element z początku listy
//-----------------------------------------
procedure l_pop_front(var L : dlistVar);
begin
  if L.count > 0 then l_remove(L,L.head);
end;

// Procedura usuwa element z końca listy
//--------------------------------------
procedure l_pop_back(var L : dlistVar);
begin
  if L.count > 0 then l_remove(L,L.tail);
end;

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

var

  L : dlistVar;
  i : char;

begin
  l_init(L);  // inicjujemy zmienną obsługi listy

  for i := 'A' to 'C' do l_push_front(L,i); // [C B A]
  l_printl(L);
  for i := 'D' to 'F' do l_push_back(L,i);  // [C B A D E F]
  l_printl(L);
  l_insert_before(L,L.tail,'#');            // [C B A D E # F]
  l_printl(L);
  l_insert_after(L,L.head,'%');             // [C % B A D E # F]
  l_printl(L);
  l_pop_front(L);                           // [% B A D E # F]
  l_printl(L);
  l_pop_back(L);                            // [% B A D E #]
  l_printl(L);
  l_remove(L,L.head^.next^.next);           // [% B D E #]
  l_printl(L);

end.
Code::Blocks
// Program testowy dla list dwukierunkowych
// Data: 14.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicje typów
//----------------

// Element listy
//--------------
struct dlistEl
{
  dlistEl * next;   // następnik
  dlistEl * prev;   // poprzednik
  char data;
};

// Zmienna obsługująca listę
//--------------------------
struct dlistVar
{
  dlistEl * head;  // początek listy
  dlistEl * tail;  // koniec listy
  unsigned count; // licznik elementów
};

//-----------------------------
// Obsługa listy dwukierunkowej
//-----------------------------

// Inicjuje pola zmiennej listy
//---------------------------------------
void l_init(dlistVar & L)
{
  L.head  = L.tail  = NULL;
  L.count = 0;
}

// Wyświetla zawartość elementów listy
//----------------------------------------------
void l_printl(dlistVar & L)
{
  dlistEl * p;

  cout << setw(3) << L.count << " : [";
  p = L.head;
  while(p)
  {
    cout << " " << p->data;
    p = p->next;
  }
  cout << " ]\n\n";
}

// Dodaje nowy element na początek listy
//------------------------------------------------
void l_push_front(dlistVar & L, char v)
{
  dlistEl * p;

  p = new dlistEl;
  p->data = v;
  p->prev = NULL;
  p->next = L.head;
  L.head  = p;
  L.count++;
  if(p->next) p->next->prev = p;
  else L.tail = p;
}

// Dodaje nowy element na koniec listy
//----------------------------------------------
void l_push_back(dlistVar & L, char v)
{
  dlistEl * p;

  p = new dlistEl;
  p->data = v;
  p->next = NULL;
  p->prev = L.tail;
  L.tail  = p;
  L.count++;
  if(p->prev) p->prev->next = p;
  else L.head = p;
}

// Dodaje nowy element przed wybranym
//-----------------------------------
void l_insert_before(dlistVar & L, dlistEl * e, char v)
{
  dlistEl * p;

  if(e == L.head) l_push_front(L,v);
  else
  {
    p = new dlistEl;
    p->data = v;
    p->next = e;
    p->prev = e->prev;
    L.count++;
    e->prev->next = p;
    e->prev = p;
  }
}

// Dodaje nowy element za wybranym
//--------------------------------
void l_insert_after(dlistVar & L, dlistEl * e, char v)
{
  dlistEl * p;

  if(e == L.tail) l_push_back(L,v);
  else
  {
    p = new dlistEl;
    p->data = v;
    p->next = e->next;
    p->prev = e;
    L.count++;
    e->next->prev = p;
    e->next = p;
  }
}

// Usuwa wybrany element z listy
//------------------------------
void l_remove(dlistVar & L, dlistEl * e)
{
  L.count--;
  if(e->prev) e->prev->next = e->next;
  else        L.head = e->next;
  if(e->next) e->next->prev = e->prev;
  else        L.tail = e->prev;
  delete e;
}

// Usuwa element z początku listy
//-------------------------------
void l_pop_front(dlistVar & L)
{
  if(L.count) l_remove(L,L.head);
}

// Usuwa element z końca listy
//----------------------------
void l_pop_back(dlistVar & L)
{
  if(L.count) l_remove(L,L.tail);
}

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

int main()
{
  dlistVar L;
  char i;

  l_init(L);  // inicjujemy zmienną obsługi listy

  for(i = 'A'; i <= 'C'; i++) l_push_front(L,i);
  l_printl(L);
  for(i = 'D'; i <= 'F'; i++) l_push_back(L,i);
  l_printl(L);
  l_insert_before(L,L.tail,'#');
  l_printl(L);
  l_insert_after(L,L.head,'%');
  l_printl(L);
  l_pop_front(L);
  l_printl(L);
  l_pop_back(L);
  l_printl(L);
  l_remove(L,L.head->next->next);
  l_printl(L);

  return 0;
}
Free Basic
' Program testowy dla list dwukierunkowych
' Data: 14.02.2012
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------------------

' Definicje typów
'----------------

' Element listy
'--------------
Type dlistEl
  next As dlistEl Ptr   ' następnik
  prev As dlistEl Ptr   ' poprzednik
  data As String * 1
End Type

' Zmienna obsługująca listę
'--------------------------
Type dlistVar
  head As dlistEl Ptr  ' początek listy
  tail As dlistEl Ptr  ' koniec listy
  count As UInteger   ' licznik elementów
End Type

' Procedura inicjuje pola zmiennej listy
'---------------------------------------
Sub l_init(ByRef L As dlistVar)
  L.head  = 0
  L.tail  = 0
  L.count = 0
End Sub

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub l_printl(ByRef L As dlistVar)
  Dim p As dlistEl Ptr

  Print Using "### : [";L.count;
  p = L.head
  while p
    Print " ";p->Data;
    p = p->next
  Wend
  Print " ]"
  Print
End Sub

' Procedura dodaje nowy element na początek listy
'------------------------------------------------
Sub l_push_front(ByRef L As dlistVar, v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  p->data = v
  p->prev = 0
  p->next = L.head
  L.head  = p
  L.count += 1
  If p->next Then
    p->next->prev = p
  Else
    L.tail = p
  End If
End Sub

' Procedura dodaje nowy element na koniec listy
'----------------------------------------------
Sub l_push_back(ByRef L As dlistVar, v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  p->data = v
  p->next = 0
  p->prev = L.tail
  L.tail  = p
  L.count += 1
  If p->prev Then
    p->prev->next = p
  Else
    L.head = p
  End If
End Sub

' Procedura dodaje nowy element przed wybranym
'---------------------------------------------
Sub l_insert_before(ByRef L As dlistVar, e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = L.head Then
    l_push_front(L,v)
  Else
    p = New dlistEl
    p->data = v
    p->next = e
    p->prev = e->prev
    L.count += 1
    e->prev->next = p
    e->prev = p
  End If
End Sub

' Procedura dodaje nowy element za wybranym
'------------------------------------------
Sub l_insert_after(ByRef L As dlistVar, e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = L.tail Then
    l_push_back(L,v)
  Else
    p = New dlistEl
    p->data = v
    p->next = e->next
    p->prev = e
    L.count += 1
    e->next->prev = p
    e->next = p
  End If
End Sub

' Procedura usuwa wybrany element z listy
'----------------------------------------
Sub l_remove(ByRef L As dlistVar, e As dlistEl Ptr)
  L.count -= 1
  If e->prev Then
    e->prev->next = e->next
  Else
    L.head = e->next
  End If
  If e->next Then
    e->next->prev = e->prev
  Else
    L.tail = e->prev
  End If
  Delete e
End Sub

' Procedura usuwa element z początku listy
'-----------------------------------------
Sub l_pop_front(ByRef L As dlistVar)
  If L.count > 0 Then l_remove(L,L.head)
End Sub

' Procedura usuwa element z końca listy
'--------------------------------------
Sub l_pop_back(ByRef L As dlistVar)
  If L.count > 0 Then l_remove(L,L.tail)
End Sub

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

Dim L As dlistVar
Dim i AS UInteger

l_init(L)  ' inicjujemy zmienną obsługi listy
l_printl(L)
For i = Asc("A") To Asc("C"): l_push_front(L,Chr(i)): Next
l_printl(L)
For i = Asc("D") To Asc("F"): l_push_back(L,Chr(i)): Next
l_printl(L)
l_insert_before(L,L.tail,"#")
l_printl(L)
l_insert_after(L,L.head,"%")
l_printl(L)
l_pop_front(L)
l_printl(L)
l_pop_back(L)
l_printl(L)
l_remove(L,L.head->next->next)
l_printl(L)

End
Wynik
  0 : [ ]

  3 : [ C B A ]

  6 : [ C B A D E F ]

  7 : [ C B A D E # F ]

  8 : [ C % B A D E # F ]

  7 : [ % B A D E # F ]

  6 : [ % B A D E # ]

  5 : [ % B D E # ]

  0 : [ ]

 

Wersja obiektowa

Poniższy program jest obiektową wersją ostatniego programu.

 

Lazarus
// Obiekt listy dwukierunkowej
// Data: 14.02.2012
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program dlist_object;

// Definicje typów
//----------------

type

  PdlistEl = ^dlistEl;  // wskaźnik do elementów listy

  // Element listy
  //--------------
  dlistEl = record
    next : PdlistEl;   // następnik
    prev : PdlistEl;   // poprzednik
    data : char;
  end;


// Definicja obiektu listy dwukierunkowej
//---------------------------------------
  dlist = object
    public
      head  : PdlistEl;  // początek listy
      tail  : PdlistEl;  // koniec listy
      count : cardinal;  // licznik elementów

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

//---------------------------------------------
// Definicje metod obiektu listy dwukierunkowej
//---------------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
constructor dlist.init;
begin
  head  := nil;
  tail  := nil;
  count := 0;
end;

// Usuwa elementy listy
//---------------------
destructor dlist.destroy;
begin
  while count > 0 do pop_front;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlist.printl;
var
  p : PdlistEl;
begin
  write(count:3,' : [');
  p := head;
  while p <> NIL do
  begin
    write(' ',p^.data);
    p := p^.next;
  end;
  writeln(' ]');
  writeln;
end;

// Procedura dodaje nowy element na początek listy
//------------------------------------------------
procedure dlist.push_front(v : char);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data := v;
  p^.prev := nil;
  p^.next := head;
  head  := p;
  inc(count);
  if p^.next <> nil then p^.next^.prev := p
  else tail := p;
end;

// Procedura dodaje nowy element na koniec listy
//----------------------------------------------
procedure dlist.push_back(v : char);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data := v;
  p^.next := nil;
  p^.prev := tail;
  tail    := p;
  inc(count);
  if p^.prev <> nil then p^.prev^.next := p
  else head := p;
end;

// Procedura dodaje nowy element przed wybranym
//---------------------------------------------
procedure dlist.insert_before(e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = head then push_front(v)
  else
  begin
    new(p);
    p^.data := v;
    p^.next := e;
    p^.prev := e^.prev;
    inc(count);
    e^.prev^.next := p;
    e^.prev := p;
  end;
end;

// Procedura dodaje nowy element za wybranym
//------------------------------------------
procedure dlist.insert_after(e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = tail then push_back(v)
  else
  begin
    new(p);
    p^.data := v;
    p^.next := e^.next;
    p^.prev := e;
    inc(count);
    e^.next^.prev := p;
    e^.next := p;
  end;
end;

// Procedura usuwa wybrany element z listy
//----------------------------------------
procedure dlist.remove(e : PdlistEl);
begin
  dec(count);
  if e^.prev <> nil then e^.prev^.next := e^.next
  else head := e^.next;
  if e^.next <> nil then e^.next^.prev := e^.prev
  else tail := e^.prev;
  dispose(e);
end;

// Procedura usuwa element z początku listy
//-----------------------------------------
procedure dlist.pop_front;
begin
  if count > 0 then remove(head);
end;

// Procedura usuwa element z końca listy
//--------------------------------------
procedure dlist.pop_back;
begin
  if count > 0 then remove(tail);
end;

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

var

  L : dlist;
  i : char;

begin
  L.init;  // inicjujemy obiekt              []
  L.printl;
  for i := 'A' to 'C' do L.push_front(i); // [C B A]
  L.printl;
  for i := 'D' to 'F' do L.push_back(i);  // [C B A D E F]
  L.printl;
  L.insert_before(L.tail,'#');            // [C B A D E # F]
  L.printl;
  L.insert_after(L.head,'%');             // [C % B A D E # F]
  L.printl;
  L.pop_front;                            // [% B A D E # F]
  L.printl;
  L.pop_back;                             // [% B A D E #]
  L.printl;
  L.remove(L.head^.next^.next);           // [% B D E #]
  L.printl;
  L.destroy; // usuwamy listę z pamięci      []
  L.printl;
end.
Code::Blocks
// Obiekt listy dwukierunkowej
// Data: 14.02.2012
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Element listy
//--------------
struct dlistEl
{
  dlistEl * next;   // następnik
  dlistEl * prev;   // poprzednik
  char data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class dlist
{
  public:
    dlistEl * head;  // początek listy
    dlistEl * tail;  // koniec listy
    unsigned count;  // licznik elementów

    dlist();         // konstruktor
    ~dlist();        // destruktor
    void printl();
    void push_front(char v);
    void push_back(char v);
    void insert_before(dlistEl * e, char v);
    void insert_after(dlistEl * e, char v);
    void remove(dlistEl * e);
    void pop_front();
    void pop_back();
};

//------------------------------------
// Metody obiektu listy dwukierunkowej
//------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
dlist::dlist()
{
  head  = tail  = NULL;
  count = 0;
}

// Usuwa listę z pamięci
//----------------------
dlist::~dlist()
{
  while(count) pop_front();
}

// Wyświetla zawartość elementów listy
//----------------------------------------------
void dlist::printl()
{
  dlistEl * p;

  cout << setw(3) << count << " : [";
  p = head;
  while(p)
  {
    cout << " " << p->data;
    p = p->next;
  }
  cout << " ]\n\n";
}

// Dodaje nowy element na początek listy
//------------------------------------------------
void dlist::push_front(char v)
{
  dlistEl * p;

  p = new dlistEl;
  p->data = v;
  p->prev = NULL;
  p->next = head;
  head  = p;
  count++;
  if(p->next) p->next->prev = p;
  else tail = p;
}

// Dodaje nowy element na koniec listy
//----------------------------------------------
void dlist::push_back(char v)
{
  dlistEl * p;

  p = new dlistEl;
  p->data = v;
  p->next = NULL;
  p->prev = tail;
  tail  = p;
  count++;
  if(p->prev) p->prev->next = p;
  else head = p;
}

// Dodaje nowy element przed wybranym
//-----------------------------------
void dlist::insert_before(dlistEl * e, char v)
{
  dlistEl * p;

  if(e == head) push_front(v);
  else
  {
    p = new dlistEl;
    p->data = v;
    p->next = e;
    p->prev = e->prev;
    count++;
    e->prev->next = p;
    e->prev = p;
  }
}

// Dodaje nowy element za wybranym
//--------------------------------
void dlist::insert_after(dlistEl * e, char v)
{
  dlistEl * p;

  if(e == tail) push_back(v);
  else
  {
    p = new dlistEl;
    p->data = v;
    p->next = e->next;
    p->prev = e;
    count++;
    e->next->prev = p;
    e->next = p;
  }
}

// Usuwa wybrany element z listy
//------------------------------
void dlist::remove(dlistEl * e)
{
  count--;
  if(e->prev) e->prev->next = e->next;
  else        head = e->next;
  if(e->next) e->next->prev = e->prev;
  else        tail = e->prev;
  delete e;
}

// Usuwa element z początku listy
//-------------------------------
void dlist::pop_front()
{
  if(count) remove(head);
}

// Usuwa element z końca listy
//----------------------------
void dlist::pop_back()
{
  if(count) remove(tail);
}

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

int main()
{
  dlist L;
  char i;

  L.printl();
  for(i = 'A'; i <= 'C'; i++) L.push_front(i);
  L.printl();
  for(i = 'D'; i <= 'F'; i++) L.push_back(i);
  L.printl();
  L.insert_before(L.tail,'#');
  L.printl();
  L.insert_after(L.head,'%');
  L.printl();
  L.pop_front();
  L.printl();
  L.pop_back();
  L.printl();
  L.remove(L.head->next->next);
  L.printl();

  return 0;
}
Free Basic
' Obiekt listy dwukierunkowej
' Data: 14.02.2012
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

' Element listy
'--------------
Type dlistEl
  next As dlistEl Ptr   ' następnik
  prev As dlistEl Ptr   ' poprzednik
  data As String * 1
End Type

' Typ obiektowy listy dwukierunkowej
'-----------------------------------
Type dlist
  head As dlistEl Ptr  ' początek listy
  tail As dlistEl Ptr  ' koniec listy
  count As UInteger   ' licznik elementów

  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Sub push_front(v As String)
  Declare Sub push_back(v As String)
  Declare Sub insert_before(e As dlistEl Ptr, v As String)
  Declare Sub insert_after(e As dlistEl Ptr, v As String)
  Declare Sub remove(e As dlistEl Ptr)
  Declare Sub pop_front()
  Declare Sub pop_back()
End Type

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

Dim L As dlist
Dim i AS UInteger

L.printl()
For i = Asc("A") To Asc("C"): L.push_front(Chr(i)): Next
L.printl()
For i = Asc("D") To Asc("F"): L.push_back(Chr(i)): Next
L.printl()
L.insert_before(L.tail,"#")
L.printl()
L.insert_after(L.head,"%")
L.printl()
L.pop_front()
L.printl()
L.pop_back()
L.printl()
L.remove(L.head->next->next)
L.printl()
End

' Konstruktor listy
'------------------
Constructor dlist()
  head  = 0
  tail  = 0
  count = 0
End Constructor

' Usuwa listę z pamięci
Destructor dlist()
  While count > 0
  	 pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub dlist.printl()
  Dim p As dlistEl Ptr

  Print Using "### : [";count;
  p = head
  while p
    Print " ";p->Data;
    p = p->next
  Wend
  Print " ]"
  Print
End Sub

' Procedura dodaje nowy element na początek listy
'------------------------------------------------
Sub dlist.push_front(v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  p->data = v
  p->prev = 0
  p->next = head
  head  = p
  count += 1
  If p->next Then
    p->next->prev = p
  Else
    tail = p
  End If
End Sub

' Procedura dodaje nowy element na koniec listy
'----------------------------------------------
Sub dlist.push_back(v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  p->data = v
  p->next = 0
  p->prev = tail
  tail  = p
  count += 1
  If p->prev Then
    p->prev->next = p
  Else
    head = p
  End If
End Sub

' Procedura dodaje nowy element przed wybranym
'---------------------------------------------
Sub dlist.insert_before(e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = head Then
    push_front(v)
  Else
    p = New dlistEl
    p->data = v
    p->next = e
    p->prev = e->prev
    count += 1
    e->prev->next = p
    e->prev = p
  End If
End Sub

' Procedura dodaje nowy element za wybranym
'------------------------------------------
Sub dlist.insert_after(e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = tail Then
    push_back(v)
  Else
    p = New dlistEl
    p->data = v
    p->next = e->next
    p->prev = e
    count += 1
    e->next->prev = p
    e->next = p
  End If
End Sub

' Procedura usuwa wybrany element z listy
'----------------------------------------
Sub dlist.remove(e As dlistEl Ptr)
  count -= 1
  If e->prev Then
    e->prev->next = e->next
  Else
    head = e->next
  End If
  If e->next Then
    e->next->prev = e->prev
  Else
    tail = e->prev
  End If
  Delete e
End Sub

' Procedura usuwa element z początku listy
'-----------------------------------------
Sub dlist.pop_front()
  If count > 0 Then remove(head)
End Sub

' Procedura usuwa element z końca listy
'--------------------------------------
Sub dlist.pop_back()
  If count > 0 Then remove(tail)
End Sub

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.