Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Operacje na listach dwukierunkowych

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Uwaga:

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

Typy dla list dwu-kierunkowych

Pascal
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : typ_danych;
  end;

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

struct dlistVar
{
  dlistEl * head, * tail;
  unsigned count;
};
Basic
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
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

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ę dwukierunkową.

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: pL.head ; w p ustawiamy adres pierwszego elementu listy
K02: Dopóki p ≠ nil, ; w pętli przechodzimy przez kolejne
         wykonuj kroki K03…K05 ; 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: pL.tail ; w p ustawiamy adres ostatniego elementu listy
K02: Dopóki p ≠ nil, ; w pętli przechodzimy przez kolejne
     wykonuj kroki K03…K05 ; elementy listy
K03: Przetwarzaj element wskazywany przez p
K04: p ← (pprev) ; w p umieść zawartość pola prev elementu
     ; wskazywanego przez p
K05: Zakończ
Pascal
// Przejście w przód
p := L.head;
while p <> nil do
begin
  …
  p := p^.next;
end;
 
// Przejście w tył
p := L.tail;
while p <> nil do
begin
  …
  p := p^.prev;
end;
C++
// Przejście w przód
p = L.head;
while(p)
{
  …
  p = p->next;
}
 
// Przejście w tył
p = L.tail;
while(p)
{
  …
  p = p->prev;
}
Basic
' Przejście w przód
p = L.head
While p
  …
  p = p->next
Wend
 
' Przejście w tył
p = L.tail
While p
  …
  p = p->prev
Wend
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0
…
L = dlistVar() # Lista dwukierunkowa
…

# Przejście w przód
p = L.head
while p:
    …
    p = p.next

# Przejście w tył
p = L.tail
while p:
    …
    p = p.prev

Na początek:  podrozdziału   strony 

Liczba elementów listy

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


Na początek:  podrozdziału   strony 

Dodawanie elementu na początku listy

 obrazek
Mamy listę dwukierunkową, którą obsługuje zmienna L typu slist. Naszym zadaniem jest dodanie nowego elementu na początku listy dwukierunkowej.
obrazek
Dynamicznie tworzymy nowy element 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.
obrazek
W polu next umieszczamy adres przechowywany przez pole head. W ten sposób następnikiem nowego elementu stanie się obecny pierwszy element listy.
obrazek
W polu head umieszczamy adres nowego elementu, który teraz staje się pierwszym elementem listy.
obrazek
Zwiększamy pole count o 1.
obrazek
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 wstecz do pierwszego elementu. Lista staje się kompletna.
obrazek
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: p ← nowy element
K02: (pdata) ← v ; umieszczamy dane w nowym elemencie
K03: (pprev) ← nil ; pierwszy element nie posiada poprzednika
K04: (pnext) ← L.head ; następnikiem będzie obecny pierwszy element listy
K05: L.headp ; dołączamy element do początku listy
K06  L.countL.count+1 ; zwiększamy licznik elementów o 1
K07: Jeśli (pnext) ≠ nil, ; jeśli istnieje następnik,
     to ((pnext)→prev) ← p ; to jego poprzednikiem czynimy nowy element
     inaczej L.tailp ; inaczej adres nowego elementu umieszczamy w polu tail
K08: Zakończ

Pascal
procedure l_push_front(var L : dlistVar;
                           v : char);
var
  p : PdlistEl;
begin
  new(p); // 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;
