Algorytmy i Struktury Danych - Operacje na listach dwukierunkowych

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: p ← L.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 ← p→next ; 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, ; w pętli przechodzimy przez kolejne
     wykonuj kroki K03…K05 ; elementy listy
K03: Przetwarzaj element wskazywany przez p
K04: p ← p→prev ; 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 DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

…

dl = DLvar() # Lista dwukierunkowa
…

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

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

do podrozdziału do strony

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

do podrozdziału do strony

Mamy listę dwukierunkową, którą obsługuje zmienna L typu slist. Naszym zadaniem jest dodanie nowego elementu na początku listy dwukierunkowej.

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.

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 wstecz 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: p ← nowy element
K02: p→data ← v ; umieszczamy dane w nowym elemencie
K03: p→prev ← nil ; pierwszy element nie posiada poprzednika
K04: p→next ← L.head ; następnikiem będzie obecny pierwszy element listy
K05: L.head ← p ; dołączamy element do początku listy
K06  L.count ← L.count+1 ; zwiększamy licznik elementów o 1
K07: Jeśli p→next ≠ nil, ; jeśli istnieje następnik, 
     to p→next→prev ← p ; to jego poprzednikiem czynimy nowy element
     inaczej L.tail ← p ; inaczej adres nowego elementu umieszczamy w polu tail
K08: Zakończ

Pascal

procedure l_push_front(var L : DLvar;
                           v : char);
var
  p : PDLel;
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(DLvar & L, 
                  char v)
{
  DLel * p;

  p = new DLel; // 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 DLvar, _
                       v As String)
  Dim p As DLel Ptr

  p = New DLel ' 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 DLel:


    def __init__(self, data):
        self.next = None # następnik elementu
        self.prev = None # poprzednik elementu
        self.data = data # dane elementu


# klasa listy dwukierunkowej
class DLvar:


    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 = DLel(v) # nowy element
        p.next = self.head
        self.head  = p
        self.count += 1
        if p.next:
            p.next.prev = p
        else:
            self.tail = p

do podrozdziału do strony

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: p ← nowy element
K02: p→data ← v ; umieszczamy dane w nowym elemencie
K03: p→next ← nil ; ostatni element nie będzie posiadał następnika
K04; p→prev ← L.tail ; poprzednikiem będzie obecny ostatni element
K05: L.tail ← p ; nowy element staje się ostatnim na liście
K06: L.count ← L.count+1 ; zwiększamy o 1 licznik elementów listy
K07: Jeśli p→prev ≠ nil, ; jeśli istnieje poprzednik, 
     to p→prev→next ← p ; to nowy element będzie jego następnikiem, 
     inaczej L.head ← p ; inaczej adres nowego elementu;
     ; umieszczamy w polu head
K08: Zakończ

Pascal

procedure l_push_back(var L : DLvar;
                          v : char);
var
  p : PDLel;
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(DLvar & L, 
                 char v)
{
  DLel * p;

  p = new DLel;
  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 DLvar, _
                      v As String)
  Dim p As DLel Ptr

  p = New DLel
  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 DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0


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

do podrozdziału do strony

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.
l_push_front(L, v) : wstawianie elementu v na początek listy L.

Lista kroków:

K01: Jeśli e ≠ L.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: p→data ← v ; umieszczamy dane w nowym elemencie
K06: p→next ← e ; następnikiem będzie element wybrany
K07: p→prev ← e→prev ; poprzednikiem będzie poprzednik
     ; elementu wybranego
K08: L.count ← L.count+1 ; zwiększamy licznik elementów listy
K09: e→prev→next ← p ; następnikiem poprzednika elementu
     ; wybranego będzie nowy element
K10: e→prev ← p ; poprzednikiem elementu wybranego
     ; będzie nowy element
K11: Zakończ

Pascal

procedure l_insert_before(var L : DLvar;
                              e : PDLel;
                              v : char);
