>

>
1x
go to beginning previous frame pause play next frame go to end

Linked List is a data structure consisting of a group of vertices (nodes) which together represent a sequence. Under the simplest form, each vertex is composed of a data and a reference (link) to the next vertex in the sequence. Try clicking Search(77) for a sample animation on searching a value in a (Singly) Linked List.


Linked List and its variations are used as underlying data structure to implement List, Stack, Queue, and Deque ADTs (read this Wikipedia article about ADT if you are not familiar with that term).


In this visualization, we discuss (Singly) Linked List (LL) — with a single next pointer — and its two variants: Stack and Queue, and also Doubly Linked List (DLL) — with both next and previous pointers — and its variant: Deque.


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

Kami memutuskan untuk menggabungkan lima mode-mode yang berhubungan dengan Senarai Berantai (LL, Tumpukan, Antrean, DLL, Deque) didalam sebuah halaman visualisasi saja. Untuk memfasilitasi keberagaman, kami mengacak mode terpilih saat anda mengakses URL langsung ini: https://visualgo.net/en/list.


Tetapi, anda bisa menggunakan shortcut URL dibawah ini untuk mengakses mode tersendiri secara langsung:

  1. https://visualgo.net/en/ll,
  2. https://visualgo.net/en/stack,
  3. https://visualgo.net/en/queue,
  4. https://visualgo.net/en/dll,
  5. https://visualgo.net/en/deque.

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

Struktur data Senarai Berantai biasanya diajarkan dalam mata kuliah Ilmu Komputer (Computer Science, CS) karena berbagai alasan-alasan:

  1. Struktur data ini sederhana dan linear,
  2. Struktur data ini memiliki banyak potensi aplikasi-aplikasi sebagai ADT list misalkan daftar murid, daftar even, daftar perjanjian, dsb (meskipun ada beberapa struktur-struktur data yang lebih tingkat lanjut yang bisa melakukan aplikasi-aplikasi yang sama (dan lebih) dengan lebih baik) atau sebagai ADT tumpukan/antrean/deque,
  3. Struktur data memiliki beberapa kasus corner/spesial untuk mengilustrasikan kebutuhan akan implementasi yang baik dari sebuah struktur data,
  4. Struktur data ini memiliki berbagai opsi-opsi kustomisasi dan sehingga struktur data Senarai Berantai ini biasanya diajarkan menggunakan cara Object-Oriented Programming (OOP).

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

List is a sequence of items/data where positional order matter {a0, a1, ..., aN-2, aN-1}.
Common List ADT operations are:

  1. get(i) — maybe a trivial operation, return ai (0-based indexing),
  2. search(v) — decide if item/data v exists (and report its position/index)
    or not exist (and usually report a non existing index -1) in the list,
  3. insert(i, v) — insert item/data v specifically at position/index i in the list, potentially shifting the items from previous positions: [i..N-1] by one position to their right to make a space,
  4. remove(i) — remove item that is specifically at position/index i in the list, potentially shifting the items from previous positions: [i+1..N-1] by one position to their left to close the gap.

Discussion 1: What if we want to remove item with specific value v in the list?

Discussion 2: Can a List ADT contains duplicate items, i.e., ai = aj where i ≠ j?


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Larik (Padat) adalah sebuah kandidat baik untuk mengimplementasikan ADT Daftar karena itu adalah konstruksi sederhana untuk mengurus sebuah koleksi dari item-item.


Ketika kita membahas larik padat, kita merujuk kepada larik yang tidak mempunyai celah, yaitu jika ada N item-item dalam larik (yang memiliki ukuran M, dimana M ≥ N), maka hanya indeks [0..N-1] yang terisi dan indeks-indeks lain [N..M-1] harus tetap kosong.


Compact Array Illustration
🕑

Let the compact array name be A with index [0..N-1] occupied with the items of the list.


get(i), just return A[i].
This simple operation will be unnecessarily complicated if the array is not compact.


search(v), we check each index i ∈ [0..N-1] one by one to see if A[i] == v.
This is because v (if it exists) can be anywhere in index [0..N-1].
Since this visualization only accept distinct items, v can only be found at most once.
In a general List ADT, we may want to have search(v) returns a list of indices.


insert(i, v), we shift items ∈ [i..N-1] to [i+1..N] (from backwards) and set A[i] = v.
This is so that v is inserted correctly at index i and maintain compactness.


