Jika Queue diimplementasikan dengan Linked List, tetapi linked list hanya memiliki referensi ke head, berapa lama waktu berjalannya enqueue dan berapa lama waktu berjalannya dequeue?

0
User 12 Mei 2021, 18:30

2 jawaban

Jawaban Terbaik

Mari kita mulai dengan kutipan dari artikel Wikipedia tentang Antrian:

Ada beberapa implementasi antrian FIFO yang efisien. Implementasi yang efisien adalah implementasi yang dapat melakukan operasi—en-queuing dan de-queuing—dalam waktu O(1).

  • Daftar tertaut

    • [...]
    • Daftar tertaut tunggal biasa hanya memiliki penyisipan dan penghapusan yang efisien di salah satu ujungnya. [...]

Ini benar-benar esensi. Karena operasi enqueue dan dequeue mempengaruhi daftar di ujung yang berlawanan dari daftar, dan kita hanya memiliki referensi dari salah satu dari dua ujung itu, kita harus "berjalan" ke ujung yang lain untuk dapat melakukan operasi lain di sana.

Kita dapat memilih ujung mana dari daftar tertaut yang akan berfungsi sebagai ujung di mana item di-enqueued (ditambahkan), sedangkan ujung lainnya adalah di mana item-item didequeued (diekstraksi). head dari daftar tertaut dapat berupa -- ini adalah pilihan desain.

Mari kita asumsikan bahwa enqueue akan menambahkan entri di akhir daftar tertaut (setelah ekor daftar saat ini), dan dequeue akan kembali entri kepala, dan hapus simpul itu dari daftar. Maka kodenya akan seperti ini -- saya menggunakan Python sebagai contoh:

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

class Queue:
    def __init__(self):
        self.head = None

    def enqueue(self, value):
        if self.head is None:
            self.head = Node(value)
        else:
            node = self.head
            while node.next is not None:
                node = node.next
            node.next = Node(value)
    
    def dequeue(self):
        if self.head is None:
            raise ValueError("Queue is empty")
        else:
            value = self.head.value
            self.head = self.head.next
            return value 

Jadi untuk enqueue, kita perlu menelusuri daftar, mulai dari simpul head, menemukan di mana ekor daftar. Kemudian kami membuat simpul untuk nilai yang diberikan dan menautkannya setelah simpul ekor itu, membuat daftar satu entri lebih panjang. Karena kita perlu menelusuri seluruh daftar sebelum kita dapat melakukan penjumlahan, ini memiliki kompleksitas waktu O(n).

Untuk dequeue, kita segera memiliki simpul yang nilainya perlu kita peroleh: itu adalah simpul head. Jadi tidak perlu melintasi daftar di sini. Kita hanya harus mengubah referensi head, sehingga merujuk ke node berikutnya dalam daftar, menghapus node pertama darinya. Operasi ini memiliki kompleksitas waktu O(1).

Sekarang, kita juga dapat mengambil keputusan desain alternatif di mana daftar tertaut akan tumbuh ke arah lain, dan enqueue akan menambahkan simpul baru sebelum simpul head saat ini. Metode dequeue kemudian harus mendapatkan nilai di simpul ekor dan menghapus simpul ekor itu dari daftar. Seperti yang Anda lihat, sekarang operasi enqueue memiliki kompleksitas waktu O(1), sedangkan dequeue memiliki kompleksitas waktu O(n).

Jadi bagaimanapun, akan ada salah satu dari dua yang memiliki kompleksitas waktu O(n), sedangkan yang lain memiliki kompleksitas waktu O(1).

0
trincot 12 Mei 2021, 19:05

Sebenarnya dimungkinkan untuk membuat antrian yang didukung oleh daftar tertaut yang hanya menyimpan pointer ke kepala daftar, tetapi di mana enqueue dan dequeue membutuhkan waktu O(1). Idenya adalah menggunakan daftar tertaut ganda yang ditautkan dalam sebuah siklus, sehingga elemen pertama dari daftar menunjuk mundur ke elemen terakhir dan elemen terakhir dari daftar menunjuk ke depan ke elemen pertama. Sebagai contoh:

head
 |    +---+     +---+     +---+     +---+
 +--> | 1 | <-> | 2 | <-> | 3 | <-> | 4 |
      +---+     +---+     +---+     +---+
        ^                             ^
        |                             |
        +-----------------------------+     

Untuk melakukan dequeue dalam waktu O(1), kita cukup menghapus dan mengembalikan sel daftar tertaut pertama. Saat melakukannya, kami memasang kembali sel sebelum dan tepat setelahnya untuk menunjuk satu sama lain, seperti ini:

head -------------+
                  |
                  v
                +---+     +---+     +---+
                | 2 | <-> | 3 | <-> | 4 |
                +---+     +---+     +---+
                  ^                   ^
                  |                   |
                  +-------------------+    

Untuk melakukan enqueue dalam waktu O(1), masukkan nilai baru yang ditempatkan di antara elemen pertama dan elemen terakhir, seperti ini:

head -------------+
                  |
                  v
                +---+     +---+     +---+
                | 2 | <-> | 3 | <-> | 4 |
                +---+     +---+     +---+
                  ^                   ^
                  |       +---+       |
                  +-----> | 5 | <-----+   
                          +---+

Saya akan menyerahkan detail juggling pointer yang sebenarnya kepada Anda untuk disortir, tetapi mereka cukup mudah, bisa dibilang lebih mudah daripada seperti apa antrian daftar tertaut biasa karena ada lebih sedikit kondisi batas untuk diperiksa.

0
templatetypedef 12 Mei 2021, 23:24