var
  p : PDLel;
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(DLvar & L, 
                     DLel * e, 
                     char v)
{
  DLel * p;

  if(e == L.head)
    l_push_front(L, v);
  else
  {
    p = new DLel;
    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 DLvar, _
                          e As DLel Ptr, _
                          v As String)
  Dim p As DLel Ptr

  If e = L.head Then
    l_push_front(L, v)
  Else
    p = New DLel
    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 DLel:


    def __init__(self, data):
        self.next = None # następnik elementu
        self.prev = None # poprzednik elementu
        self.data = data # dane elementu


# klasa listy dwukierunkowej
class DLvar:


    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 = DLel(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 = DLel(v)
            p.next = e
            p.prev = e.prev
            self.count += 1
            e.prev.next = p
            e.prev = p

do podrozdziału do strony

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.
l_push_back(L, v) : wstawianie elementu v na koniec listy L.

Lista kroków:

K01: Jeśli e ≠ L.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: p→data ← v ; umieszczamy dane w nowym elemencie
K06: p→next ← e→next ; następnikiem będzie następnik
     ; elementu wybranego
K07: p→prev ← e ; poprzednikiem będzie element wybrany
K08: L.count ← L.count+1 ; zwiększamy licznik elementów
K09: e→next→prev ← p ;ustawiamy p jako poprzednik następnika
K10: e→next ← p ; ustawiamy p jako następnik elementu wybranego
K11:Zakończ

Pascal

procedure l_insert_after(var L : DLvar;
                             e : PDLel;
                             v : char);
var
  p : PDLel;
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(DLvar & L, 
                    DLel * e, 
                    char v)
{
  DLel * p;

  if(e == L.tail)
    l_push_back(L, v);
  else
  {
    p = new DLel;
    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 DLvar, _
                         e As DLel Ptr, _
                         v As String)
  Dim p As DLel Ptr

  If e = L.tail Then
    l_push_back(L, v)
  Else
    p = New DLel
    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 DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0


    # dodanie elementu na koniec
    def l_push_back(self, v):
        p = DLel(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 = DLel(v)
            p.next = e.next
            p.prev = e
            self.count += 1
            e.next.prev = p
            e.next = p

do podrozdziału do strony

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.

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

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.count ← L.count-1 ; zmniejszamy licznik elementów listy
K02: Jeśli e→prev ≠ nil, ; następnikiem poprzednika będzie
     to e→prev→next ← e→next ; następnik usuwanego elementu
     inaczej L.head ← e→next ; jeśli poprzednika nie ma, modyfikujemy head
K03: Jeśli e→next) ≠ nil, ; poprzednikiem następnika będzie
     to e→next→prev ← e→prev ; poprzednik usuwanego elementu
     inaczej L.tail ← e→prev ; jeśli następnika nie ma, to modyfikujemy tail
K04: Usuń element e
K05: Zakończ

Pascal

procedure l_remove(var L : DLvar;
                       e : PDLel);
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(DLvar & L, 
              DLel * 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 DLvar, _
                   e As DLel 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 DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    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
        e = None

do podrozdziału do strony

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 : DLvar);
begin
  if L.count > 0 then
    l_remove(L, L.head);
end;

C++

void l_pop_front(DLvar & L)
{
  if(L.count)
    l_remove(L, L.head);
}

Basic

Sub l_pop_front(ByRef L As DLvar)
  If L.count > 0 Then _
    l_remove(L, L.head)
End Sub

Python (dodatek)

# klasa elementu listy dwukierunkowej
class DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    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
        e = None


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

do podrozdziału do strony

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 : DLvar);
begin
  if L.count > 0 then
    l_remove(L, L.tail);
end;

C++

void l_pop_back(DLvar & L)
{
  if(L.count)
    l_remove(L, L.tail);
}

Basic

Sub l_pop_back(ByRef L As DLvar)
  If L.count > 0 Then _
    l_remove(L, L.tail)
End Sub

Python (dodatek)

# klasa elementu listy dwukierunkowej
class DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    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
        e = None


    # 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

  PDLel = ^DLel; // wskaźnik elementu

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

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

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

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

// Wyświetla zawartość listy
//--------------------------
procedure l_print(var L : DLvar);
var
  p : PDLel;
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 : DLvar;
                           v : char);
var
  p : PDLel;
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 : DLvar;
                          v : char);
var
  p : PDLel;
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 : DLvar;
                              e : PDLel;
                              v : char);
var
  p : PDLel;
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 : DLvar;
                             e : PDLel;
                             v : char);
var
  p : PDLel;
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 : DLvar;
                       e : PDLel);
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 : DLvar);
begin
  if L.count > 0 then
    l_remove(L, L.head);
end;

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

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

var
  L : DLvar;
  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 DLel
{
  DLel * next; // następnik
  DLel * prev; // poprzednik
  char data;
};

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

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

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