remove(i), we shift items ∈ [i+1..N-1] to [i..N-2], overwriting the old A[i].
This is to maintain compactness.

🕑

get(i) sangat cepat: Hanya satu akses, O(1).
Sebuah modul CS lainnya: 'Organisasi Komputer' mendiskusikan detil-detil tentang performa O(1) dari operasi indeks larik ini.


cari(v)
Pada kasus terbaik, v ditemukan pada posisi pertama, O(1).
Pada kasus terjelek, v tidak ditemukan di daftar dan kita membutuhkan pemindaian dalam O(N) untuk menentukan hal itu.


insert(i, v)
Pada kasus terbaik, pemasukkan pada i = N, tidak ada penggeseran elemen, O(1).
Pada kasus terjelek, pemasukkan pada i = 0, kita harus menggeser semua N element-elemen, O(N).


remove(i)
Pada kasus terbaik, penghapusan pada i = N-1, tidak ada penggesearan elemen, O(1).
Pada kasus terjelek, penghapusan padai = 0, kita harus menggeser semua N element-elemen, O(N).

🕑

Ukuran dari larik padat M tidak tak-terbatas, tetapi terbatas. Ini menimbulkan masalah karena ukuran maksimum mungkin tidak diketahui dimuka pada banyak aplikasi-aplikasi.


Jika M terlalu besar, maka ruang-ruang yang tidak terpakai akan terbuang.
Jika M terlalu kecil, maka kita akan kehabisan ruang dengan mudah.

🕑

Solution: Make M a variable. So when the array is full, we create a larger array (usually two times larger) and move the elements from the old array to the new array. Thus, there is no more limits on size other than the (usually large) physical computer memory size.


C++ STL std::vector, Python list, Java Vector, or Java ArrayList all implement this variable-size array. Note that Python list and Java ArrayList are not Linked Lists, but are actually variable-size arrays.


However, the classic array-based issues of space wastage and copying/shifting items overhead are still problematic.

🕑

Untuk koleksi-koleksi dengan ukuran-tetap dengan pengetahuan tentang limit maksimum jumlah item-item yang akan pernah dibutuhkan, yaitu ukuran maksimum dari M, larik adalah struktur data yang sudah lumayan bagus untuk implementasi ADT Daftar.


Untuk koleksi-koleksi dengan ukuran-variabel dengan ukuran M yang tidak diketahui dan dimana operasi-operasi dinamis seperti pemasukkan/penghapusan cukup sering digunakan, sebuah larik sederhana sebenarnya adalah pilihan struktur data yang jelek.


Untuk aplikasi-aplikasi seperti itu, ada struktur-struktur data lain yang lebih baik. Mari lanjutkan baca...

🕑

We now introduce the Linked List data structure. It uses pointers/references to allow items/data to be non-contiguous in memory (that is the main difference with a simple array). The items are ordered from index 0 to index N-1 by associating item i with its neighbour item i+1 through a pointer.


Linked List Illustration
🕑

Pada bentuk paling dasar, sebuah simpul (node) tunggal dalam Senarai Berantai memiliki struktur kasar seperti ini:

struct Vertex { // kita bisa memakai C struct atau C++/Python/Java class
int item; // data ada disini, sebuah bilangan bulat di contoh ini
Vertex* next; // petunjuk ini menunjuk ke simpul berikut
};

Menggunakan contoh default Senarai Berantai [22 (kepala)->2->77->6->43->76->89 (ekor)]  sebagai ilustrasi, kita punya:
a0 dengan item = 22 dan next = a1,
a1 dengan item = 2 dan next = a2,
...
a6 dengan item = 89 dan next = null.


Diskusi: Yang mana yang lebih baik untuk sebuah implementasi C++ dari Senarai Berantai? struct atau class? Bagaimana dengan implementasi Python atau Java?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

We also have a few additional data that we remember in this Linked List data structure. We use the default example Linked List [22 (head)->2->77->6->43->76->89 (tail)] for illustration.

  1. The head pointer points to a0 — it is 22, nothing points to the head item,
  2. The current number of elements N in the Linked List — N = 7 elements.
  3. The tail pointer points to aN-1 — it is a6 = 89, nothing is after the tail item.

That's it, we only add three more extra variables in data structure.

🕑

