Lista înlănțuită
Scris de Denis Nuțiu
- 4 minute de citit
- 6 exemple de cod în Kotlin
- 1 imagine
Disponibil și în English
Pe această pagină
Introducere
O listă înlănțuită este o structură de date fundamentală formată din noduri conectate între ele.
Alte variante sunt:
- Lista dublu înlănțuită
- Lista circulară înlănțuită (buffer circular)
Lista simplu înlănțuită
Pentru a vizualiza structura de date, dacă vrei să stochezi două numere întregi, 10 și 20, vei avea o listă cu 2 noduri care arată așa: [Nodul 1, Valoarea 10] -> [Nodul 2, Valoarea: 20] -> [null]
Nodul 1 indică spre Nodul 2, iar Nodul 2 indică spre null.
Structura de date Lista înlănțuită permite stocarea datelor într-un mod eficient.
Spre deosebire de tablouri, structura de date lista înlănțuită nu alocă spațiu dinainte pentru date. Ea crește și se micșorează în timpul execuției, atunci când este nevoie.
Lista înlănțuită are multe aplicații, dar iată câteva:
- Implementarea funcției de anulare-refacere (undo-redo) într-un editor de text.
- Reprezentarea unei liste de melodii.
-
Gestionarea unui cache în care intrările sunt adăugate și eliminate în funcție de utilizare.
- Stocarea datelor într-un sistem cu memorie limitată, cum ar fi sistemele embedded.
- Buffering.
În funcție de implementare, poate suporta operații precum:
- inserarea unui element la o poziție
- adăugarea unui element la final
- ștergerea ultimului element
- ștergerea unui element
- obținerea primului element
- obținerea ultimului element
- obținerea unui element de la o poziție
- inversarea listei
Complexitatea spațiului și a timpului
Complexitatea spațiului și a timpului pentru operațiile unei liste înlănțuite depinde de implementare.
O implementare de bază, care stochează nodul de cap (head) și nodul de coadă (tail), are următoarea complexitate:
Complexitatea spațiului este O(N), lista crește sau se micșorează liniar, în funcție de câte elemente sunt adăugate în timpul execuției.
Complexitatea timpului diferă pentru fiecare operație:
- Adăugarea unui element la sfârșitul listei durează O(1).
- Inserarea la o poziție durează O(N).
- Ștergerea de la o poziție durează O(N).
- Obținerea primului și a ultimului element durează O(1).
- Obținerea elementului de la poziția N durează O(N).
Operațiile care durează O(N) au nevoie de atât timp deoarece trebuie să parcurgi lista cel puțin N noduri pentru a le executa cu succes. Pe de altă parte, operațiile care durează O(1) nu necesită nicio parcurgere, deoarece lista ține pointeri către capul (primul nod) și coada (ultimul nod).
Implementarea în Kotlin
Dacă dorești, poți opri lectura aici și să începi să implementezi o listă înlănțuită generică în limbajul de programare preferat. Pentru mine a fost o experiență de învățare plăcută și sper că va fi la fel și pentru tine.
Implementarea în Kotlin a listei înlănțuite se află în repo-ul de GitHub: Implementarea | Testele.
Să analizăm câteva:
Adăugarea unui element la sfârșitul listei
Append adaugă valoarea unui element la sfârșitul listei. Deoarece metoda poate accesa capul și coada listei, implementarea este destul de simplă.
Dacă lista conține cel puțin un element, folosești coada pentru a adăuga elementul, apoi actualizezi coada. Dacă lista este goală, adaugi noul nod la cap și la coadă.
fun append(value: T) { val newNode = Node(value, null) if (head == null) { head = newNode tail = newNode } else { tail!!.next = newNode tail = newNode } size += 1 }Obținerea valorii unui element din listă
Pentru a obține un element din listă de la poziția N, trebuie să parcurgi lista până când ajungi la poziție.
O posibilă optimizare aici este dacă parcurgerea ar trebui să înceapă de la capul sau de la coada listei.
fun get(position: Int): T? { var currentPosition = 0 var currentNode = head while (currentPosition <= position && currentNode != null) { if (currentPosition == position) { return currentNode.value } currentNode = currentNode.next currentPosition += 1 } return null }Modelul iterator
Pentru a parcurge lista într-un mod prietenos cu Kotlin, cu linkedList.forEach {}, trebuie implementat modelul iterator.
Deoarece iterabilul este Node<T>, lista trebuie să implementeze interfața Iterable<Node<T>>, apoi să implementeze
funcția iterator:
override fun iterator(): Iterator<Node<T>> { return NodeIterator(this) }NodeIterator este o clasă internă care implementează interfața Iterator<Node<T>> și oferă
funcționalitatea de iterare.
class NodeIterator<T>(linkedList: LinkedList<T>) : Iterator<Node<T>> { private var currentNode: Node<T>? = linkedList.head override fun hasNext(): Boolean { return currentNode != null } override fun next(): Node<T> { val node = currentNode!! currentNode = currentNode?.next return node } }listOf - un constructor elegant
Construiește o listă înlănțuită dintr-un număr variabil de argumente.
Metoda listOf este implementată cu ajutorul unei metode de extensie:
fun <T> LinkedList.Companion.listOf(vararg items: T): LinkedList<T> { val linkedList = LinkedList<T>() items.forEach { linkedList.append(it) } return linkedList}Oferă utilizatorului API-ului Linked List o modalitate elegantă de a o instanția: LinkedList.listOf(1, 2).
toArray - transformă lista înlănțuită într-un tablou
toArray este dificil de implementat ca metodă de instanță.
Deoarece tipurile generice sunt șterse la execuție (type erasure), metoda nu știe ce tip este T.
Făcând din ea o metodă de extensie generică și definind un tip reificat nou E, tipul parametrului metodei poate fi
omis la apel. Compilatorul îl poate deduce automat.
De exemplu, apelând toArray() pe un LinkedList<String>, parametrul de tip E va fi linkedList.toArray<String>().
inline fun <reified E> LinkedList<E>.toArray(): Array<E?> { val newArray = arrayOfNulls<E>(this.size()) this.forEachIndexed { i, node -> newArray[i] = node.value } return newArray}
