Procedura sortowania przy wstawieniu do listy

Witam,
Jak w temacie, mój wykładowca zażądał sobie funkcję, która wstawia element do listy 'w odpowiednim miejscu', czyli sortuje przy okazji. Kod wygląda następująco:

type
    pElem = ^TElem;
    TElem = record
      data: TRekord;
      next: pElem;
      prev: pElem;
    end;

    TList = record
      head: pElem;
      tail: pElem;
      pos: pElem;
    end;

procedure pushSortByAgeInc(var list: TList; var elem: pElem);
  var temp: pElem;
  begin
    if (list.head = nil) then
    begin
      addElemToEmptyList(list, elem);
    end
    else
    begin
      temp := list.head;
      while (temp^.next <> nil) AND (temp^.data.age <= elem^.data.age) do
      begin
        temp := temp^.next;
      end;

      if (temp^.next = nil) AND (temp^.data.age <= elem^.data.age) then
        pushBack(list, elem)
      else if (temp^.prev = nil) then
        pushFront(list, elem)
      else
      begin
        elem^.next := temp;
        elem^.prev := temp^.prev;
        temp^.prev^.next := elem;
        temp^.prev := elem;
      end;
    end;
  end; 

Procedura działa jak należy, wstawia element na swoje miejsce, ustawiając go poprawnie względem innych, ale mam jeden problem. Ta procedura jest a) zbyt długa, b) niejasna i robi kilka rzeczy na raz. Ktoś ma jakieś pomysły jak można ją podzielić, ew. pozmieniać nazwy, żeby było ok?

Skorzystaj z mojego artykułu - http://4programmers.net/Delphi/Implementacja_listy_dwukierunkowej_ze_znacznikiem

Co prawda działa ona nieco inaczej (dodatkowy znacznik), ale ogólna zasada jest taka sama (to też lista dwukierunkowa); W tym artykule opisana jest metoda InsertElement - ona odpowiada za wstawianie nowego węzła w zadane miejsce listy; Ona bazuje na indeksie, więc musisz zamienić iterowanie na podstawie indeksu na iterowanie w celu znalezienia odpowiedniego miejsca dla nowego elementu;

PS: Pomiń wszystko co dotyczy znacznika, bo tego nie potrzebujesz;

Ta procedura jest a) zbyt długa, b) niejasna i robi kilka rzeczy na raz.

Nie jest zbyt długa - dobrze, że skorzystałeś z osobnej procedury do wstawienia elementu, jeśli lista jest pusta (dzięki temu kod omawianej procedurki jest faktycznie krótki); Jedyne co mnie zastanawia to to, dlaczego w argumencie podajesz wskaźnik na już utworzony węzeł, zamiast gołych danych (czyli rekordu typu TRekord - popraw tę nazwę); Nie twierdzę jednak że jest to błąd - nie widziałem pozostałego kodu.

Jak zobaczyłem geniusz rozwiązania, w którym każdy element ma swój indeks, to stwierdziłem, że czas dodać taką funkcjonalność do mojej listy. Do tego zastanowiłem się, czy faktycznie dobrze jest przyjmować utworzony element, bo wtedy użytkownik listy będzie musiał sam je tworzyć i doszedłem do wniosku, że to tez należy zmienić. Wymyśliłem, że napiszę procedurę pushAtIndex, która będzie wstawiała element w określone miejsce, a potem zrobię procedurę znajdującą indeks, na który trzeba wstawić, żeby się sortowało. Procedura pushSortByAge będzie wywoływała znalezienie indeksu i wstawienie. Myślę, że będzie to o wiele bardziej eleganckie rozwiązanie. Dzięki za odpowiedź ;)

Jak zobaczyłem geniusz rozwiązania, w którym każdy element ma swój indeks, to stwierdziłem, że czas dodać taką funkcjonalność do mojej listy.

Tzn. w mojej liście, każdy węzeł jest zwykłym węzłem i oprócz wskaźników na poprzedni i następny węzeł, nie posiada żadnych dodatkowych informacji o jego położeniu:

type
  PListNode = ^TListNode;
  TListNode = record
    PreviousNode: PListNode;  // wskaźnik na poprzedni węzeł
    NextNode: PListNode;      // wskaźnik na następny węzeł
    Element: TObject;        // dane węzła
  end;

Różnica natomiast jest taka, że dostęp do elementów uzyskuje się tylko i wyłącznie na podstawie indeksu - tak jak do zwykłej macierzy;

Do tego zastanowiłem się, czy faktycznie dobrze jest przyjmować utworzony element, bo wtedy użytkownik listy będzie musiał sam je tworzyć i doszedłem do wniosku, że to tez należy zmienić.

Zależy jaki efekt Cię interesuje;

Jeżeli Twoja lista, na podobieństwo mojej, ma stanowić bazowy kontener możliwy do rozszerzania, a tym samym do przechowywania danych dowolnego typu, powinieneś wybrać jakiś ogólny typ danych, np. Pointer; Kod rozszerzający bazową implementację i konkretyzujący typ danych, które mają być w liście zawarte, powinien pobierać gołe dane w parametrach i maskować ewentualne rzutowanie (bo bez tego nie obejdzie się);

Wymyśliłem, że napiszę procedurę pushAtIndex, która będzie wstawiała element w określone miejsce, a potem zrobię procedurę znajdującą indeks, na który trzeba wstawić, żeby się sortowało. Procedura pushSortByAge będzie wywoływała znalezienie indeksu i wstawienie.

O to chodzi - uruchamiasz swoją PushSortByAge i wyliczasz indeks, po czym ten indeks (i dane) przekazujesz do wywołania PushAtIndex, a ta z kolei robi całą robotę związaną z alokacją pamięci i reorganizacją listy.