Note that there are various subtle differences found in many Computer Science textbooks on how to implement a (Singly) Linked List e.g., use tail pointer or not, circular or not, use dummy head item or not, allow duplicate items or not — see this slide.


Our version in this visualization (with tail pointer, not circular, without dummy head, disallow duplicate) may not be 100% the same compared to what you learn in your class but the basic ideas should remain the same.


In this visualization, each vertex has Integer item, but this can easily be changed to any other data type as needed.

🕑

Karena kita hanya menyimpan penunjuk-penunjuk kepala dan ekor, subrutin penjelajahan daftar dibutuhkan untuk mencapai posisi-posisi diluar kepala (indeks 0) dan ekor (indeks N-1).


Karena sub-rutin ini sering sekali dipakai, kita akan mengabstraksikannya sebagai sebuah fungsi. Kode dibawah ditulis dalam bahasa C++.

Vertex* Get(int i) { // kembalikan sebuah simpul
Vertex* ptr = head; // kita harus mulai dari kepala
for (int k = 0; k < i; k++) // maju ke depan i kali
ptr = ptr->next; // penunjuk menunjuk ke indeks lebih tinggi
return ptr;
}

Sub-rutin ini berjalan dalam O(N) karena i bisa sebesar indeks N-2.
Bandingkan ini dengan larik dimana kita bisa mengakses indeks i dalam waktu O(1).

🕑

Karena kita hanya memiliki referensi langsung ke item kepala yang pertama dan item ekor yang terakhir, ditambah lagi semua penunjuk-penunjuk menunjuk ke kanan (posisi/indeks yang lebih tinggi), kita hanya bisa mengakses yang lainnya dengan memulai dari item kepala dan menelusuri penunjuk-penunjuk berikutnya. Pada [22 (kepala)->2->77->6->43->76->89 (ekor)] default, kita punya::


Search(77) — ditemukan pada contoh diatas pada posisi/indeks 2 (indeks berbasis-0).


Search(7) — tidak ditemukan pada contoh diatas, dan ini hanya dapat diketahui setelah semua N item diperiksa, jadi Cari(v) memiliki kompleksitas waktu terjelek sebesar O(N).

🕑

There are more cases than array version due to the nature of Linked List.


Most CS students who learn Linked List for the first time usually are not aware of all cases until they figure it out themselves when their Linked List code fail.


In this e-Lecture, we directly elaborate all cases.


For insert(i, v), there are four (legal) possibilities, i.e., item v is added to:

  1. The head (before the current first item) of the linked list, i = 0,
  2. An empty linked list (which fortunately similar to the previous case),
  3. The position beyond the last (the current tail) item of the linked list, i = N,
  4. The other positions of the linked list, i = [1..N-1].
🕑

Kode (C++) untuk pemasukkan pada kepala mudah dan efisien, dalam O(1):

Vertex* vtx = new Vertex(); // buat simpul baru vtx dari item v
vtx->item = v;
vtx->next = head; // hubungkan simpul baru ini ke simpul kepala (lama)
head = vtx; // simpul baru menjadi kepala yang baru

Coba InsertHead(50), yaitu masukkan(0, 50), pada contoh Senarai Berantai [22 (kepala)->2->77->6->43->76->89 (ekor)] .


Diskusi: Apa yang terjadi jika kita menggunakan implementasi larik untuk pemasukkan pada kepala dari daftar?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Struktur data kosong adalah sebuah kasus sudut/spesial yang umum yang sering menyebabkan crash yang tidak dikehendaki jika tidak diuji dengan baik. Adalah legal untuk memasukkan sebuah item baru ke daftar yang saat ini kosong, yaitu pada indeks i = 0. Untungnya, pseudo-code yang sama untuk pemasukkan pada kepala juga bisa dipakai untuk daftar yang kosong sehingga kita bisa langsung menggunakan kode yang sama seperti di slide ini (dengan satu perubahan minor, kita juga perlu mengeset ekor = kepala).


Coba InsertHead(50), yaitu masukkan(0, 50), tetapi pada Senarai Berantai kosong [].

🕑

Dengan sub-rutin penjelajahan Senarai Berantai Get(i), kita sekarang bisa mengimplementasikan pemasukkan di tengah Senarai Berantai sebagai berikut (dalam C++):

