PricingLoginStart free
C Academy · Pelajaran

Senarai Pautan Berganda

Pautan dua hala

Pelajaran 4 daripada 413 langkah

Senarai Pautan Berganda ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Pautan dua hala

Senarai berpaut dua hala memberikan setiap Node dua penuding: satu kepada Node next dan satu kepada Node prev (sebelumnya).

Ini membolehkan anda menelusuri senarai dalam kedua-dua arah dan memudahkan pemadaman.

#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;
}

Mentakrifkan Node

Struktur itu menambah penuding prev di samping next. Kedua-duanya ialah NULL di hujung senarai.

#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 penciptaan

Seperti sebelum ini, fungsi pembantu memusatkan peruntukan. Fungsi itu menetapkan prev dan next kepada 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;
}

Memautkan Node dalam kedua-dua arah

Apabila menyambungkan dua Node, anda mesti mengemas kini kedua-dua arah: next Node pertama dan prev Node 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;
}

Sisipkan di hadapan

Menolak ke hadapan: next Node baharu ialah kepala lama, prev kepala lama ialah Node baharu, kemudian kepala dialihkan kepada Node baharu.

#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 ke hadapan

Penelusuran ke hadapan sama seperti senarai berpaut sehala: ikuti next sehingga 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 ke belakang

Kelebihan utamanya: dari mana-mana Node, anda boleh menelusuri ke belakang dengan mengikuti penuding prev sehingga 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;
}

Pemadaman lebih mudah

Oleh sebab setiap Node mengetahui pendahulunya, anda boleh memadamkannya tanpa mencari Node sebelumnya.

Hanya sambungkan node->prev kepada node->next dalam kedua-dua 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;
}

Kemas kini kedua-dua jiran

Apabila mengalih Node, sentiasa betulkan next Node sebelumnya dan prev Node berikutnya.

Semak NULL di setiap hujung supaya anda tidak menyahrujuk jiran yang tiada.

#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 penuding ekor

Banyak senarai berpaut dua hala turut menyimpan penuding ekor kepada Node terakhir, yang membolehkan penambahan di belakang O(1) dan lelaran ke belakang dari hujung.

#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 kelebihan dan kos

Senarai berpaut dua hala menggunakan memori tambahan (satu penuding lagi bagi setiap Node) dan memerlukan dua pautan dikemas kini pada setiap perubahan.

Sebagai balasan, anda mendapat penelusuran dua hala dan pemadaman O(1) bagi Node yang diketahui. Buat pilihan berdasarkan keperluan 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;
}

Semakan Pantas

Uji pemahaman anda tentang senarai berpaut dua hala.

Jawab dalam pelajaran interaktif

Ringkasan

Anda telah mempelajari senarai berpaut dua hala:

  • Setiap Node mempunyai penuding prev dan next.
  • Memautkan Node memerlukan kemas kini pada kedua-dua arah.
  • Anda boleh menelusuri ke hadapan dan ke belakang, serta memadam Node yang diketahui dalam O(1).
  • Kosnya ialah memori tambahan dan lebih banyak kemas kini penuding; penuding ekor membolehkan penambahan di belakang O(1).
Percuma untuk bermula

Pelajari C dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
39
Pelajaran
144
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Senarai Pautan Berganda” percuma?

Ya — teks penuh “Senarai Pautan Berganda” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Senarai Pautan Berganda”?

Pautan dua hala Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan C Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “Senarai Pautan Berganda” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Senarai Pautan Tunggal
  2. Penyisipan dan Pemadaman
  3. Pengembaraan dan Carian
  4. Senarai Pautan Berganda
← Kembali ke C Academy