Lista: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
uogólnienie |
m zamiana implementacji |
||
Linia 4:
== Implementacja listy ==
Istnieją dwie popularne [[Implementacja (informatyka)|implementacje]] struktury listy: tablicowa i wskaźnikowa.
=== Tablicowa ===▼
Jak wskazuje nazwa, lista zaimplementowana w ten sposób opiera się na [[Tablica (informatyka)|tablicy]] obiektów (lub rekordów) danego typu. ▼
'''Dopisanie elementu''' do listy to wstawienie elementu do tablicy: ▼
* jeśli ma ono nastąpić na końcu listy, będzie to kolejny element w tablicy;▼
* jeśli nowy element ma znaleźć się między innymi elementami, należy przesunąć o jedno pole w prawo wszystkie elementy o indeksie wyższym niż pole, na które będzie wstawiany obiekt; następnie w powstałą lukę wpisuje się nowy element.▼
'''Usunięcie elementu''' znajdującego się pod danym indeksem tablicy to przesunięcie o jedno pole w lewo wszystkich elementów o indeksie wyższym.▼
'''Zalety''' tej implementacji: prosta nawigacja wewnątrz listy, korzystanie z gotowej struktury tablicy, szybki dostęp do elementu o konkretnym numerze, większa odporność na błędy.▼
'''Wady''': niska elastyczność, szczególnie dotycząca rozmiaru tablicy, liniowa [[Złożoność obliczeniowa|złożoność]] operacji wstawiania i usuwania.▼
Implementację tablicową stosuje się tam, gdzie elastyczność nie odgrywa istotnej roli, a wymagana jest szybka i prosta nawigacja.▼
=== Wskaźnikowa ===
Linia 50 ⟶ 35:
Zaletą takiej reprezentacji jest oszczędność pamięci (jeden wskaźnik, zamiast dwóch), wadą natomiast utrudnione przeglądanie - jeśli nie rozpoczyna się od pierwszego lub ostatniego elementu, potrzeba znać co najmniej dwa wskaźniki w celu odkodowania rzeczywistych wartości.
▲=== Tablicowa ===
▲Jak wskazuje nazwa, lista zaimplementowana w ten sposób opiera się na [[Tablica (informatyka)|tablicy]] obiektów (lub rekordów) danego typu.
▲'''Dopisanie elementu''' do listy to wstawienie elementu do tablicy:
▲* jeśli ma ono nastąpić na końcu listy, będzie to kolejny element w tablicy;
▲* jeśli nowy element ma znaleźć się między innymi elementami, należy przesunąć o jedno pole w prawo wszystkie elementy o indeksie wyższym niż pole, na które będzie wstawiany obiekt; następnie w powstałą lukę wpisuje się nowy element.
▲'''Usunięcie elementu''' znajdującego się pod danym indeksem tablicy to przesunięcie o jedno pole w lewo wszystkich elementów o indeksie wyższym.
▲'''Zalety''' tej implementacji: prosta nawigacja wewnątrz listy, korzystanie z gotowej struktury tablicy, szybki dostęp do elementu o konkretnym numerze, większa odporność na błędy.
▲'''Wady''': niska elastyczność, szczególnie dotycząca rozmiaru tablicy, liniowa [[Złożoność obliczeniowa|złożoność]] operacji wstawiania i usuwania.
▲Implementację tablicową stosuje się tam, gdzie elastyczność nie odgrywa istotnej roli, a wymagana jest szybka i prosta nawigacja.
== Zobacz też ==
| |||