Vertex* pre = Get(i-1); // pergi ke simpul (i-1), O(N)
aft = pre.next // aft tidak bisa null, pikirkanlah
Vertex vtx = new Vertex(); // buat simpul baru
vtx->item = v;
vtx->next = aft; // hubungkan ini
pre->next = vtx; // dan ini

Coba Insert(3, 44) pada contoh Senarai Berantai [22 (kepala)->2->77->6->43->76->89 (ekor)] .


Juga coba Insert(6, 55) pada contoh Senarai Berantai yang sama. Ini adalah kasus sudut: Pemasukan pada posisi item ekor, menggeser ekor ke satu posisi ke kanan.


Operasi ini lambat, O(N), karena perlunya menjelajahi daftar (jika i dekat dengan N-1).

🕑

Jika kita juga mengingat petunjuk ekor seperti implementasi dalam kuliah maya ini (yang dianjurkan karena itu hanyalah satu tambahan variabel petunjuk), kita bisa melakukan pemasukan setelah item ekor (pada i = N) dengan efisien, dalam O(1):

Vertex* vtx = new Vertex(); // ini juga adalah kode C++
vtx->item = v; // buat simpul baru vtx dari item v
tail->next = vtx; // hubungkan saja, ekor adalah item ke i = (N-1)
tail = vtx; // sekarang mutakhirkan petunjuk ekor

Coba InsertTail(10), yaitu masukkan(7, 10), pada contoh Senarai Berantai [22 (kepala)->2->77->6->43->76->89 (ekor)] . Sebuah miskonsepsi umum adalah untuk mengatakan bahwa ini adalah pemasukkan pada ekor. Pemasukkan pada elemen ekor adalah masukkan(N-1, v). Pemasukan setelah ekor adalah masukkan(N, v).


Diskusi: Apa yang terjadi jika kita menggunakan implementasi larik untuk pemasukkan setelah ekor dari sebuah daftar?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Untuk hapus(i), ada tiga kemungkinan-kemungkinan (legal), yaitu indeks i adalah:

  1. Kepala (item yang sekarang pertama) dari senarai berantai, i = 0, ini mempengaruhi penunjuk kepala
  2. Ekor dari senarai berantai, i = N-1, ini mempengaruhi penunjuk ekor
  3. Posisi-posisi lain dari senarai berantai, i = [1..N-2].

Diskusi: Bandingkan slide ini dengan slide Kasus-Kasus Pemasukkan untuk menyadari perbedaan yang halus. Apakah menghapus sesuatu dari Senarai Berantai yang sudah kosong dapat dikatkan 'legal'?

🕑

This case is straightforward (written in C++):

if (head == NULL) return; // avoid crashing when SLL is empty
Vertex* tmp = head; // so we can delete it later
head = head->next; // book keeping, update the head pointer
delete tmp; // which is the old head

Try RemoveHead() repeatedly on the (shorter) example Linked List [22 (head)->2->77->6 (tail)]. It will continuously working correctly up until the Linked List contains one item where the head = the tail item. We prevent execution if the LL is already empty as it is an illegal case.


Discussion: What happen if we use array implementation for removal of head of the list?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Dengan sub-rutin penjelajahan Senarai Berantai Get(i) (yang telah dibahas sebelumnya), kita sekarang dapat mengimplementasikan penghapusan item ditengah-tengah sebuah Senarai Berantai sebagai berikut (dalam bahasa C++):

Vertex* pre = Get(i-1); // pergi ke simpul ke-(i-1), O(N)
Vertex* del = pre->next, aft = del->next;
pre->next = aft; // lewati del
delete del;

Coba Remove(5), elemen pada indeks N-2 (N = 7 pada contoh [22 (kepala)->2->77->6->43->76->89 (ekor)] ).
Ini adalah kasus O(N) terjelek pada contoh diatas.


Catat bahwa Hapus(N-1) adalah penghapusan pada ekor yang membutuhkan pemutakhiran dari petunjuk ekor, lihat kasus setelah ini.

🕑

We can implement the removal of the tail of the Linked List as follows, assuming that the Linked List has more than 1 item (in C++):

Vertex* pre = head;
tmp = head->next;
while (tmp->next != null) // while my neighbor is not the tail
pre = pre->next, tmp = tmp->next;
pre->next = null;
delete tmp; // tmp = (old) tail
tail = pre; // update tail pointer