C++
void l_push_front(dlistVar & L,
                  char v)
{
  dlistEl * p;

  p = new dlistEl; // 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;
}
Basic
Sub l_push_front(ByRef L As dlistVar, _
                       v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl ' 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
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None # następnik elementu
        self.prev = None # poprzednik elementu
        self.data = data # dane elementu

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None # pierwszy element
        self.tail = None # ostatni element
        self.count = 0   # liczba elementów

    # dodanie elementu na początek
    def l_push_front(self,v):
        p = dlistEl(v) # nowy element
        p.next = self.head
        self.head  = p
        self.count += 1
        if p.next:
            p.next.prev = p
        else:
            self.tail = p

Na początek:  podrozdziału   strony 

Dodawanie elementu na koniec listy

obrazek
Dodawanie elementu na koniec listy jest symetryczne z dodawaniem na początek. Musi tak być, ponieważ lista dwukierunkowa jest strukturą symetryczną.
obrazek
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.
obrazek
Do pola prev kopiujemy zawartość pola tail ze zmiennej obsługującej listę. Poprzednikiem nowego elementu stanie się obecny ostatni element listy.
obrazek
W polu tail umieszczamy adres nowego elementu. Nowy element staje się ostatnim elementem listy
obrazek
Zwiększamy o 1 zawartość pola count.
obrazek
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ść.
obrazek
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: p ← nowy element
K02: (pdata) ← v ; umieszczamy dane w nowym elemencie
K03: (pnext) ← nil ; ostatni element nie będzie posiadał następnika
K04; (pprev) ← L.tail ; poprzednikiem będzie obecny ostatni element
K05: L.tailp ; nowy element staje się ostatnim na liście
K06: L.countL.count+1 ; zwiększamy o 1 licznik elementów listy
K07: Jeśli (pprev) ≠ nil, ; jeśli istnieje poprzednik,
     to ((pprev)→next) ← p ; to nowy element będzie jego następnikiem,
     inaczej L.headp ; inaczej adres nowego elementu;
     ; umieszczamy w polu head
K08: Zakończ

Pascal
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;
C++
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;
}
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
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # dodanie elementu na koniec
    def l_push_back(self,v):
        p = dlistEl(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p

Na początek:  podrozdziału   strony 

Dodawanie nowego elementu przed wybranym elementem listy

obrazek
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.
obrazek
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.
obrazek
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).
obrazek
Zwiększamy o 1 licznik elementów count w zmiennej obsługującej listę.
obrazek
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ę.
: 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.
l_push_front(L,v) : wstawianie elementu v na początek listy L.

Lista kroków:

K01: Jeśli eL.head, ; sprawdzamy, czy wybrany element
     to idź do K04 ; nie jest pierwszym elementem listy
K02: l_push_front(L,v) ; jeśli tak, to wykorzystujemy algorytm
     ; wstawiania na początek listy
K03: Zakończ
K04; p ← nowy element ; tworzymy nowy element listy
     ; i jego adres umieszczany w p
K05: (pdata) ← v ; umieszczamy dane w nowym elemencie
K06: (pnext) ← e ; następnikiem będzie element wybrany
K07: (pprev) ← (eprev) ; poprzednikiem będzie poprzednik
     ; elementu wybranego
K08: L.countL.count+1 ; zwiększamy licznik elementów listy
K09: ((eprev)→next) ← p ; następnikiem poprzednika elementu
     ; wybranego będzie nowy element
K10: (eprev) ← p ; poprzednikiem elementu wybranego
     ; będzie nowy element
K11: Zakończ

Pascal
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;
C++
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;
  }
}
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
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None # następnik elementu
        self.prev = None # poprzednik elementu
        self.data = data # dane elementu

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None # pierwszy element
        self.tail = None # ostatni element
        self.count = 0   # liczba elementów

    # dodanie elementu na początek
    def l_push_front(self,v):
        p = dlistEl(v) # nowy element
        p.next = self.head
        self.head  = p
        self.count += 1
        if p.next:
            p.next.prev = p
        else:
            self.tail = p

    # dodanie elementu przed
    def l_insert_before(self,e,v):
        if e is self.head:
            self.l_push_front(v)
        else:
            p = dlistEl(v)
            p.next = e
            p.prev = e.prev
            self.count += 1
            e.prev.next = p
            e.prev = p

Na początek:  podrozdziału   strony 

Dodawanie nowego elementu za elementem wybranym

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

obrazek
Załóżmy, że wybrany element nie jest ostatni na liście. Wtedy posiada następnik (na rysunku w kolorze żółtym).
obrazek
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.
obrazek
Zwiększamy licznik elementów count o 1.
obrazek
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.
l_push_back(L,v) : wstawianie elementu v na koniec listy L.

Lista kroków:

K01: Jeśli eL.tail, ; sprawdzamy, czy e nie jest
     to idź do kroku K04 ; ostatnim elementem listy
K02: l_push_back(L,v) ; jeśli jest ostatnim elementem listy,
     ; wykorzystujemy algorytm wstawiania na koniec listy
K03: Zakończ
K04; p ← nowy element
K05: (pdata) ← v ; umieszczamy dane w nowym elemencie
K06: (pnext) ← (enext) ; następnikiem będzie następnik
     ; elementu wybranego
K07: (pprev) ← e ; poprzednikiem będzie element wybrany
K08: L.count ← L.count+1 ; zwiększamy licznik elementów
K09: ((enext)→prev) ← p ;ustawiamy p jako poprzednik następnika
K10: (enext) ← p ; ustawiamy p jako następnik elementu wybranego
K11:Zakończ

