Listy jedno i dwukierunkowe - sprawdzenie poprawności kodu

Witam. Chciałem tylko zapytać czy kod, który napisałem będzie działał. Chodzi mi tylko o to, czy dobrze zrozumiałem temat list.

Listy jednokierunkowe

1. Wstawianie elementu na początek listy.

type
	Lista = ^element;
	element = record
		liczba : integer;
		nast : Lista;
	end;

procedure dodaj_na_poczatek(var wsk : Lista, x : integer);

var 
	nowy : Lista;

begin
	new(nowy);

	if(wsk = nil) then
		begin
			nowy^.liczba := x;
			nowy^.nast := nil;
			wsk := nowy;
		end
	else
		begin
			nowy^.liczba := x;
			nowy^.nast := wsk;
			wsk := nowy;
		end;
end;

2. Wstawianie elementu na koniec listy.

type
	Lista = ^element;
	element = record
		liczba : integer;
		nast : Lista;
	end;

procedure dodaj_na_koniec(var wsk : Lista, x : integer);

var
	nowy, pom : Lista;
	
begin
	new(nowy);
	
	if (wsk = nil) then
		begin
			nowy^.liczba := x;
			nowy^.nast := nil;
			wsk := nowy;
		end
	else
		begin
			pom := wsk;
			
			while (pom^.nast != nil) do
				pom := pom^.nast;
				
			nowy^.liczba := x;
			nowy^.nast := nil;
			pom^.nast := nowy;
		end;
end;

3. Wstawianie elementu do listy z sortowaniem rosnąco.

type
	Lista = ^element;
	element = record
		liczba : integer;
		nast : Lista;
	end;
	
procedure dodaj_sort_rosnoca(var wsk : Lista, x : integer);

var
	nowy, pom : Lista;
	
begin
	new(nowy)
	
	if (wsk = nil) then
		begin
			nowy^.liczba := x;
			nowy^.nast := nil;
			wsk := nowy;
		end
	else
		begin
			pom := wsk;
			
			if (pom^.liczba > x) then
				begin
					nowy^.liczba := x;
					nowy^.nast := pom;
					pom := nowy;
				end
			else
				begin
					while (pom^.nast != nil) and (pom^.nast^.liczba < x) then
						pom := pom^.nast;
					
					if (pom^.nast = nil) then
						begin
							nowy^.liczba := x;
							nowy^.nast := nil;
							pom^.nast := nowy;
						end
					else
						begin
							nowy^.liczba := x;
							nowy^.nast := pom;
						end;
				end;
end;

Listy dwukierunkowe

1. Wstawianie elementu na początek listy.

type
	Lista = ^element;
	element = record
		liczba : integer;
		nast : Lista;
		pop : Lista;
	end;

procedure dodaj_na_poczatek(var wsk : Lista, x : integer);

var
	nowy : Lista;
	
begin
	new(nowy);
	
	if (wsk = nil) then
		begin
			nowy^.liczba := x;
			nowy^.nast := nil;
			nowy^.pop := nil;
			wsk := nowy;
		end
	else
		begin
			nowy^.liczba := x;
			nowy^.nast := wsk;
			nowy^.pop := nil;
			wsk^.pop := nowy;
			wsk := nowy;
		end;
end;

2. Wstawianie elementu na koniec listy.

type
	Lista = ^element;
	element = record
		liczba : integer;
		nast : Lista;
		pop : Lista;
	end;
	
procedure dodaj_na_koniec(var wsk : Lista, x : integer);

var
	nowy, pom : Lista;
	
begin
	new(nowy);
	
	if (wsk = nil) then
		begin
			nowy^.liczba := x;
			nowy^.nast := nil;
			nowy^.pop := nil;
			wsk := nowy;
		end
	else
		begin
			pom := wsk;
			
			while (pom^.nast != nil) then
				pom := pom^.nast;
				
			nowy^.liczba = x;
			nowy^.nast := nil;
			nowy^.pop := pom;
			pom := nowy;
		end;
end;

3. Wstawianie elementu do listy z sortowaniem rosnąco.

type
	Lista = ^element;
	element = record
		liczba : integer;
		nast : Lista;
		pop : Lista;
	end;
	
procedure dodaj_sort_rosnoco(var wsk : Lista, x : integer);

var
	nowy, pom, pom2 : Lista;
	
begin
	new(nowy)
	
	if (wsk = nil) then
		begin
			nowy^.liczba := x;
			nowy^.nast := nil;
			nowy^.pop := nil;
			wsk := nowy;
		end
	else
		begin
			pom := wsk;
			
			if (pom^.liczba > x) then
				begin
					nowy^.liczba := x;
					nowy^.nast := pom;
					nowy^.pop := nil;
					pom^.pop := nowy;
					pom := nowy;
				end
			else
				begin
					while (pom^.nast != nil) and (pom^.nast^.liczba < x) then
						pom := pom^.nast;
					
					if (pom^.nast = nil) then
						begin
							nowy^.liczba := x;
							nowy^.nast := nil;
							nowy^.pop := pom;
							pom^.nast := nowy;
						end
					else
						begin
							pom2 := pom^.pop;
							nowy^.liczba := x;
							nowy^.nast := pom;
							nowy^.pop := pom2;
							pom^.pop := nowy;
						end;
				end;