Try RemoveTail() repeatedly on the (shorter) example Linked List [22 (head)->2->77->6 (tail)]. It will continuously working correctly up until the Linked List contains one item where the head = the tail item and we switch to removal at head case. We prevent execution if the LL is already empty as it is an illegal case.

🕑

Sesungguhnya, jika kita juga menyimpan ukuran dari Senarai Berantai N (bandingkan dengan slide ini), kita dapat menggunakan sub-rutin penjelajahan Senarai Berantai Get(i) untuk mengimplementasikan penghapusan dari ekor dari sebuah Senarai Berantai seperti ini (dalam bahasa C++):

Vertex* pre = Get(N-2); // pergi ke satu indeks dibelakang ekor, O(N)
pre->next = null;
delete tail;
tail = pre; // kita punya akses ke ekor yang lama

Sadari bahwa operasi ini lambat, O(N), hanya karena kita butuh untuk memutakhirkan petunjuk ekor dari item N-1 kebelakang sebesar satu unit ke item N-2 sehingga pemasukkan setelah ekor di masa mendatang tetap benar... Kelemahan ini akan nantinya diatasi dalam varian Senarai Berantai Ganda (Doubly Linked List).


Diskusi: Apa yang terjadi jika kita menggunakan implementasi larik untuk penghapusan dari ekor dari sebuah daftar?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

get(i) pelan: O(N).
Dalam Senarai Berantai, kita perlu untuk melakukan akses sekuensial dari elemen kepala.


cari(v)
Pada kasus terbaik, v ditemukan di posisi pertama, O(1).
Pada kasus terjelek, v tidak ditemukan dalam daftar dan kita membutuhkan pemindaian dalam O(N) untuk menentukan hal itu.


masukkan(i, v)
Pada kasus terbaik, pemasukkan pada i = 0 atau pada i = N, penunjuk-penunjuk kepala dan ekor membantu, O(1).
Pada kasus terjelek, pemasukkan pada i = N-1, kita harus mencari item N-2 tepat dibelakang ekor, O(N).


hapus(i)
Pada kasus terbaik, penghapusan pada i = 0, penunjuk kepala membantu, O(1).
Pada kasus terjelek, penghapusan pada i = N-1, karena kita butuh untuk memutakhirkan penunjuk ekor, O(N).

🕑

Aplikasi-aplikasi murni dari Senarai Berantai (Tunggal) secara mengejutkan ternyata jarang karena larik padat yang bisa diubah ukurannya (vector) bisa melakukan tugas dengan lebih baik, bandingkan versi Senarai Berantai dengan versi larik padat.


Tetapi, konsep dasar dari Senarai Berantai yang mengijinkan simpul-simpul tidak berdekatan di memori membuatnya menjadi struktur data yang bisa berubah-ukuran yang efisien untuk dua Tipe Data Abstrak berikutnya: Tumpukan dan Antrean.

🕑

Tumpukkan adalah sebuah struktur data abstrak di mana operasi utama pada koleksi adalah tambahan terhadap nilai-nilai kedalam koleksi, disebut sebagau push, hanya ke bagian atas tumpukan dan penghapusan nilai yang sudah ada, disebut sebagai pop, hanya dari bagian atas tumpukan.


Tumpukkan dikenal sebagai struktur data Last-In-First-Out (LIFO) / Masuk-Terakhir-Keluar-Pertama, misalkan tumpukan buku dibawah.

Stack Illustration
🕑

In most implementations and also in this visualization, Stack is basically a protected (Singly) Linked List where we can only peek at the head item, push a new item only to the head (insert at head), e.g., try InsertHead(6), and pop existing item only from the head (remove from head), e.g., try RemoveHead(). All operations are O(1).


In this visualization, we orientate the (Single) Linked List top down, with the head/tail item at the top/bottom, respectively. In the example, we have [2 (top/head)->7->5->3->1->9 (bottom/tail)]. Due to vertical screen size limit (in landscape mode), we only allow a Stack of at most 7 items in this visualization.


Discussion: Can we use vector, a resizeable array, to implement Stack ADT efficiently?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Tumpukan memiliki beberapa aplikasi-aplikasi buku teks yang popular, yaitu:

  1. Pencocokan Kurung,
  2. Perhitungan Postfix,
  3. Beberapa aplikasi-aplikasi lain yang menarik yang tidak ditunjukkan karena alasan pedagogis.
