Domů » Informatika » Datová struktura » Seznam (datová struktura)

Seznam (datová struktura)

Seznam je jednou ze základních dynamických datových struktur, která pojme libovolné množství prvků (které je samozřejmě omezené množstvím dostupné paměti). Tyto prvky jsou „obaleny“ pomocnou datovou strukturou, která obsahuje ukazatele na sousednící pomocné struktury a tak umožňuje se mezi nimi efektivně pohybovat. 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 seznamu (hlavička, head, top), případně i na prvek poslední (patička, foot, tail). Bez nich by nebylo jasné, kde seznam začíná.

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)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Třída reprezentující jednosměrně zřetězený generický seznam.
  3.  *
  4.  * @author Vojtěch Hordějčuk
  5.  * @param <T>
  6.  * typ hodnot v seznamu
  7.  */
  8. public class SingleList<T>
  9. {
  10.   /**
  11.    * Třída reprezentující jeden prvek seznamu.
  12.    *
  13.    * @author Vojtěch Hordějčuk
  14.    * @param <T>
  15.    * typ hodnoty v prvku seznamu
  16.    */
  17.   private static class SingleListNode<T>
  18.   {
  19.     /**
  20.      * ukazatel na další prvek seznamu
  21.      */
  22.     public SingleListNode<T> next;
  23.     /**
  24.      * hodnota prvku seznamu
  25.      */
  26.     public T value;
  27.   }
  28.  
  29.   /**
  30.    * ukazatel na první prvek (hlavičku) seznamu
  31.    */
  32.   private SingleListNode<T> head;
  33.   /**
  34.    * ukazatel na poslední prvek (patičku) seznamu
  35.    */
  36.   private SingleListNode<T> tail;
  37.  
  38.   /**
  39.    * Vytvoří nový seznam.
  40.    */
  41.   public SingleList ()
  42.   {
  43.     this.head = null;
  44.     this.tail = null;
  45.   }
  46.  
  47.   /**
  48.    * Vloží hodnotu na konec seznamu.
  49.    *
  50.    * @param value
  51.    * hodnota
  52.    */
  53.   public void append (final T value)
  54.   {
  55.     // vytvořit nový prvek
  56.  
  57.     final SingleListNode<T> node = new SingleListNode<T> ();
  58.  
  59.     node.next = null;
  60.     node.value = value;
  61.  
  62.     if (this.head == null)
  63.     {
  64.       // seznam je prázdný, nový prvek bude hlavičkou i patičkou
  65.  
  66.       this.head = node;
  67.       this.tail = node;
  68.     }
  69.     else
  70.     {
  71.       // seznam není prázdný, nový prvek bude vložen na konec seznamu
  72.  
  73.       this.tail.next = node;
  74.       this.tail = node;
  75.     }
  76.   }
  77.  
  78.   /**
  79.    * Odebere první výskyt zadané hodnoty.
  80.    *
  81.    * @param value
  82.    * hodnota k odebrání
  83.    * @return TRUE právě když byla hodnota nalezena a odebrána
  84.    */
  85.   public boolean removeFirst (final T value)
  86.   {
  87.     SingleListNode<T> temp = this.head;
  88.     SingleListNode<T> temp_prev = null;
  89.  
  90.     while (temp != null)
  91.     {
  92.       if (temp.value.equals (value))
  93.       {
  94.         // hodnota byla nalezena, odpovídající prvek bude odebrán
  95.  
  96.         if (temp_prev == null)
  97.         {
  98.           // odebírá se první prvek
  99.  
  100.           this.head = temp.next;
  101.         }
  102.         else
  103.         {
  104.           // odebírá se obecný prvek
  105.  
  106.           temp_prev.next = temp.next;
  107.         }
  108.  
  109.         return true;
  110.       }
  111.  
  112.       // posun na další prvek
  113.  
  114.       temp_prev = temp;
  115.       temp = temp.next;
  116.     }
  117.  
  118.     return false;
  119.   }
  120.  
  121.   /**
  122.    * Odebere všechny výskyty zadané hodnoty.
  123.    *
  124.    * @param value
  125.    * hodnota k odebrání
  126.    */
  127.   public void removeAll (final T value)
  128.   {
  129.     SingleListNode<T> temp = this.head;
  130.     SingleListNode<T> temp_prev = null;
  131.  
  132.     while (temp != null)
  133.     {
  134.       if (temp.value.equals (value))
  135.       {
  136.         if (temp_prev == null)
  137.         {
  138.           // odebírá se první prvek
  139.  
  140.           this.head = temp.next;
  141.         }
  142.         else
  143.         {
  144.           // odebírá se obecný prvek
  145.  
  146.           temp_prev.next = temp.next;
  147.         }
  148.       }
  149.       else
  150.       {
  151.         // "temp_prev" musí vždy ukazovat na poslední nesmazaný prvek
  152.  
  153.         temp_prev = temp;
  154.       }
  155.  
  156.       // posun na další prvek
  157.  
  158.       temp = temp.next;
  159.     }
  160.   }
  161.  
  162.   /**
  163.    * Vyhledá hodnotu v seznamu.
  164.    *
  165.    * @param value
  166.    * hodnota k nalezení
  167.    * @return TRUE právě když byla hodnota nalezena
  168.    */
  169.   public boolean find (final T value)
  170.   {
  171.     SingleListNode<T> temp = this.head;
  172.  
  173.     while (temp != null)
  174.     {
  175.       if (temp.value.equals (value))
  176.       {
  177.         return true;
  178.       }
  179.  
  180.       temp = temp.next;
  181.     }
  182.  
  183.     return false;
  184.   }
  185.  
  186.   /**
  187.    * Vrátí hodnotu v hlavičce seznamu.
  188.    *
  189.    * @return hodnota hlavičky seznamu, nebo NULL
  190.    */
  191.   public T getHead ()
  192.   {
  193.     if (this.head == null)
  194.     {
  195.       return null;
  196.     }
  197.     else
  198.     {
  199.       return this.head.value;
  200.     }
  201.   }
  202.  
  203.   /**
  204.    * Vrátí hodnotu v patičcce seznamu.
  205.    *
  206.    * @return hodnota patičky seznamu, nebo NULL
  207.    */
  208.   public T getTail ()
  209.   {
  210.     if (this.tail == null)
  211.     {
  212.       return null;
  213.     }
  214.     else
  215.     {
  216.       return this.tail.value;
  217.     }
  218.   }
  219.  
  220.   @Override
  221.   public String toString ()
  222.   {
  223.     final StringBuffer buffer = new StringBuffer ();
  224.  
  225.     SingleListNode<T> temp = this.head;
  226.  
  227.     while (temp != null)
  228.     {
  229.       buffer.append (temp.value.toString () + " ");
  230.       temp = temp.next;
  231.     }
  232.  
  233.     return "[" + buffer.toString ().trim () + "]";
  234.   }
  235. }
