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.
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.
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.
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
001./**002. * Jednosmerne zretezeny spojovy seznam (bez zarazky)003. * @author Pavel Micka004. */005.public class LinkedList {006. 007. private Node first;008. private Node last;009. private int size;010. 011. public LinkedList() {012. this.size = 0;013. }014. 015. /**016. * Vlozi prvek na konec seznamu017. * @param i prvek k vlozeni018. */019. public void insert(int i) {020. Node n = new Node(i);021. if (size == 0) {022. this.first = n;023. this.last = n;024. } else {025. this.last.next = n;026. this.last = n;027. }028. size++;029. }030. 031. /**032. * Vrati prvek na indexu i033. * @return prvek na indexu i034. */035. public int read(int i) {036. if (i >= size) {037. throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);038. }039. if (i < 0) {040. throw new IllegalArgumentException("Index mensi nez 0");041. }042. Node curr = first;043. for (int j = 0; j < i; j++) {044. curr = curr.next;045. }046. return curr.value;047. }048. 049. /**050. * Smaze prvek na indexu i051. * @param i index mazaneho prvku052. */053. public void delete(int i) {054. if (i >= size) {055. throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);056. }057. if (i < 0) {058. throw new IllegalArgumentException("Index mensi nez 0");059. }060. if (i == 0) {061. first = first.next;062. } else {063. Node curr = first;064. for (int j = 0; j < i - 1; j++) { //najdeme predchozi065. curr = curr.next;066. }067. curr.next = curr.next.next; //a mazany prvek vynechame068. if (i == size - 1) { //pokud mazeme posledni069. last = curr;070. }071. }072. size--;073. }074. 075. /**076. * Delka seznamu077. * @return delka seznamu078. */079. public int size() {080. return this.size;081. }082. 083. /**084. * Klasicka toString metoda, vraci textovou reprezentaci objektu085. * @return textova reprezentace objektu086. */087. @Override088. public String toString() {089. StringBuilder builder = new StringBuilder();090. Node curr = first;091. for (int i = 0; i < this.size; i++) {092. builder.append(curr.value).append(" ");093. curr = curr.next;094. }095. return builder.toString();096. }097. 098. /**099. * Vnitrni trida reprezentujici uzel spojoveho seznamu100. */101. private class Node {102. 103. private int value;104. private Node next;105. 106. private Node(int value) {107. this.value = value;108. }109. }110.}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>.