🕑

Ekspresi matematika bisa cukup berbelit-belit, seperti {[x+2]^(2+5)-2}*(y+5).


Masalah Pencocokan Tanda-Kurung adalah sebuah masalah pengecekan apabila semua tanda-tanda kurung yang diberikan dalam masukan dapat dicocokkan dengan benar, yaitu ( dengan ), [ dengan ] dan { dengan }, dan sebagainya.


Pencocokan Tanda-Kurung juga berguna untuk mengecek legalitas dari sebuah kode sumber.


Diskusi: Kita bisa pakai sifat LIFO dari Tumpukan untuk menyelesaikan masalah ini.
Pertanyaannya: Bagaimana?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Ekspresi Postfix adalah ekspresi matematika dalam format: operand1 operand2 operator yang adalah berbeda dengan apa yang paling nyaman untuk manusia, yaitu ekspresi Infix: operand1 operator operand2.


Contohnya, ekspresi 2 3 + 4 * adalah versi Postfix dari (2+3)*4.


Dalam ekspresi Postfix, kita tidak memerlukan tanda-tanda kurung.


Diskusi: Kita bisa pakai Tumpukan untuk menyelesaikan masalah ini secara efisien.
Pertanyaannya: Bagaimana?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Antrean adalah sebuah struktur data abstrak di mana item-item dalam koleksi dipertahankan urutannya dan operasi-operasi utama yang dapat dilakukan pada koleksi adalah menambahkan item-item ke posisi belakang (enqueue) dan menghapus item-item dari posisi depan (dequeue).


Antrean dikenal sebagai struktur data First-In-First-Out (FIFO) / Masuk-Pertama-Keluar-Pertama karena item pertama yang di-enqueue akan pada akhirnya menjadi item pertama yang di-dequeue, sama seperti antrean di kehidupan nyata (lihat dibawah).

Queue Illustration
🕑

Jika kita secara sederhana menggunakan implementasi larik padat untuk ADT Antrean ini dengan a0 sebagai depan dari antrean dan aN-1 sebagai belakang dari antrean, kita akan menjumpai isu performa yang mayor dengan operasi dequeue.


Ini karena pemasukkan pada posisi belakang dari larik padat itu cepat, O(1), tetapi penghapusan pada depan dari larik padat adalah lambat karena kita butuh untuk menggeser item-item, silahkan ulas slide ini.

🕑

Another possible array implementation is to avoid that shifting of items during dequeue operation by having two indices: front (the index of the queue front-most item, increased after a dequeue operation) and back (the index of the queue back-most item, also increased after an enqueue operation).


Suppose we use an array of size M = 8 items and the content of our queue is as follows: [(2,4,1,7),-,-,-,-] with front = 0 (underlined) and back = 3 (italic). The current active queue elements are highlighted with (green color).


If we call dequeue(), we have [-,(4,1,7),-,-,-,-], front = 0+1 = 1, and back = 3.


If we call enqueue(5), we have [-,(4,1,7,5),-,-,-], front = 1, and back = 3+1 = 4.

🕑

However, many dequeue and enqueue operations later, we may have [-,-,-,-,-,6,2,3], front = 5, and back = 7. By now, we cannot enqueue anything else albeit we have many empty spaces at the front of the array.


If we allow both front and back indices to "wrap back" to index 0 when they have reached index M-1, we effectively make the array "circular" and we can use the empty spaces.


For example, if we call enqueue(8) next, we have [8),-,-,-,-,(6,2,3], front = 5, and back = (7+1)%8 = 0.

🕑

Yet, this does not solve the main problem of fixed-size array implementation. A few more enqueue operations later, we may have [8,10,11,12,13),(6,2,3], front = 5, and back = 4. At this point (front = (back+1) % M)), we cannot enqueue anything else.


Do note that if we know that our queue size will never exceed the fixed array size M, then the circular array idea is actually already a good way to implement Queue ADT.


However, if we do not know the upper bound of queue size, we can enlarge (double) the size of the array, e.g., make M = 2*8 = 16 (two-times larger), but that will entail re-copying the items from index front to back in a slow (but rare) O(N) process to have [(6,2,3,8,10,11,12,13),-,-,-,-,-,-,-,-,], front = 0, and back = 7.