// Wyświetla zawartość elementów listy
//------------------------------------
void l_print(DLvar & L)
{
  DLel * 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(DLvar & L, 
                  char v)
{
  DLel * p;

  p = new DLel;
  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(DLvar & L, 
                 char v)
{
  DLel * p;

  p = new DLel;
  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(DLvar & L, 
                     DLel * e, 
                     char v)
{
  DLel * p;

  if(e == L.head)
    l_push_front(L, v);
  else
  {
    p = new DLel;
    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(DLvar & L, 
                    DLel * e, 
                    char v)
{
  DLel * p;

  if(e == L.tail)
    l_push_back(L, v);
  else
  {
    p = new DLel;
    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(DLvar & L, 
              DLel * 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(DLvar & L)
{
  if(L.count) l_remove(L, L.head);
}

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

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

int main()
{
  DLvar 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 DLel
  next As DLel Ptr ' następnik
  prev As DLel Ptr ' poprzednik
  data As String * 1
End Type

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

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

' Wyświetla zawartość elementów listy
'------------------------------------
Sub l_print(ByRef L As DLvar)
  Dim p As DLel 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 DLvar, _
                       v As String)
  Dim p As DLel Ptr

  p = New DLel
  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 DLvar, _
                      v As String)
  Dim p As DLel Ptr

  p = New DLel
  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 DLvar, _
                          e As DLel Ptr, _
                          v As String)
  Dim p As DLel Ptr

  If e = L.head Then
    l_push_front(L, v)
  Else
    p = New DLel
    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 DLvar, _
                         e As DLel Ptr, _
                         v As String)
  Dim p As DLel Ptr

  If e = L.tail Then
    l_push_back(L, v)
  Else
    p = New DLel
    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 DLvar, _
                   e As DLel 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 DLvar)
  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 DLvar)
  If L.count > 0 Then _
    l_remove(L, L.tail)
End Sub

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

Dim L As DLvar
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
#-----------------------------------------


# klasa elementu listy
#---------------------
class DLel:


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


# klasa listy dwukierunkowej
#---------------------------
class DLvar:


    # 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 = DLel(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 = DLel(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 = DLel(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 = DLel(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


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

dl = DLvar()
for i in range(ord('A'), ord('C')+1):
    dl.l_push_front(chr(i))
dl.l_print()
for i in range(ord('D'), ord('F')+1):
    dl.l_push_back(chr(i))
dl.l_print()
dl.l_insert_before(dl.tail, '#')
dl.l_print()
dl.l_insert_after(dl.head, '%')
dl.l_print()
dl.l_pop_front()
dl.l_print()
dl.l_pop_back()
dl.l_print()
dl.l_remove(dl.head.next.next)
dl.l_print()
dl = None
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

do podrozdziału do strony

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

  PDLel = ^DLel; // wskaźnik do elementów listy

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

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
  DLvar = object
    public
      head  : PDLel; // początek listy
      tail  : PDLel; // 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 : PDLel;
                                  v : char);
      procedure   l_insert_after(e : PDLel;
                                 v : char);
      procedure   l_remove(e : PDLel);
      procedure   l_pop_front;
      procedure   l_pop_back;
  end;

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

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

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

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

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

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

var

  L : DLvar;
  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 DLel
{
  DLel * next; // następnik
  DLel * prev; // poprzednik
  char data;
};

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

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

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

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

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

// Wyświetla zawartość elementów listy
//------------------------------------
void DLvar::l_print()
{
  DLel * 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 DLvar::l_push_front(char v)
{
  DLel * p;

  p = new DLel;
  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 DLvar::l_push_back(char v)
{
  DLel * p;

  p = new DLel;
  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 DLvar::l_insert_before(DLel * e, 
                               char v)
{
  DLel * p;

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

// Dodaje nowy element za wybranym
//--------------------------------
void DLvar::l_insert_after(DLel * e, 
                              char v)
{
  DLel * p;

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

// Usuwa wybrany element z listy
//------------------------------
void DLvar::l_remove(DLel * 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 DLvar::l_pop_front()
{
  if(count)
    l_remove(head);
}

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

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

int main()
{
  DLvar 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 DLel
  next As DLel Ptr ' następnik
  prev As DLel Ptr ' poprzednik
  data As String * 1
End Type

' Typ obiektowy listy dwukierunkowej
'-----------------------------------
Type DLvar
  head As DLel Ptr ' początek listy
  tail As DLel 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 DLel Ptr, _
                              v As String)
  Declare Sub l_insert_after(e As DLel Ptr, _
                             v As String)
  Declare Sub l_remove(e As DLel Ptr)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
End Type

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

Dim L As DLvar
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 DLvar()
  head  = 0
  tail  = 0
  count = 0
End Constructor

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

' Procedura wyświetla zawartość
' elementów listy
'------------------------------
Sub DLvar.l_print()
  Dim p As DLel 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 DLvar.l_push_front(v As String)
  Dim p As DLel Ptr

  p = New DLel
  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 DLvar.l_push_back(v As String)
  Dim p As DLel Ptr

  p = New DLel
  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 DLvar.l_insert_before(e As DLel Ptr, _
                             v As String)
  Dim p As DLel Ptr

  If e = head Then
    l_push_front(v)
  Else
    p = New DLel
    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 DLvar.l_insert_after(e As DLel Ptr, _
                            v As String)
  Dim p As DLel Ptr

  If e = tail Then
    l_push_back(v)
  Else
    p = New DLel
    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 DLvar.l_remove(e As DLel 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 DLvar.l_pop_front()
  If count > 0 Then _
    l_remove(head)
End Sub

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

do podrozdziału do strony

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.

Operacje na listach dwukierunkowych

Uwaga:

Typy dla list dwu-kierunkowych

Przejście przez listę

Algorytm przechodzenia przez listę dwukierunkową

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków : przejście w przód:

Lista kroków : przejście wstecz:

Liczba elementów listy

Dodawanie elementu na początku listy

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

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Dodawanie elementu na koniec listy

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

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Dodawanie nowego elementu przed wybranym elementem listy

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

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Dodawanie nowego elementu za elementem wybranym

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

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Usuwanie wybranego elementu listy

Algorytm usuwania wybranego elementu listy dwukierunkowej

Wejście:

Wyjście:

Lista kroków:

Usuwanie elementu z początku listy

Algorytm usuwania elementu z początku listy dwukierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Usuwanie elementu z końca listy

Algorytm usuwania elementu z końca listy dwukierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Przykładowe programy

Wersja obiektowa