Pascal
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;
C++
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;
  }
}
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
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # dodanie elementu na koniec
    def l_push_back(self,v):
        p = dlistEl(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p

    # dodanie elementu za
    def l_insert_after(self,e,v):
        if e is self.tail:
            self.l_push_back(v)
        else:
            p = dlistEl(v)
            p.next = e.next
            p.prev = e
            self.count += 1
            e.next.prev = p
            e.next = p

Na początek:  podrozdziału   strony 

Usuwanie wybranego elementu listy

obrazek
obrazek
obrazek
Zmniejszamy o 1 pole count. Usuwany element oznaczyliśmy kolorem czerwonym na rysunkach. 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.
obrazek
obrazek
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.

obrazek
obrazek
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 zostaje odłączony od listy.

obrazek
Usuwamy wybrany element 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, ; następnikiem poprzednika będzie
     to ((eprev)→next) ← (enext) ; następnik usuwanego elementu
     inaczej L.head ← (enext) ; jeśli poprzednika nie ma, modyfikujemy head
K03: Jeśli (enext) ≠ nil, ; poprzednikiem następnika będzie
     to ((enext)→prev) ← (eprev) ; poprzednik usuwanego elementu
     inaczej L.tail ← (eprev) ; jeśli następnika nie ma, to modyfikujemy tail
K04: Usuń element e
K05: Zakończ

Pascal
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;
C++
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;
}
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
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # usuwa e z listy
    def l_remove(self,e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        del e

Na początek:  podrozdziału   strony 

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.

Dane pomocnicze:

l_remove(L,e) : usuwa z listy L element e.

Lista kroków:

K01: Jeśli L.count = 0, ; lista jest pusta i nie ma co usuwać
     to zakończ
K02: l_remove(L,L.head) ; usuń z listy element L.head
K03: Zakończ

Pascal
procedure l_pop_front(var L : dlistVar);
begin
  if L.count > 0 then
    l_remove(L,L.head);
end;
C++
void l_pop_front(dlistVar & L)
{
  if(L.count)
    l_remove(L,L.head);
}
Basic
Sub l_pop_front(ByRef L As dlistVar)
  If L.count > 0 Then _
    l_remove(L,L.head)
End Sub
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # usuwa e z listy
    def l_remove(self,e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        del e

    # usuwa pierwszy element
    def l_pop_front(self):
        if self.count:
            self.l_remove(self.head)

Na początek:  podrozdziału   strony 

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.

Dane pomocnicze:

l_remove(L,e) : usuwa z listy L element e.

Lista kroków:

K01: Jeśli L.count = 0, ; lista jest pusta i nie ma co usuwać
     to zakończ
K02: l_remove(L,L.tail) ; usuń z listy element L.tail
K03: Zakończ
Pascal
procedure l_pop_back(var L : dlistVar);
begin
  if L.count > 0 then
    l_remove(L,L.tail);
end;
C++
void l_pop_back(dlistVar & L)
{
  if(L.count)
    l_remove(L,L.tail);
}
Basic
Sub l_pop_back(ByRef L As dlistVar)
  If L.count > 0 Then _
    l_remove(L,L.tail)
End Sub
Python (dodatek)
# klasa elementu listy dwukierunkowej
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # usuwa e z listy
    def l_remove(self,e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        del e

    # usuwa ostatni element
    def l_pop_back(self):
        if self.count:
            self.l_remove(self.tail)

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.

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.
Pascal
// Program testowy dla list dwukierunkowych
// Data: 14.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------------------

program dlist_test;

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

  PdlistEl = ^dlistEl; // wskaźnik elementu

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

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

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

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

// Wyświetla zawartość listy
//--------------------------
procedure l_print(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;

// Dodaje 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;

// Dodaje element na koniec listy
//------------------------------
procedure l_push_back(var L : dlistVar;
                          v : char);
var
  p : PdlistEl;
begin
  new(p); // 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;

// Dodaje 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;

// 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;

// 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;

// 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;

// 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 listę
  for i := 'A' to 'C' do
    l_push_front(L,i);
  l_print(L);
  for i := 'D' to 'F' do
    l_push_back(L,i);
  l_print(L);
  l_insert_before(L,L.tail,'#');
  l_print(L);
  l_insert_after(L,L.head,'%');
  l_print(L);
  l_pop_front(L);
  l_print(L);
  l_pop_back(L);
  l_print(L);
  l_remove(L,L.head^.next^.next);
  l_print(L);
end.
C++
// Program testowy dla list dwukierunkowych
// Data: 14.02.2012
// (C)2020 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_print(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ą listy
  for(i = 'A'; i <= 'C'; i++)
    l_push_front(L,i);
  l_print(L);
  for(i = 'D'; i <= 'F'; i++)
    l_push_back(L,i);
  l_print(L);
  l_insert_before(L,L.tail,'#');
  l_print(L);
  l_insert_after(L,L.head,'%');
  l_print(L);
  l_pop_front(L);
  l_print(L);
  l_pop_back(L);
  l_print(L);
  l_remove(L,L.head->next->next);
  l_print(L);

  return 0;
}
Basic
' Program testowy dla list dwukierunkowych
' Data: 14.02.2012
' (C)2020 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

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

' Wyświetla zawartość elementów listy
'------------------------------------
Sub l_print(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

' 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

' 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

' 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

' 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

' 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

' 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

' 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ą listy
l_print(L)
For i = Asc("A") To Asc("C")
  l_push_front(L,Chr(i))
Next
l_print(L)
For i = Asc("D") To Asc("F")
  l_push_back(L,Chr(i))
Next
l_print(L)
l_insert_before(L,L.tail,"#")
l_print(L)
l_insert_after(L,L.head,"%")
l_print(L)
l_pop_front(L)
l_print(L)
l_pop_back(L)
l_print(L)
l_remove(L,L.head->next->next)
l_print(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 : [ ]
Python (dodatek)
# Program testowy dla list dwukierunkowych
# Data: 8.05.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------------------

# Definicje typów
#----------------

# klasa elementu listy
#---------------------
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
#---------------------------
class dlistVar:

    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0
        print("Lista utworzona")
        print("===============")
        self.l_print()

    # Destruktor
    def __del__(self):
        while self.head:
            self.l_pop_front()
        self.l_print()
        print("Lista usunięta")
        print("==============")

    # Wyświetla zawartość
    # elementów listy
    def l_print(self):
        print("%3d: [ " % self.count,end="")
        p = self.head
        while p:
            print(p.data,end=" ")
            p = p.next
        print("]")
        print()

    # Dodaje nowy element
    # na początek listy
    def l_push_front(self,v):
        p = dlistEl(v)
        p.next = self.head
        self.head = p
        self.count += 1
        if p.next:
            p.next.prev = p
        else:
            self.tail = p

    # Dodaje nowy element
    # na koniec listy
    def l_push_back(self,v):
        p = dlistEl(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p

    # Dodaje nowy element
    # przed wybranym
    def l_insert_before(self,e,v):
        if e is self.head:
            self.l_push_front(v)
        else:
            p = dlistEl(v)
            p.next = e
            p.prev = e.prev
            self.count += 1
            e.prev.next = p
            e.prev = p

    # Dodaje nowy element
    # za wybranym
    def l_insert_after(self,e,v):
        if e is self.tail:
            self.l_push_back(v)
        else:
            p = dlistEl(v)
            p.next = e.next
            p.prev = e
            self.count += 1
            e.next.prev = p
            e.next = p

    # Usuwa wybrany element
    # z listy
    def l_remove(self,e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        del e

    # Usuwa element
    # z początku listy
    def l_pop_front(self):
        if self.count:
            self.l_remove(self.head)

    # Usuwa element
    # z końca listy
    def l_pop_back(self):
        if self.count:
            self.l_remove(self.tail)

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

L = dlistVar()
for i in range(ord('A'),ord('C')+1):
    L.l_push_front(chr(i))
L.l_print()
for i in range(ord('D'),ord('F')+1):
    L.l_push_back(chr(i))
L.l_print()
L.l_insert_before(L.tail,'#')
L.l_print()
L.l_insert_after(L.head,'%')
L.l_print()
L.l_pop_front()
L.l_print()
L.l_pop_back()
L.l_print()
L.l_remove(L.head.next.next)
L.l_print()
del L
print("KONIEC")
Wynik:
Lista utworzona
===============
  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: [ ]

Lista usunięta
==============
KONIEC

Na początek:  podrozdziału   strony 

Wersja obiektowa

Poniższy program jest obiektową wersją ostatniego programu.
Pascal
// Obiekt listy dwukierunkowej
// Data: 14.02.2012
// (C)2020 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
//---------------------------------------
  dlistVar = object
    public
      head  : PdlistEl; // początek listy
      tail  : PdlistEl; // koniec listy
      count : cardinal; // licznik elementów

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

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

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlistVar.l_print;
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 dlistVar.l_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 dlistVar.l_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 dlistVar.l_insert_before(e : PdlistEl;
                                   v : char);
var
  p : PdlistEl;
begin
  if e = head then
    l_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 dlistVar.l_insert_after(e : PdlistEl;
                                  v : char);
var
  p : PdlistEl;
begin
  if e = tail then
    l_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 dlistVar.l_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 dlistVar.l_pop_front;
begin
  if count > 0 then
    l_remove(head);
end;

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

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

var

  L : dlistVar;
  i : char;

begin
  L.init; // inicjujemy obiekt       []
  L.l_print;
  for i := 'A' to 'C' do
    L.l_push_front(i);           //  [C B A]
  L.l_print;
  for i := 'D' to 'F' do
    L.l_push_back(i);            //  [C B A D E F]
  L.l_print;
  L.l_insert_before(L.tail,'#'); //  [C B A D E # F]
  L.l_print;
  L.l_insert_after(L.head,'%');  //  [C % B A D E # F]
  L.l_print;
  L.l_pop_front;                 //  [% B A D E # F]
  L.l_print;
  L.l_pop_back;                  //  [% B A D E #]
  L.l_print;
  L.l_remove(L.head^.next^.next); // [% B D E #]
  L.l_print;
  L.destroy; // usuwamy listę        []
  L.l_print;
end.
C++
// Obiekt listy dwukierunkowej
// Data: 14.02.2012
// (C)2020 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 dlistVar
{
  public:
    dlistEl * head; // początek listy
    dlistEl * tail; // koniec listy
    unsigned count; // licznik elementów

    dlistVar(); // konstruktor
    ~dlistVar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_push_back(char v);
    void l_insert_before(dlistEl * e,
                         char v);
    void l_insert_after(dlistEl * e,
                        char v);
    void l_remove(dlistEl * e);
    void l_pop_front();
    void l_pop_back();
};

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

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

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

// Wyświetla zawartość elementów listy
//------------------------------------
void dlistVar::l_print()
{
  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 dlistVar::l_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 dlistVar::l_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 dlistVar::l_insert_before(dlistEl * e,
                               char v)
{
  dlistEl * p;

  if(e == head)
    l_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 dlistVar::l_insert_after(dlistEl * e,
                              char v)
{
  dlistEl * p;

  if(e == tail)
    l_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 dlistVar::l_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 dlistVar::l_pop_front()
{
  if(count)
    l_remove(head);
}

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

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

int main()
{
  dlistVar L;
  char i;

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

  return 0;
}
Basic
' Obiekt listy dwukierunkowej
' Data: 14.02.2012
' (C)2020 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 dlistVar
  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 l_print()
  Declare Sub l_push_front(v As String)
  Declare Sub l_push_back(v As String)
  Declare Sub l_insert_before(e As dlistEl Ptr, _
                              v As String)
  Declare Sub l_insert_after(e As dlistEl Ptr, _
                             v As String)
  Declare Sub l_remove(e As dlistEl Ptr)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
End Type

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

Dim L As dlistVar
Dim i AS UInteger

L.l_print()
For i = Asc("A") To Asc("C")
  L.l_push_front(Chr(i))
Next
L.l_print()
For i = Asc("D") To Asc("F")
  L.l_push_back(Chr(i))
Next
L.l_print()
L.l_insert_before(L.tail,"#")
L.l_print()
L.l_insert_after(L.head,"%")
L.l_print()
L.l_pop_front()
L.l_print()
L.l_pop_back()
L.l_print()
L.l_remove(L.head->next->next)
L.l_print()
End

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

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

' Procedura wyświetla zawartość
' elementów listy
'------------------------------
Sub dlistVar.l_print()
  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 dlistVar.l_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 dlistVar.l_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 dlistVar.l_insert_before(e As dlistEl Ptr, _
                             v As String)
  Dim p As dlistEl Ptr

  If e = head Then
    l_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 dlistVar.l_insert_after(e As dlistEl Ptr, _
                            v As String)
  Dim p As dlistEl Ptr

  If e = tail Then
    l_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 dlistVar.l_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 dlistVar.l_pop_front()
  If count > 0 Then _
    l_remove(head)
End Sub

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

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

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

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

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

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

Informacje dodatkowe.