2/10

Structuri de Date Fundamentale — Liste, Stive, Cozi

Lecția 2 ⏱ 90 min

Structuri de Date Fundamentale¶

Array vs Linked List: Compromisul Fundamental¶

Înainte de a construi structuri complexe, trebuie să înțelegem diferența fundamentală dintre cele două moduri de a stoca o secvență de elemente.

Array-ul stochează elementele contiguu în memorie. Accesul la orice element se face printr-un calcul de adresă:

$$\text{adresa}[i] = \text{bază} + i \times \text{sizeof(element)}$$

Lista înlănțuită stochează fiecare element într-un nod care conține date + un pointer către nodul următor. Nodurile pot fi oriunde în memorie.

Operație	Array	Linked List
Acces pe index	$O(1)$	$O(n)$
Inserare la început	$O(n)$	$O(1)$
Inserare la final	$O(1)$ amortizat	$O(1)$ cu pointer la coadă
Inserare la mijloc	$O(n)$	$O(1)$ dacă ai referința
Căutare	$O(n)$ ($O(\log n)$ sortat)	$O(n)$
Memorie	Compactă, cache-friendly	Overhead pointeri, cache-unfriendly

Insight practic: În ciuda avantajelor teoretice ale listelor, array-urile sunt aproape mereu mai rapide în practică datorită cache locality — procesorul încarcă blocuri de memorie contiguă, nu elemente izolate.

Lista Simplu Înlănțuită¶

Fiecare nod conține o valoare și un pointer next către nodul următor. Ultimul nod are next = None.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def prepend(self, data):
        """Inserare la început — O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, data):
        """Inserare la final — O(n), dar O(1) dacă păstrăm tail"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1

    def delete(self, data):
        """Ștergerea primei apariții — O(n)"""
        if not self.head:
            return False

        # Caz special: ștergem head-ul
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return True

        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False

    def find(self, data):
        """Căutare — O(n)"""
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def __repr__(self):
        return " → ".join(str(x) for x in self) + " → None"

Tehnica Two Pointers pe liste¶

Multe probleme clasice cu liste se rezolvă cu doi pointeri care avansează cu viteze diferite.

Detectarea ciclurilor (Floyd's Tortoise and Hare):

def has_cycle(head):
    """
    Slow avansează câte 1 nod, fast câte 2.
    Dacă există un ciclu, se vor întâlni.
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Găsirea mijlocului listei:

def find_middle(head):
    """Când fast ajunge la final, slow e la mijloc"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Inversarea listei — un exercițiu fundamental:

def reverse_list(head):
    """
    Inversare in-place — O(n) timp, O(1) spațiu.
    La fiecare pas, schimbăm direcția pointer-ului next.
    """
    prev = None
    current = head
    while current:
        next_node = current.next   # salvăm referința
        current.next = prev        # inversăm pointer-ul
        prev = current             # avansăm prev
        current = next_node        # avansăm current
    return prev  # noul head

Lista Dublu Înlănțuită¶

Fiecare nod are pointer atât la next cât și la prev. Permite traversare în ambele direcții și ștergere în $O(1)$ dacă avem referința la nod.

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        # Sentinel nodes — simplifică dramatic cazurile speciale
        self.head = DNode(None)  # sentinel cap
        self.tail = DNode(None)  # sentinel coadă
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def _insert_between(self, data, pred, succ):
        """Inserează între două noduri — operația atomică"""
        new_node = DNode(data)
        new_node.prev = pred
        new_node.next = succ
        pred.next = new_node
        succ.prev = new_node
        self.size += 1
        return new_node

    def _remove_node(self, node):
        """Elimină un nod — O(1) dacă avem referința"""
        pred = node.prev
        succ = node.next
        pred.next = succ
        succ.prev = pred
        self.size -= 1
        return node.data

    def append(self, data):
        return self._insert_between(data, self.tail.prev, self.tail)

    def prepend(self, data):
        return self._insert_between(data, self.head, self.head.next)

    def pop_front(self):
        if self.size == 0:
            raise IndexError("Lista goală")
        return self._remove_node(self.head.next)

    def pop_back(self):
        if self.size == 0:
            raise IndexError("Lista goală")
        return self._remove_node(self.tail.prev)

De ce sentinel nodes? Fără ei, fiecare operație trebuie să verifice: „e head?", „e tail?", „e lista goală?". Sentinel-urile elimină toate aceste cazuri speciale — orice nod real are mereu un prev și un next valid.

Stiva (Stack)¶

Principiu LIFO (Last In, First Out) — ultimul element adăugat e primul scos. Gândește-te la o stivă de farfurii: pui deasupra, iei de deasupra.

Operații¶

Operație	Descriere	Complexitate
`push(x)`	Adaugă `x` pe vârful stivei	$O(1)$
`pop()`	Scoate și returnează vârful	$O(1)$
`peek()` / `top()`	Returnează vârful fără a-l scoate	$O(1)$
`is_empty()`	Verifică dacă stiva e goală	$O(1)$

class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

Aplicație 1: Validarea Parantezelor¶

O problemă clasică de interviu. Folosim o stivă pentru a verifica că fiecare paranteză deschisă are o paranteză închisă corespunzătoare, în ordinea corectă.

def is_balanced(expression):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for ch in expression:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()

    return len(stack) == 0

print(is_balanced("{[()]}"))   # True
print(is_balanced("{[(])}"))   # False — ] ar trebui să închidă [
print(is_balanced("((())"))    # False — ( fără pereche

Aplicație 2: Evaluarea Expresiilor Postfix¶

În notația postfix (poloneză inversă), operatorii vin după operanzi: 3 4 + 5 * înseamnă $(3 + 4) \times 5 = 35$.

def eval_postfix(expression):
    """
    Evaluează o expresie în notație postfix.
    Algoritmul: cifrele se pun pe stivă, operatorii scot doi operanzi,
    calculează, și pun rezultatul înapoi.
    """
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
    }

    for token in expression.split():
        if token in ops:
            b = stack.pop()  # atenție la ordine!
            a = stack.pop()
            stack.push(ops[token](a, b))
        else:
            stack.append(float(token))

    return stack[-1]