Obousměrně zřetězený seznam (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Třída reprezentující obousměrně zřetězený generický seznam.
  3.  *
  4.  * @author Vojtěch Hordějčuk
  5.  * @param <T>
  6.  * typ hodnot v seznamu
  7.  */
  8. public class DoubleList<T>
  9. {
  10.   /**
  11.    * Třída reprezentující jeden prvek seznamu.
  12.    *
  13.    * @author Vojtěch Hordějčuk
  14.    * @param <T>
  15.    * typ hodnoty v prvku seznamu
  16.    */
  17.   private static class DoubleListNode<T>
  18.   {
  19.     /**
  20.      * ukazatel na předchozí prvek seznamu
  21.      */
  22.     public DoubleListNode<T> previous;
  23.     /**
  24.      * ukazatel na další prvek seznamu
  25.      */
  26.     public DoubleListNode<T> next;
  27.     /**
  28.      * hodnota prvku seznamu
  29.      */
  30.     public T value;
  31.   }
  32.  
  33.   /**
  34.    * ukazatel na první prvek (hlavičku) seznamu
  35.    */
  36.   private DoubleListNode<T> head;
  37.   /**
  38.    * ukazatel na poslední prvek (patičku) seznamu
  39.    */
  40.   private DoubleListNode<T> tail;
  41.  
  42.   /**
  43.    * Vytvoří nový seznam.
  44.    */
  45.   public DoubleList ()
  46.   {
  47.     this.head = null;
  48.     this.tail = null;
  49.   }
  50.  
  51.   /**
  52.    * Vloží hodnotu na konec seznamu.
  53.    *
  54.    * @param value
  55.    * hodnota
  56.    */
  57.   public void append (final T value)
  58.   {
  59.     // vytvořit nový prvek
  60.  
  61.     final DoubleListNode<T> node = new DoubleListNode<T> ();
  62.  
  63.     node.previous = null;
  64.     node.next = null;
  65.     node.value = value;
  66.  
  67.     if (this.head == null)
  68.     {
  69.       // seznam je prázdný, nový prvek bude hlavičkou i patičkou
  70.  
  71.       this.head = node;
  72.       this.tail = node;
  73.     }
  74.     else
  75.     {
  76.       // seznam není prázdný, nový prvek bude vložen na konec seznamu
  77.  
  78.       node.previous = this.tail;
  79.       this.tail.next = node;
  80.       this.tail = node;
  81.     }
  82.   }
  83.  
  84.   /**
  85.    * Odebere první výskyt zadané hodnoty.
  86.    *
  87.    * @param value
  88.    * hodnota k odebrání
  89.    * @return TRUE právě když byla hodnota nalezena a odebrána
  90.    */
  91.   public boolean removeFirst (final T value)
  92.   {
  93.     DoubleListNode<T> temp = this.head;
  94.  
  95.     while (temp != null)
  96.     {
  97.       if (temp.value.equals (value))
  98.       {
  99.         // hodnota byla nalezena, odpovídající prvek bude odebrán
  100.  
  101.         temp.next.previous = temp.previous;
  102.         temp.previous.next = temp.next;
  103.  
  104.         return true;
  105.       }
  106.  
  107.       // posun na další prvek
  108.  
  109.       temp = temp.next;
  110.     }
  111.  
  112.     return false;
  113.   }
  114.  
  115.   /**
  116.    * Odebere všechny výskyty zadané hodnoty.
  117.    *
  118.    * @param value
  119.    * hodnota k odebrání
  120.    */
  121.   public void removeAll (final T value)
  122.   {
  123.     DoubleListNode<T> temp = this.head;
  124.  
  125.     while (temp != null)
  126.     {
  127.       if (temp.value.equals (value))
  128.       {
  129.         if (temp.next != null)
  130.         {
  131.           temp.next.previous = temp.previous;
  132.         }
  133.  
  134.         if (temp.previous == null)
  135.         {
  136.           // odebírá se první prvek
  137.  
  138.           this.head = temp.next;
  139.         }
  140.         else
  141.         {
  142.           // odebírá se obecný prvek
  143.  
  144.           temp.previous.next = temp.next;
  145.         }
  146.       }
  147.  
  148.       // posun na další prvek
  149.  
  150.       temp = temp.next;
  151.     }
  152.   }
  153.  
  154.   /**
  155.    * Vyhledá hodnotu v seznamu.
  156.    *
  157.    * @param value
  158.    * hodnota k nalezení
  159.    * @return TRUE právě když byla hodnota nalezena
  160.    */
  161.   public boolean find (final T value)
  162.   {
  163.     DoubleListNode<T> temp = this.head;
  164.  
  165.     while (temp != null)
  166.     {
  167.       if (temp.value.equals (value))
  168.       {
  169.         return true;
  170.       }
  171.  
  172.       temp = temp.next;
  173.     }
  174.  
  175.     return false;
  176.   }
  177.  
  178.   /**
  179.    * Vrátí hodnotu v hlavičce seznamu.
  180.    *
  181.    * @return hodnota hlavičky seznamu, nebo NULL
  182.    */
  183.   public T getHead ()
  184.   {
  185.     if (this.head == null)
  186.     {
  187.       return null;
  188.     }
  189.     else
  190.     {
  191.       return this.head.value;
  192.     }
  193.   }
  194.  
  195.   /**
  196.    * Vrátí hodnotu v patičcce seznamu.
  197.    *
  198.    * @return hodnota patičky seznamu, nebo NULL
  199.    */
  200.   public T getTail ()
  201.   {
  202.     if (this.tail == null)
  203.     {
  204.       return null;
  205.     }
  206.     else
  207.     {
  208.       return this.tail.value;
  209.     }
  210.   }
  211.  
  212.   @Override
  213.   public String toString ()
  214.   {
  215.     final StringBuffer buffer = new StringBuffer ();
  216.  
  217.     DoubleListNode<T> temp = this.head;
  218.  
  219.     while (temp != null)
  220.     {
  221.       buffer.append (temp.value.toString () + " ");
  222.       temp = temp.next;
  223.     }
  224.  
  225.     return "[" + buffer.toString ().trim () + "]";
  226.   }
  227. }
Obousměrně zřetězený seznam II. (Java)

kód v jazyce Java - Zobrazit

  1. package seznam;
  2.  
  3. public class Seznam<T> {
  4.  
  5.     private Polozka<T> prvni = null;
  6.     private Polozka<T> posledni = null;
  7.  
  8.     public Seznam() {
  9.     }
  10.  
  11.     public boolean prazdny() {
  12.         return prvni == null;
  13.     }
  14.  
  15.     public void pridat(T hodnota) {
  16.         Polozka<T> nova = new Polozka<T>();
  17.         nova.hodnota = hodnota;
  18.  
  19.         if (prvni == null) {
  20.             prvni = nova;
  21.             posledni = nova;
  22.         } else {
  23.             posledni.next = nova;
  24.             nova.prev = posledni;
  25.             posledni = nova;
  26.         }
  27.     }
  28.  
  29.     public T vzitPosledni() {
  30.         if (posledni == null) {
  31.             throw new RuntimeException();
  32.         }
  33.  
  34.         T hodnota = posledni.hodnota;
  35.  
  36.         if (prvni == posledni) {
  37.             prvni = null;
  38.             posledni = null;
  39.         } else {
  40.             posledni.prev.next = null;
  41.             posledni = posledni.prev;
  42.         }
  43.  
  44.         return hodnota;
  45.     }
  46.  
  47.     public T vzitPrvni() {
  48.         if (prvni == null) {
  49.             throw new RuntimeException();
  50.         }
  51.  
  52.         T hodnota = prvni.hodnota;
  53.  
  54.         if (prvni == posledni) {
  55.             prvni = null;
  56.             posledni = null;
  57.         } else {
  58.             prvni.next.prev = null;
  59.             prvni = prvni.next;
  60.         }
  61.  
  62.         return hodnota;
  63.     }
  64.  
  65.     public void print() {
  66.         StringBuilder sb = new StringBuilder();
  67.         sb.append("[");
  68.         Polozka<T> temp = prvni;
  69.  
  70.         while (temp != null) {
  71.             sb.append(temp.hodnota);
  72.             temp = temp.next;
  73.             if (temp != null) {
  74.                 sb.append(", ");
  75.             }
  76.         }
  77.  
  78.         sb.append("]");
  79.         System.out.println(sb.toString());
  80.     }
  81.  
  82.     private static class Polozka<T> {
  83.  
  84.         T hodnota = null;
  85.         Polozka<T> next = null;
  86.         Polozka<T> prev = null;
  87.     }
  88. }

Reference