Seznam (datová struktura)
Seznam je jednou ze základních dynamických datových struktur, která pojme libovolné množství prvků. Tyto prvky jsou „obaleny“ pomocnou datovou strukturou, která obsahuje ukazatele. Podle počtu a cílů těchto ukazatelů rozlišujeme jednotlivé druhy seznamů. V jedné pomocné proměnné je dále třeba udržovat ukazatel na první prvek (hlavička, head), případně i na prvek poslední (patička, tail).
Jednosměrně zřetězený seznam
Každý prvek obsahuje právě jeden odkaz na následující prvek. Poslední prvek ukazuje na NULL, tedy na neplatnou hodnotu. Podle toho při procházení poznáme, že se jedná o poslední prvek.
jednosměrně zřetězený seznam
Cyklický jednosměrně zřetězený seznam
Cyklický jednosměrný seznam je shodný se seznamen jednosměrně zřetězeným až na to, že poslední prvek má jako následníka prvek první. Tím docílíme toho, že při procházení seznamu nikdy nedojdeme na konec. V konzistentním stavu (po dokončení všech operací) by žádný prvek neměl ukazovat na neplatnou adresu (NULL).
cyklický jednosměrně zřetězený seznam
Obousměrně zřetězený seznam
Každý prvek obsahuje odkaz na následující i předchozí prvek. Seznam je tedy možné seznam procházet dvěma směry. Jako následník posledního prvku a předchůdce prvního je nastavena neplatná adresa (NULL), abychom poznali, že jsme na některém konci seznamu.
obousměrně zřetězený seznam
Cyklický obousměrně zřetězený seznam
Následníkem posledního prvku cyklického obousměrně zřetězeného seznamu je prvek první. Analogicky je i předchůdcem prvního prvku prvek poslední. V konzistentním stavu (po dokončení všech operací) by žádný prvek neměl ukazovat na neplatnou adresu (NULL).
cyklický obousměrně zřetězený seznam
Výhody a nevýhody
Výhody seznamu
Narozdíl od pole nemusí prvky následovat v paměti lineárně za sebou a tak se může počet prvků dynamicky rozrůstat bez potřeby realokovat paměťový prostor. Při zvětšování seznamu stačí vytvořit nový prvek a spojit jej pomocí ukazatelů s ostatními.
Nevýhody seznamu
Právě ona „roztříštěnost“ seznamu, kdy je každý prvek na libolném místě v paměti, zvyšuje časovou náročnost některých operací (např. vyhledávání, vkládání, mazání). Seznam je totiž nutné často procházet, protože neznáme přesná umístění všech prvků. Také implementace seznamu je složitější, protože je nutné pracovat korektně s ukazateli.
Implementace
Jednosměrně zřetězený seznam (Java)
* Třída reprezentující jednosměrně zřetězený generický seznam.
*
* @author Vojtěch Hordějčuk
* @param <T>
* typ hodnot v seznamu
*/
public class SingleList<T>
{
/**
* Třída reprezentující jeden prvek seznamu.
*
* @author Vojtěch Hordějčuk
* @param <T>
* typ hodnoty v prvku seznamu
*/
private static class SingleListNode<T>
{
/**
* ukazatel na další prvek seznamu
*/
public SingleListNode<T> next;
/**
* hodnota prvku seznamu
*/
public T value;
}
/**
* ukazatel na první prvek (hlavičku) seznamu
*/
private SingleListNode<T> head;
/**
* ukazatel na poslední prvek (patičku) seznamu
*/
private SingleListNode<T> tail;
/**
* Vytvoří nový seznam.
*/
public SingleList ()
{
this.head = null;
this.tail = null;
}
/**
* Vloží hodnotu na konec seznamu.
*
* @param value
* hodnota
*/
public void append (final T value)
{
// vytvořit nový prvek
final SingleListNode<T> node = new SingleListNode<T> ();
node.next = null;
node.value = value;
if (this.head == null)
{
// seznam je prázdný, nový prvek bude hlavičkou i patičkou
this.head = node;
this.tail = node;
}
else
{
// seznam není prázdný, nový prvek bude vložen na konec seznamu
this.tail.next = node;
this.tail = node;
}
}
/**
* Odebere první výskyt zadané hodnoty.
*
* @param value
* hodnota k odebrání
* @return TRUE právě když byla hodnota nalezena a odebrána
*/
public boolean removeFirst (final T value)
{
SingleListNode<T> temp = this.head;
SingleListNode<T> temp_prev = null;
while (temp != null)
{
if (temp.value.equals (value))
{
// hodnota byla nalezena, odpovídající prvek bude odebrán
if (temp_prev == null)
{
// odebírá se první prvek
this.head = temp.next;
}
else
{
// odebírá se obecný prvek
temp_prev.next = temp.next;
}
return true;
}
// posun na další prvek
temp_prev = temp;
temp = temp.next;
}
return false;
}
/**
* Odebere všechny výskyty zadané hodnoty.
*
* @param value
* hodnota k odebrání
*/
public void removeAll (final T value)
{
SingleListNode<T> temp = this.head;
SingleListNode<T> temp_prev = null;
while (temp != null)
{
if (temp.value.equals (value))
{
if (temp_prev == null)
{
// odebírá se první prvek
this.head = temp.next;
}
else
{
// odebírá se obecný prvek
temp_prev.next = temp.next;
}
}
else
{
// "temp_prev" musí vždy ukazovat na poslední nesmazaný prvek
temp_prev = temp;
}
// posun na další prvek
temp = temp.next;
}
}
/**
* Vyhledá hodnotu v seznamu.
*
* @param value
* hodnota k nalezení
* @return TRUE právě když byla hodnota nalezena
*/
public boolean find (final T value)
{
SingleListNode<T> temp = this.head;
while (temp != null)
{
if (temp.value.equals (value))
{
return true;
}
temp = temp.next;
}
return false;
}
/**
* Vrátí hodnotu v hlavičce seznamu.
*
* @return hodnota hlavičky seznamu, nebo NULL
*/
public T getHead ()
{
if (this.head == null)
{
return null;
}
else
{
return this.head.value;
}
}
/**
* Vrátí hodnotu v patičcce seznamu.
*
* @return hodnota patičky seznamu, nebo NULL
*/
public T getTail ()
{
if (this.tail == null)
{
return null;
}
else
{
return this.tail.value;
}
}
@Override
public String toString ()
{
final StringBuffer buffer = new StringBuffer ();
SingleListNode<T> temp = this.head;
while (temp != null)
{
buffer.append (temp.value.toString () + " ");
temp = temp.next;
}
return "[" + buffer.toString ().trim () + "]";
}
}
zdrojový kód (Java) - zobrazit (4114 znaků)
Obousměrně zřetězený seznam (Java)
* Třída reprezentující obousměrně zřetězený generický seznam.
*
* @author Vojtěch Hordějčuk
* @param <T>
* typ hodnot v seznamu
*/
public class DoubleList<T>
{
/**
* Třída reprezentující jeden prvek seznamu.
*
* @author Vojtěch Hordějčuk
* @param <T>
* typ hodnoty v prvku seznamu
*/
private static class DoubleListNode<T>
{
/**
* ukazatel na předchozí prvek seznamu
*/
public DoubleListNode<T> previous;
/**
* ukazatel na další prvek seznamu
*/
public DoubleListNode<T> next;
/**
* hodnota prvku seznamu
*/
public T value;
}
/**
* ukazatel na první prvek (hlavičku) seznamu
*/
private DoubleListNode<T> head;
/**
* ukazatel na poslední prvek (patičku) seznamu
*/
private DoubleListNode<T> tail;
/**
* Vytvoří nový seznam.
*/
public DoubleList ()
{
this.head = null;
this.tail = null;
}
/**
* Vloží hodnotu na konec seznamu.
*
* @param value
* hodnota
*/
public void append (final T value)
{
// vytvořit nový prvek
final DoubleListNode<T> node = new DoubleListNode<T> ();
node.previous = null;
node.next = null;
node.value = value;
if (this.head == null)
{
// seznam je prázdný, nový prvek bude hlavičkou i patičkou
this.head = node;
this.tail = node;
}
else
{
// seznam není prázdný, nový prvek bude vložen na konec seznamu
node.previous = this.tail;
this.tail.next = node;
this.tail = node;
}
}
/**
* Odebere první výskyt zadané hodnoty.
*
* @param value
* hodnota k odebrání
* @return TRUE právě když byla hodnota nalezena a odebrána
*/
public boolean removeFirst (final T value)
{
DoubleListNode<T> temp = this.head;
while (temp != null)
{
if (temp.value.equals (value))
{
// hodnota byla nalezena, odpovídající prvek bude odebrán
temp.next.previous = temp.previous;
temp.previous.next = temp.next;
return true;
}
// posun na další prvek
temp = temp.next;
}
return false;
}
/**
* Odebere všechny výskyty zadané hodnoty.
*
* @param value
* hodnota k odebrání
*/
public void removeAll (final T value)
{
DoubleListNode<T> temp = this.head;
while (temp != null)
{
if (temp.value.equals (value))
{
if (temp.next != null)
{
temp.next.previous = temp.previous;
}
if (temp.previous == null)
{
// odebírá se první prvek
this.head = temp.next;
}
else
{
// odebírá se obecný prvek
temp.previous.next = temp.next;
}
}
// posun na další prvek
temp = temp.next;
}
}
/**
* Vyhledá hodnotu v seznamu.
*
* @param value
* hodnota k nalezení
* @return TRUE právě když byla hodnota nalezena
*/
public boolean find (final T value)
{
DoubleListNode<T> temp = this.head;
while (temp != null)
{
if (temp.value.equals (value))
{
return true;
}
temp = temp.next;
}
return false;
}
/**
* Vrátí hodnotu v hlavičce seznamu.
*
* @return hodnota hlavičky seznamu, nebo NULL
*/
public T getHead ()
{
if (this.head == null)
{
return null;
}
else
{
return this.head.value;
}
}
/**
* Vrátí hodnotu v patičcce seznamu.
*
* @return hodnota patičky seznamu, nebo NULL
*/
public T getTail ()
{
if (this.tail == null)
{
return null;
}
else
{
return this.tail.value;
}
}
@Override
public String toString ()
{
final StringBuffer buffer = new StringBuffer ();
DoubleListNode<T> temp = this.head;
while (temp != null)
{
buffer.append (temp.value.toString () + " ");
temp = temp.next;
}
return "[" + buffer.toString ().trim () + "]";
}
}
zdrojový kód (Java) - zobrazit (4002 znaků)