PS1: If you understand amortized analysis, this heavy O(N) cost when the circular array is full can actually be spread out so that each enqueue remains O(1) in amortized sense.


PS2: There is an alternative way to implement an efficient Queue using two Stacks. How?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

If we do not really know the the upper bound of queue size, then Singly Linked List (SLL) can be a good data structure to implement Queue ADT.


Recall that in a Queue, we only need the two extreme ends of the List, one for insertion (enqueue) only and one for removal (dequeue) only.


If we review this slide, we see that insertion after tail and removal from head in a Singly Linked List are fast, i.e., O(1). Thus, we designate the head/tail of the Singly Linked List as the front/back of the queue, respectively. Then, as the items in a Linked List are not stored contiguously in computer memory, our Linked List can grow and shrink as needed.


In our visualization, Queue is basically a protected Singly Linked List where we can only peek at the head item, enqueue a new item to one position after the current tail, e.g., try Enqueue(random-integer), and dequeue existing item from the head, e.g., try RemoveHead() (which is essentially a dequeue operation). All operations are O(1).

🕑

ADT Antrean biasanya digunakan untuk mensimulasikan antrean-antrean nyata.


Satu aplikasi sangat penting dari ADT Antrean adalah didalam algoritma penjelajahan graf Breadth-First Search.

🕑
Senarai Berantai ganda adalah sebuah struktur data terhubung yang terdiri dari simpul-simpul yang terhubung dalam sebuah barisan. Tiap simpul memiliki dua atribut, bernama links, yang merupakan referensi ke simpul sebelum dan sesudahnya dalam barisan tersebut.

Dalam visualisasi kita, dua buah pointer akan digunakan: head/front dan tail/back dan kita memperbolehkan senarai berantai ganda yang kosong dan memiliki kasus-kasus khusus. Semua operasi berjalan dalam O(1) kecuali cari/insert kth/remove kth, yang berjalan dalam O(N). Perlu diketahui bahwa operasi remove tail berjalan dalam O(1) dalam senarai berantai ganda.
🕑

The main problem of removal of the tail element in the Singly Linked List, even if we have direct access to the tail item via the tail pointer, is that we then have to update the tail pointer to point to one item just before the tail after such removal.


With Doubly Linked List ability to move backwards, we can find this item before the tail via tail->prev... Thus, we can implement removal of tail this way (in C++):

Vertex* tmp = tail; // remember tail item
tail = tail->prev; // the key step to achieve O(1) performance :O
tail->next = null; // remove this dangling reference
delete tmp; // remove the old tail

Now this operation is O(1). Try RemoveTail() on example DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)].

🕑

Karena kita memiliki satu penunjuk lagi prev untuk setiap simpul, nilai-nilai mereka perlu dimutakhirkan juga pada setiap pemasukkan dan penghapusan. Cobalah semua operasi-operasi berikut pada DLL contoh [22 (kepala)<->2<->77<->6<->43<->76<->89 (ekor)].


Coba InsertHead(50) — langkah tambahan: penunjuk prev 22 menunjuk ke kepala baru 50.


Coba InsertTail(10) — langkah tambahan: penunjuk prev 10 menunjuk ke ekor lama 89.


Coba Insert(3, 44) — langkah tambahan: penunjuk prev 6/44 masing-masing menunjuk ke 44/77.


Coba RemoveHead() — set penunjuk prev kepala baru 2 ke null.


Coba Remove(5) — set penunjuk prev 89 ke 43.

🕑
Antrean Dua Arah (Deque) adalah struktur data abstrak yang merupakan generalisasi dari antrean, di mana nilai dapat dimasukkan dan dikeluarkan dari depan (head) ataupun belakang (tail).

Dalam visualisasi kita, Deque direpresentasikan sebagai Senarai Berantai Ganda di mana kita hanya bisa mencari nilai head/tail (peek front/back), memasukkan nilai baru ke depan/belakang (push front/back), dan mengambil nilai dari depan / belakang (pop front/back). Semua operasi berjalan dalam O(1).
🕑

Deque dipakai dalam beberapa aplikasi-aplikasi advanced, seperti mencari jarak terpendek dalam graf berbobot 0/1 menggunakan BFS yang dimodifikasi, pada beberapa teknik sliding window, dan sebagainya.

🕑

