C Academy · Pelajaran

Linked List Dua Arah

Tautan dua arah.

Linked List Dua Arah adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.

Tautan dua arah

Daftar tertaut ganda memberikan setiap simpul dua penunjuk: satu ke simpul next dan satu ke simpul prev (sebelumnya).

Dengan demikian, Anda dapat menelusuri daftar ke dua arah dan penghapusan menjadi lebih sederhana.

#include <stdio.h>

struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
};

int main(void) {
    printf("Each node links forward and backward\n");
    return 0;
}

Mendefinisikan simpul

Struktur tersebut menambahkan penunjuk prev di samping next. Keduanya bernilai NULL di ujung-ujung daftar.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 1; n->prev = NULL; n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Pembantu pembuatan

Seperti sebelumnya, fungsi pembantu memusatkan proses alokasi. Fungsi tersebut menetapkan prev dan next ke NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v; n->prev = NULL; n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(42);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Menautkan simpul ke dua arah

Saat menghubungkan dua simpul, Anda harus memperbarui kedua arah: next milik simpul pertama dan prev milik simpul kedua.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b;
    b->prev = a;
    printf("forward %d, back %d\n", a->next->value, b->prev->value);
    free(a); free(b);
    return 0;
}

Menyisipkan di awal

Untuk menambahkan ke awal: next simpul baru adalah kepala lama, prev kepala lama adalah simpul baru, lalu kepala dipindahkan ke simpul baru.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    if (*head) (*head)->prev = n;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 2); push(&head, 1);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Penelusuran maju

Penelusuran maju sama seperti pada daftar tertaut tunggal: ikuti next hingga NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    free(a); free(b);
    return 0;
}

Penelusuran mundur

Keunggulan utamanya: dari simpul mana pun, Anda dapat menelusuri mundur dengan mengikuti penunjuk prev hingga mencapai kepala.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
    printf("\n");
    free(a); free(b); free(c);
    return 0;
}

Penghapusan lebih mudah

Karena setiap simpul mengetahui pendahulunya, Anda dapat menghapusnya tanpa mencari simpul sebelumnya.

Cukup hubungkan node->prev ke node->next pada kedua arah.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void del(struct Node **head, struct Node *n) {
    if (n->prev) n->prev->next = n->next; else *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next=b; b->prev=a; b->next=c; c->prev=b;
    struct Node *head = a;
    del(&head, b);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Perbarui kedua tetangga

Saat menghapus simpul, selalu perbaiki next milik simpul sebelumnya dan prev milik simpul berikutnya.

Periksa NULL di setiap ujung agar Anda tidak melakukan dereferensi terhadap tetangga yang tidak ada.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    a->next = NULL;
    free(b);
    printf("now only %d remains\n", a->value);
    free(a);
    return 0;
}

Menyimpan penunjuk ekor

Banyak daftar tertaut ganda juga menyimpan penunjuk ekor ke simpul terakhir, sehingga penambahan di akhir dan iterasi mundur dari ujung dapat dilakukan dalam O(1).

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1), *tail = head;
    struct Node *n = make(2);
    tail->next = n; n->prev = tail; tail = n;
    printf("tail = %d\n", tail->value);
    free(head); free(n);
    return 0;
}

Pertukaran keuntungan dan kerugian

Daftar tertaut ganda memerlukan memori tambahan (satu penunjuk lebih banyak per simpul) dan mengharuskan dua tautan diperbarui setiap kali terjadi perubahan.

Sebagai gantinya, Anda mendapatkan penelusuran dua arah dan penghapusan simpul yang diketahui dalam O(1). Pilihlah berdasarkan kebutuhan Anda.

#include <stdio.h>

int main(void) {
    printf("Singly: less memory, one-way\n");
    printf("Doubly: more memory, two-way + easy delete\n");
    return 0;
}

Pemeriksaan Singkat

Uji pemahaman Anda tentang daftar tertaut ganda.

Ringkasan

Anda telah mempelajari daftar tertaut ganda:

Setiap simpul memiliki penunjuk prev dan next.
Penautan mengharuskan pembaruan pada kedua arah.
Anda dapat menelusuri maju dan mundur, serta menghapus simpul yang diketahui dalam O(1).
Biayanya adalah memori tambahan dan lebih banyak pembaruan penunjuk; penunjuk ekor memungkinkan penambahan di akhir dalam O(1).

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Linked List Dua Arah” gratis?

Ya — teks lengkap “Linked List Dua Arah” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Linked List Dua Arah”?

Tautan dua arah. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C Academy?

Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Linked List Dua Arah” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke C Academy