Bog'langan ro'yxatlar

class Tugun:
    """Bog'langan ro'yxatning bitta bo'g'ini."""

    def __init__(self, qiymat):
        self.qiymat = qiymat
        self.keyingi = None

    def __repr__(self):
        return f"Tugun({self.qiymat})"


# Qo'lda uch tugunni bog'laymiz
birinchi = Tugun(85)
ikkinchi = Tugun(92)
uchinchi = Tugun(78)

birinchi.keyingi = ikkinchi
ikkinchi.keyingi = uchinchi

# Boshidan oxirigacha yuramiz
joriy = birinchi
while joriy is not None:
    print(joriy.qiymat, end=" -> ")
    joriy = joriy.keyingi
print("None")

class BoglanganRoyxat:
    """Bir tomonlama bog'langan ro'yxat."""

    def __init__(self):
        self.bosh = None
        self.uzunlik = 0

    def boshiga_qosh(self, qiymat):
        """Boshiga element qo'shadi. O(1)."""
        yangi = Tugun(qiymat)
        yangi.keyingi = self.bosh
        self.bosh = yangi
        self.uzunlik += 1

    def oxiriga_qosh(self, qiymat):
        """Oxiriga element qo'shadi. O(n)."""
        yangi = Tugun(qiymat)
        self.uzunlik += 1

        if self.bosh is None:
            self.bosh = yangi
            return

        joriy = self.bosh
        while joriy.keyingi is not None:
            joriy = joriy.keyingi
        joriy.keyingi = yangi

    def ochir(self, qiymat):
        """Birinchi uchragan qiymatni o'chiradi. O(n)."""
        if self.bosh is None:
            return False

        if self.bosh.qiymat == qiymat:
            self.bosh = self.bosh.keyingi
            self.uzunlik -= 1
            return True

        joriy = self.bosh
        while joriy.keyingi is not None:
            if joriy.keyingi.qiymat == qiymat:
                joriy.keyingi = joriy.keyingi.keyingi     # o'tkazib yuboramiz
                self.uzunlik -= 1
                return True
            joriy = joriy.keyingi

        return False

    def qidir(self, qiymat):
        """Qiymat bor-yo'qligini tekshiradi. O(n)."""
        joriy = self.bosh
        while joriy is not None:
            if joriy.qiymat == qiymat:
                return True
            joriy = joriy.keyingi
        return False

    def teskari_ogir(self):
        """Ro'yxatni teskari o'giradi. O(n) vaqt, O(1) xotira."""
        oldingi = None
        joriy = self.bosh

        while joriy is not None:
            keyingi = joriy.keyingi     # keyingisini eslab qolamiz
            joriy.keyingi = oldingi     # strelkani teskari buramiz
            oldingi = joriy             # bir qadam oldinga
            joriy = keyingi

        self.bosh = oldingi

    def __len__(self):
        return self.uzunlik

    def __iter__(self):
        joriy = self.bosh
        while joriy is not None:
            yield joriy.qiymat
            joriy = joriy.keyingi

    def __str__(self):
        return " -> ".join(str(q) for q in self) + " -> None"

royxat = BoglanganRoyxat()

royxat.oxiriga_qosh(85)
royxat.oxiriga_qosh(92)
royxat.oxiriga_qosh(78)
royxat.boshiga_qosh(100)

print(royxat)
print(f"Uzunligi: {len(royxat)}")
print(f"92 bormi: {royxat.qidir(92)}")

royxat.ochir(92)
print(f"O'chirgandan keyin: {royxat}")

royxat.teskari_ogir()
print(f"Teskari o'girilgan:  {royxat}")

class IkkiTomonlamaTugun:
    def __init__(self, qiymat):
        self.qiymat = qiymat
        self.keyingi = None
        self.oldingi = None


class IkkiTomonlamaRoyxat:
    """Ikki tomonlama bog'langan ro'yxat - oxiriga qo'shish ham O(1)."""

    def __init__(self):
        self.bosh = None
        self.oxir = None
        self.uzunlik = 0

    def oxiriga_qosh(self, qiymat):
        """O(1) - chunki oxirni bilamiz."""
        yangi = IkkiTomonlamaTugun(qiymat)
        self.uzunlik += 1

        if self.oxir is None:
            self.bosh = self.oxir = yangi
            return

        yangi.oldingi = self.oxir
        self.oxir.keyingi = yangi
        self.oxir = yangi

    def oxiridan_ol(self):
        """Oxirgi elementni olib tashlaydi. O(1)."""
        if self.oxir is None:
            return None

        qiymat = self.oxir.qiymat
        self.oxir = self.oxir.oldingi
        if self.oxir is None:
            self.bosh = None
        else:
            self.oxir.keyingi = None
        self.uzunlik -= 1
        return qiymat

    def teskari_yur(self):
        """Oxiridan boshiga qarab yuradi."""
        joriy = self.oxir
        while joriy is not None:
            yield joriy.qiymat
            joriy = joriy.oldingi


royxat = IkkiTomonlamaRoyxat()
for baho in [85, 92, 78, 95]:
    royxat.oxiriga_qosh(baho)

print("Teskari tartibda:", list(royxat.teskari_yur()))
print("Oxiridan olindi:", royxat.oxiridan_ol())
print("Qolgan uzunlik:", royxat.uzunlik)

def sikl_bormi(bosh):
    """Floyd algoritmi: sekin va tez ko'rsatkich. O(n) vaqt, O(1) xotira."""
    sekin = bosh
    tez = bosh

    while tez is not None and tez.keyingi is not None:
        sekin = sekin.keyingi              # 1 qadam
        tez = tez.keyingi.keyingi          # 2 qadam

        if sekin is tez:                   # uchrashdilar - demak sikl bor
            return True

    return False


a, b, c = Tugun(1), Tugun(2), Tugun(3)
a.keyingi, b.keyingi = b, c
print("Sikl bormi:", sikl_bormi(a))

c.keyingi = a                              # siklni yasaymiz
print("Sikl bormi:", sikl_bormi(a))