Create operation is the same for all five modes.


However there are minor differences for the search/insert/remove operations among the five modes.


For Stack, you can only peek/restricted-search, push/restricted-insert, and pop/restricted-remove from the top/head.


For Queue, you can only peek/restricted-search from the front (or sometimes, the back), push/restricted-insert from the back, and pop/restricted-remove from the front.


For Deque, you can peek/restricted-search, enqueue/restricted-insert, dequeue/restricted-remove from both front/back, but not from the middle.


Single (Singly) and Doubly Linked List do not have such restrictions.

🕑

Kita telah mencapai akhir dari Kuliah Maya ini.


Tapi tetap lanjut membaca untuk melihat beberapa tantangan-tantangan ekstra.

🕑

The following are the more advanced insights about Linked List:

  1. What happen if we don't store the tail pointer too?
  2. What if we use dummy head?
  3. What if the last tail item points back to the head item?
  4. What need to be changed to allow duplicate items (a more general List ADT)?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

C++ STL:
forward_list (sebuah Senarai Berantai Tunggal)
stack
queue
list (sebuah Senarai Berantai Ganda)
deque (sebenarnya tidak menggunakan Senarai Berantai Ganda tetapi teknik lain, lihat cppreference)


Java API:

LinkedList (sudah Senarai Berantai Ganda)
Stack
Queue (sebenarnya interface, biasanya diimplementasikan dengan LinkedList class)
Deque (sebenarnya interface, biasanya diimplementasikan dengan LinkedList class)

🕑

Python:
list untuk Senarai Berantai/Tumpukan/Antrean
deque


OCaml:
List
Stack
Queue
Tidak ada dukungan built-in untuk Deque

🕑

Untuk beberapa pertanyaan-pertanyaan yang menarik lainnya tentang struktur data ini, silahkan latihan pada modul latihan Senarai Berantai.

🕑

Kami juga memiliki beberapa masalah-masalah pemrograman yang membutuhkan penggunaan dari struktur data Senarai Berantai, Tumpukan, Antrean, atau Deque:
UVa 11988 - Broken Keyboard (a.k.a. Beiju Text), Kattis - backspace, dan Kattis - integerlists.


Cobalah mereka untuk memantapkan dan meningkatkan pengertian anda tentang struktur data ini. Anda diijinkan untuk menggunakan C++ STL, perpustakan standar Python, atau Java API jika itu mempermudah implementasi anda.


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

Buat(A)

Masukkan

Hapus

>

Kosong

User Defined List

N =

Acak

Urutan Acak

i = 0 (Kepala), tentukan v =

i = N (Setelah Ekor), tentukan v =

tentukan i dalam [1..N-1] dan v =

Hapus Head

Hapus Tail

tentukan i dalam [1..N-2]

Tentang Tim Syarat Guna Kebijakan Privasi

Tentang

Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

id, kr, vn, th.

Tim

Pemimpin & Penasihat Proyek (Jul 2011-sekarang)
Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

Murid-Murid S1 Peniliti 1
CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

Murid-Murid Proyek Tahun Terakhir/UROP 1
Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

Murid-Murid S1 Peniliti 2
CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Murid-Murid Proyek Tahun Terakhir/UROP 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Murid-Murid S1 Peniliti 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Murid-Murid Proyek Tahun Terakhir/UROP 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

Ucapan Terima Kasih
NUS CDTL gave Teaching Enhancement Grant to kickstart this project.

For Academic Year 2023/24, a generous donation from Optiver will be used to further develop VisuAlgo.

Syarat Guna

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors. You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website (https://visualgo.net) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Associate Professor Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Associate Professor Steven Halim. His contact is the concatenation of his name and add gmail dot com.

Kebijakan Privasi

Version 1.2 (Updated Fri, 18 Aug 2023).

Since Fri, 18 Aug 2023, we no longer use Google Analytics. Thus, all cookies that we use now are solely for the operations of this website. The annoying cookie-consent popup is now turned off even for first-time visitors.

Since Fri, 07 Jun 2023, thanks to a generous donation by Optiver, anyone in the world can self-create a VisuAlgo account to store a few customization settings (e.g., layout mode, default language, playback speed, etc).

Additionally, for NUS students, by using a VisuAlgo account (a tuple of NUS official email address, student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your course lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the course smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the course unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Prof Halim himself.

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.