end;

Chciałem tylko zapytać czy kod, który napisałem będzie działał.

No to nas się pytasz? Uruchom ten kod i sprawdź czy działa prawidłowo.

type
    Lista = ^element;
    element = record
        liczba : integer;
        nast : Lista;
    end;

No nie bardzo - kod pisze się w języku angielskim oraz przyjęło się, aby typy poprzedzać prefiksem T, a typy wskaźnikowe prefiksem P. Deklaracja tych typów powinna wyglądać np. tak:

type
  PListNode = ^TListNode;
  TListNode = record
    Number: Integer;
    Next: PListNode;
  end;

1. Wstawianie elementu na początek listy.

Parametr powinien przyjmować wskaźnik na głowę listy, więc musi to sugerować swoją nazwą. Poza tym, dane do pola nowego węzła powinny być wpisane bez względu na istnienie węzła głowy listy - ta operacja nie zależy od spełnienia warunku, więc powinna być przed nim:

procedure AddToFront(var AHead: PListNode; const ANumber: Integer);
var
  NewNode: PListNode;
begin
  New(NewNode);
  NewNode^.Number := ANumber;
  
  if AHead = nil then
  begin
    NewNode^.Next := nil;
    AHead := NewNode;
  end
  else
  begin
    NewNode^.Next := AHead;
    AHead := NewNode;
  end;
end;

2. Wstawianie elementu na koniec listy.

Tutaj podobnie - parametry powinny mieć sensowniejsze nazwy, a dane powinny być wpisywane do nowego węzła przed warunkiem, bo od jego spełnienia nie zależą. Również bez względu na to, czy głowa listy istnieje czy nie, nowy węzeł wstawiany na koniec listy zawsze będzie wskazywał na nil jako nastepny węzeł, więc to również nie powinno być w warunku:

procedure AddToBack(var AHead: PListNode; const ANumber: Integer);
var
  NewNode, TailNode: PListNode;
begin
  New(NewNode);
  NewNode^.Next := nil;
  NewNode^.Number := ANumber;
  
  if AHead = nil then
    AHead := NewNode
  else
  begin
    TailNode := AHead;
    
    while TailNode^.Next <> nil do
      TailNode := TailNode^.Next;
      
    TailNode^.Next := NewNode;
  end;
end;

3. Wstawianie elementu do listy z sortowaniem rosnąco.

Za dużo kodu napisałeś - operacja wstawiania węzłów do listy z zachowaniem kolejności sortowania rosnąco wcale nie jest taka trudna, jak to się może wydawać. Trzeba rozróżnić trzy przypadki:

• lista jest pusta - nowy węzeł będzie głową listy,
• lista zawiera n węzłow i pierwszy węzeł zawiera wartość większą niż nowy - nowy węzeł również będzie głową listy,
• pozostałe przypadki - szukamy węzła z mniejszą liczbą i nowy węzeł umieszczamy przed nim.

Punkt trzeci jest najtrudniejszy, dlatego też pasuje mieć pod ręką wskaźnik na poprzedni węzeł względem aktualnie sprawdzanego. Poniżej przykład takiej procedury:

procedure AddSorted(var AHead: PListNode; const ANumber: Integer);
var
  NewNode, PrevNode, CurrNode: PListNode;
begin
  New(NewNode);
  NewNode^.Number := ANumber;

  if AHead = nil then
  begin
    NewNode^.Next := nil;
    AHead := NewNode;
  end
  else
    if AHead^.Data > AData then
    begin
      NewNode^.Next := AHead;
      AHead := NewNode;
    end
    else
    begin
      PrevNode := AHead;
      CurrNode := AHead^.Next;

      while (CurrNode <> nil) and (CurrNode^.Number < ANumber) do
      begin
        PrevNode := CurrNode;
        CurrNode := CurrNode^.Next;
      end;

      PrevNode^.Next := NewNode;
      NewNode^.Next := CurrNode;
    end;
end;

W procedurach dotyczących listy dwukierunkowej zastosuj identyczny schemat.

Poza tym, podczas używania list jedno- czy dwukierunkowych, warto trzymać dwa wskaźniki - jeden na głowę listy (pierwszy węzeł), a drugi na jej ogon (ostatni). Dzięki temu dodanie nowego węzła na koniec listy nie będzie oznaczało iterowania po wszystkich jej węzłach. Dwa wskaźniki można sobie ładnie opakować w strukturkę:

type
  PListNode = ^TListNode;
  TListNode = record
    Number: Integer;
    Next: PListNode;
  end;
  
type
  TLinkedList = record
    Head: PListNode;
    Tail: PListNode;
  end;

i przekazywać do procedur czy funkcji operujących na liście. Podane swoje kody pisałem z głowy - jakby co.