Spojový seznam (Lineární seznam, Linked list) je kontejner určený k ukládání dat předem neznámé délky. Základní stavební jednotkou spojového seznamu je uzel, který vždy obsahuje ukládanou hodnotu a ukazatel na následující prvek.

Varianty spojového seznamu

Jednosměrně zřetězený seznam

Jednosměrně zřetězený seznam je základní variantou této datové struktury, ve které jednotlivé uzly obsahují kromě dat pouze ukazatel na další uzel (poslední uzel ukazuje na null), čímž umožňují pouze traverzování jedním směrem. Samotná struktura seznamu pak obsahuje pouze ukazatel na první prvek a data jsou přidávána vždy na začátek seznamu. Dílčím vylepšením je přidání ukazatele také na poslední prvek a umisťování nových prvků na konec seznamu.

Jednosměrně zřetězený spojový seznam

Obousměrně zřetězený spojový seznam

V obousměrně zřetězeném spojovém seznamu prvky obsahují nejen ukazatel na další prvek, ale také ukazatel na předchozí prvek. Tímto se sice poněkud zkomplikuje implementace struktury, ale toto je vyváženo zvýšenou flexibilitou, protože lze traverzovat v obou směrech.

Obousměrně zřetězený spojový seznam

Kruhový spojový seznam

Velmi oblíbeným trikem zjednodušujícím implementaci spojového seznamu je kruhový spojový seznam s hlídkou (sentinel). V této implementaci struktura seznamu obsahuje vždy ukazatel na objekt hlídky – speciálního uzlu, který slouží zároveň jako první a jako poslední prvek (v případě prázdného seznamu ukazuje sám na sebe). Tímto trikem dojde ke ztotožnění operací vložení na začátek, konec a mezi prvky spojového seznamu. Nevýhodou tohoto přístupu jsou dodatečné paměťové nároky na objekt hlídky.

Kruhový spojový seznam

Zjednodušení vyhledávání

Vyhledávání ve spojovém seznamu můžeme zjednodušit použitím zarážky – zarážka je uzel zvláštího typu umístěný na konec seznamu (v případě použití hlídky bude hlídka zarážkou). Do zarážky vždy umístíme data, která vyhledáváme, čímž si zajistíme, že je také najdeme. Tímto trikem eliminujeme nutnost neustálé kontroly toho, jestli již nejsme na konci seznamu.

Iterátor

Pro efektivní využití libovolného typu spojového seznamu je zapotřebí vytvořit tzv. iterátor, což je objekt, který při průchodu seznamem udržuje odkaz na aktuální pozici a umožní z ní pokračovat dále nebo se vrátit zpět (při použití obousměrně zřetězeného seznamu). Bez této struktury by byl průchod seznamem neúnosně drahou operací, protože by se při každém přístupu na další položku musel tento prvek vždy nejprve vyhledat (tj. projít celý seznam od začátku až na danou pozici).

Složitost základních operací

Operace vkládání na začátek seznamu proběhne s asymptotickou složitostí , protože se pouze zalokuje nový prvek, který se vloží na počátek seznamu. Operace mazání a čtení prvku na indexu i proběhnou v čase , protože spojový seznam neumožňuje náhodný přístup - k prvku je zapotřebí doiterovat.

Kód

  /**
   * Jednosmerne zretezeny spojovy seznam (bez zarazky)
   * @author Pavel Micka
   */
  public class LinkedList {
  
      private Node first;
      private Node last;
      private int size;
  
      public LinkedList() {
          this.size = 0;
      }
  
      /**
       * Vlozi prvek na konec seznamu
       * @param i prvek k vlozeni
       */
      public void insert(int i) {
          Node n = new Node(i);
          if (size == 0) {
              this.first = n;
              this.last = n;
          } else {
              this.last.next = n;
              this.last = n;
          }
          size++;
      }
  
      /**
       * Vrati prvek na indexu i
       * @return prvek na indexu i
       */
      public int read(int i) {
          if (i >= size) {
              throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
          }
          if (i < 0) {
              throw new IllegalArgumentException("Index mensi nez 0");
          }
          Node curr = first;
          for (int j = 0; j < i; j++) {
              curr = curr.next;
          }
          return curr.value;
      }
  
      /**
       * Smaze prvek na indexu i
       * @param i index mazaneho prvku
       */
      public void delete(int i) {
          if (i >= size) {
              throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
          }
          if (i < 0) {
              throw new IllegalArgumentException("Index mensi nez 0");
          }
          if (i == 0) {
              first = first.next;
          } else {
              Node curr = first;
              for (int j = 0; j < i - 1; j++) { //najdeme predchozi
                  curr = curr.next;
              }
              curr.next = curr.next.next; //a mazany prvek vynechame
              if (i == size - 1) { //pokud mazeme posledni
                  last = curr;
              }
          }
          size--;
      }
  
      /**
       * Delka seznamu
       * @return delka seznamu
       */
      public int size() {
          return this.size;
      }
  
      /**
       * Klasicka toString metoda, vraci textovou reprezentaci objektu
       * @return textova reprezentace objektu
       */
      @Override
      public String toString() {
          StringBuilder builder = new StringBuilder();
          Node curr = first;
          for (int i = 0; i < this.size; i++) {
              builder.append(curr.value).append(" ");
              curr = curr.next;
          }
          return builder.toString();
      }
  
      /**
       * Vnitrni trida reprezentujici uzel spojoveho seznamu
       */
      private class Node {
  
          private int value;
          private Node next;
  
          private Node(int value) {
              this.value = value;
          }
      }
  }
  

Literatura

• ALON, Joni. Joni's Home Page [online]. 2005 [cit. 2010-08-26]. Doubly-Linked List. Dostupné z WWW: <http://cs-people.bu.edu/jalon/cs113-01/dlistlab/dlist.html>.