print(eval_postfix("3 4 + 5 *"))    # 35.0
print(eval_postfix("5 1 2 + 4 * + 3 -"))  # 14.0

Aplicație 3: Monotonic Stack¶

Un pattern avansat dar extrem de util: găsirea next greater element pentru fiecare element din array.

def next_greater_elements(arr):
    """
    Pentru fiecare element, găsește primul element mai mare la dreapta.
    Complexitate: O(n) — fiecare element intră/iese din stivă cel mult o dată.
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # stocăm indecși

    for i in range(n):
        # Scoatem elementele mai mici decât arr[i]
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

print(next_greater_elements([4, 5, 2, 10, 8]))
# [5, 10, 10, -1, -1]

Coada (Queue)¶

Principiu FIFO (First In, First Out) — primul element adăugat e primul scos. Ca la coadă la magazin.

Operații¶

Operație	Descriere	Complexitate
`enqueue(x)`	Adaugă la final	$O(1)$
`dequeue()`	Scoate de la început	$O(1)$
`front()`	Returnează primul element	$O(1)$

Implementare cu array circular¶

O implementare naivă cu array ar face dequeue în $O(n)$ (trebuie mutat tot array-ul). Soluția: buffer circular — folosim doi indecși care se „înfășoară":

class CircularQueue:
    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._front = 0
        self._size = 0
        self._capacity = capacity

    def enqueue(self, item):
        if self._size == self._capacity:
            self._resize()
        idx = (self._front + self._size) % self._capacity
        self._data[idx] = item
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("Queue is empty")
        item = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return item

    def front(self):
        if self._size == 0:
            raise IndexError("Queue is empty")
        return self._data[self._front]

    def _resize(self):
        new_data = [None] * (self._capacity * 2)
        for i in range(self._size):
            new_data[i] = self._data[(self._front + i) % self._capacity]
        self._data = new_data
        self._front = 0
        self._capacity *= 2

Deque (Double-Ended Queue)¶

O coadă care suportă inserare/extragere la ambele capete în $O(1)$. Python oferă collections.deque:

from collections import deque

dq = deque()
dq.append(1)       # adaugă la dreapta
dq.appendleft(2)   # adaugă la stânga
dq.pop()            # scoate din dreapta → 1
dq.popleft()        # scoate din stânga → 2

Aplicație: Sliding Window Maximum¶

Dați un array și o fereastră de dimensiune $k$, găsiți maximul din fiecare poziție a ferestrei:

def max_sliding_window(nums, k):
    """
    Folosim un deque monoton descrescător (stocăm indecși).
    Complexitate: O(n) — fiecare element intră/iese din deque o singură dată.
    """
    dq = deque()  # indecși, cu valori descrescătoare
    result = []

    for i in range(len(nums)):
        # Scoatem indecși care au ieșit din fereastră
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Scoatem din spate elementele mai mici decât nums[i]
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Adăugăm la rezultat după ce fereastra e completă
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Exerciții¶

Implementați o stivă folosind două cozi. Ce complexitate au push și pop?
Implementați o coadă folosind două stive (amortizat $O(1)$ per operație)
Min Stack: implementați o stivă care suportă get_min() în $O(1)$
Dat un string cu paranteze ( și ), găsiți lungimea celui mai lung substring de paranteze echilibrate. Exemplu: "(()())" → 6, ")()())" → 4

← Anterior Complexitate Computațională și Notația Asimptotică Următor → Algoritmi de Sortare

Pe această pagină