Search Here - Games / News / Gadget
Home TEKNIK INFORMATIKA LINKED LIST

LINKED LIST


Linked list
Dari Wikipedia, ensiklopedia bebas
Langsung ke: navigasi , cari
Dalam ilmu komputer , sebuah linked list adalah sebuah struktur data yang terdiri dari sekelompok node yang bersama-sama mewakili berurutan. Dalam bentuk yang paling sederhana, setiap node terdiri dari datum dan referensi (dengan kata lain, link) ke node berikutnya dalam urutan; varian lebih kompleks menambahkan link tambahan. Struktur ini memungkinkan untuk penyisipan efisien atau penghapusan unsur-unsur dari setiap posisi dalam urutan.

Sendiri-linked-list.svg
Sebuah linked list yang node berisi dua bidang: nilai integer dan link ke node berikutnya. Node terakhir ini terkait dengan terminator digunakan untuk menandai akhir daftar.
Daftar link adalah salah satu struktur data sederhana dan paling umum. Mereka dapat digunakan untuk melaksanakan beberapa umum lainnya jenis data abstrak , termasuk tumpukan , antrian , array asosiatif , dan ekspresi simbolik , meskipun tidak jarang untuk mengimplementasikan struktur data lain secara langsung tanpa menggunakan daftar sebagai dasar pelaksanaan.
Manfaat utama dari linked list lebih konvensional Array adalah bahwa elemen list dengan mudah dapat dimasukkan atau dihapus tanpa realokasi atau reorganisasi seluruh struktur karena item data tidak perlu disimpan contiguously dalam memori atau pada disk. Daftar Linked memungkinkan penyisipan dan penghapusan node pada setiap titik dalam daftar, dan dapat melakukannya dengan sejumlah konstan operasi jika link sebelumnya ke link yang ditambahkan atau dihapus dipertahankan selama traversal daftar.
Di sisi lain, daftar link sederhana dengan sendirinya tidak memungkinkan akses acak untuk data, atau segala bentuk pengindeksan efisien. Dengan demikian, banyak operasi dasar - seperti memperoleh node terakhir dari daftar (dengan asumsi bahwa node terakhir tidak dipertahankan sebagai referensi node terpisah dalam struktur daftar), atau menemukan sebuah node yang berisi datum tertentu, atau mencari tempat di mana simpul baru harus disisipkan - mungkin memerlukan pemindaian sebagian besar atau semua elemen daftar.
Isi
Sejarah
Daftar Linked dikembangkan pada 1955-56 oleh Allen Newell , Cliff Shaw dan Herbert Simon di RAND Corporation sebagai dasar struktur data untuk mereka Bahasa Pengolahan Informasi . IPL digunakan oleh penulis untuk mengembangkan beberapa awal kecerdasan buatan program, termasuk Mesin Teori Logika, para Problem Solver Umum , dan program catur komputer. Laporan pekerjaan mereka muncul di Transaksi IRE pada Teori Informasi pada tahun 1956, dan prosiding konferensi beberapa 1957-1959, termasuk Prosiding Konferensi Komputer Barat Bersama pada tahun 1957 dan 1958, dan Pengolahan Informasi (Prosiding pertama UNESCO Konferensi Internasional tentang Informasi Pengolahan ) pada tahun 1959. Diagram sekarang-klasik yang terdiri dari blok yang mewakili node daftar dengan panah yang menunjuk ke node daftar berturut-turut muncul di "Pemrograman Mesin Teori Logika" oleh Newell dan Shaw di Proc. WJCC Februari 1957. Newell dan Simon yang dikenal dengan ACM Turing Award pada tahun 1975 karena telah "memberikan kontribusi dasar untuk kecerdasan buatan, psikologi kognisi manusia, dan pengolahan daftar". Masalah mesin penerjemahan untuk bahasa alami pengolahan dipimpin Victor Yngve di Massachusetts Institute of Technology (MIT) untuk menggunakan daftar link sebagai struktur data dalam bahasa pemrograman Xinfa untuk penelitian komputer di bidang linguistik . Sebuah laporan tentang bahasa ini berjudul "Sebuah bahasa pemrograman untuk terjemahan mekanis" muncul dalam Penerjemahan Mesin pada tahun 1958.
LISP , berdiri untuk prosesor daftar, diciptakan oleh John McCarthy pada tahun 1958 ketika ia berada di MIT dan pada tahun 1960 ia menerbitkan desain dalam sebuah makalah dalam Komunikasi ACM , yang berjudul "Fungsi Rekursif dari Ekspresi simbolik dan Komputasi mereka oleh Mesin, Bagian saya ". Salah satu struktur utama LISP itu data adalah linked list. Pada awal 1960-an, kegunaan kedua daftar terhubung dan bahasa yang menggunakan struktur ini sebagai representasi data primer mereka mapan. Bert Green dari MIT Lincoln Laboratory menerbitkan sebuah artikel yang berjudul "bahasa Komputer untuk manipulasi simbol" Transaksi IRE pada Faktor Manusia dalam Elektronika Maret 1961 yang dirangkum keuntungan dari pendekatan linked list. Sebuah artikel review kemudian, "Sebuah Perbandingan daftar pengolahan bahasa komputer" oleh Bobrow dan Raphael, muncul di Komunikasi ACM pada bulan April 1964.
Beberapa sistem operasi yang dikembangkan oleh Konsultan Sistem Teknis (awalnya dari West Lafayette Indiana, dan kemudian dari Chapel Hill, North Carolina) digunakan daftar sendiri-sendiri terkait sebagai struktur file. Sebuah entri direktori menunjuk ke sektor pertama dari sebuah file, dan bagian berikutnya dari file yang terletak oleh pointer melintasi. Sistem yang menggunakan teknik ini termasuk Flex (untuk Motorola 6800 CPU), mini-Flex (CPU yang sama), dan Flex9 (untuk Motorola 6809 CPU). Varian dikembangkan oleh TSC untuk dan dipasarkan oleh Asap Sinyal Penyiaran di California, digunakan penggandaan daftar dengan cara yang sama.
Para TSS/360 sistem operasi, yang dikembangkan oleh IBM untuk System 360/370 mesin, menggunakan linked list ganda untuk sistem katalog mereka file. Struktur direktori mirip dengan Unix, di mana direktori bisa berisi file dan / atau direktori lain dan memperpanjang untuk setiap kedalaman. Sebuah kutu utilitas diciptakan untuk memperbaiki masalah file sistem setelah terjadi kecelakaan, karena bagian modifikasi dari katalog file yang kadang-kadang dalam memori ketika kecelakaan terjadi. Masalah yang terdeteksi dengan membandingkan link maju dan mundur untuk konsistensi. Jika link maju adalah korup, maka jika link ke belakang ke node yang terinfeksi ditemukan, forward link ditetapkan untuk node dengan link ke belakang. Sebuah komentar lucu dalam kode sumber mana utilitas ini dipanggil menyatakan "Semua orang tahu kerah kutu menghilangkan bug pada kucing".
Dasar konsep dan tata nama
Setiap record dari sebuah linked list sering disebut elemen atau simpul .
Bidang setiap node yang berisi alamat dari node berikutnya biasanya disebut link berikutnya atau pointer berikutnya. Bidang yang tersisa dikenal sebagai data, informasi, nilai, kargo, atau bidang muatan.
Kepala daftar adalah node pertama. Ekor daftar dapat merujuk baik ke seluruh daftar setelah kepala, atau ke node terakhir dalam daftar. Dalam Lisp dan beberapa bahasa turunan, node berikutnya dapat disebut cdr (diucapkan bisa-er) daftar, sedangkan muatan node kepala dapat disebut mobil .
http://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/Linked_list_post_office_box_analogy.svg/150px-Linked_list_post_office_box_analogy.svg.png
http://bits.wikimedia.org/static-1.20wmf2/skins/common/images/magnify-clip.png
Bob (bawah) memiliki kunci kotak 201, yang berisi paruh pertama buku dan kunci kotak 102, yang berisi sisa buku.
kantor analogi kotak Posting
Konsep linked list dapat dijelaskan dengan analogi sederhana untuk dunia nyata kotak kantor pos . Misalkan Alice adalah seorang mata-mata yang ingin memberikan codebook untuk Bob dengan menempatkan dalam kotak pos dan kemudian memberinya kunci. Namun, buku ini terlalu tebal untuk bisa masuk dalam kotak pos tunggal, jadi alih-alih ia membagi buku menjadi dua bagian dan pembelian kotak pos dua kantor. Pada kotak pertama, ia menempatkan paruh pertama buku dan kunci ke kotak kedua, dan di kotak kedua ia menempatkan paruh kedua buku tersebut. Dia kemudian memberikan Bob kunci untuk kotak pertama. Tidak peduli seberapa besar buku ini, skema ini dapat diperluas ke sejumlah kotak dengan selalu menempatkan kunci ke kotak berikutnya dalam kotak sebelumnya.
Dalam analogi ini, kotak sesuai dengan elemen atau node, kunci sesuai dengan pointer, dan buku itu sendiri adalah data. Kunci diberikan kepada Bob adalah pointer kepala, sedangkan yang disimpan dalam kotak adalah pointer berikutnya. Skema seperti dijelaskan di atas adalah linked list tunggal (lihat di bawah).
daftar Linear dan melingkar
Dalam terakhir simpul dari daftar, bidang hubungan sering berisi referensi null, nilai khusus digunakan untuk menunjukkan kurangnya node lebih lanjut. Sebuah konvensi yang kurang umum adalah untuk membuat satu titik ke node pertama dari daftar; dalam kasus itu daftar dikatakan melingkar atau sirkuler terkait, jika tidak dikatakan terbuka atau linier.
Sirkuler-linked-list.svg
Sebuah linked list melingkar
Tunggal, ganda, dan kalikan terkait daftar
Daftar sendiri-sendiri terkait berisi node yang memiliki data lapangan serta kolom berikutnya, yang menunjuk ke node berikutnya dalam linked list.
Sendiri-linked-list.svg
Sebuah linked list tunggal yang berisi dua node bidang: nilai integer dan link ke node berikutnya
Dalam daftar ganda terkait , setiap node berisi, selain link di sebelah-node, bidang link kedua menunjuk ke node sebelumnya dalam urutan. Dua link dapat disebut maju (s) dan mundur, atau berikutnya dan prev (ious).
Doubly-linked-list.svg
Daftar ganda terkait yang berisi node tiga bidang: nilai integer, forward link ke node berikutnya, dan link ke belakang ke node sebelumnya
Sebuah teknik yang dikenal sebagai XOR-linking memungkinkan daftar ganda terkait untuk dilaksanakan menggunakan medan single link di setiap node. Namun, teknik ini membutuhkan kemampuan untuk melakukan operasi bit pada alamat, dan karena itu mungkin tidak tersedia dalam beberapa bahasa tingkat tinggi.
Dalam daftar multiply berhubungan, setiap node berisi bidang menghubungkan dua atau lebih, masing-masing bidang yang digunakan untuk menghubungkan set yang sama rekaman data dalam urutan yang berbeda (misalnya, dengan nama, oleh departemen, dengan tanggal lahir, dll). (Sementara penggandaan daftar dapat dilihat sebagai kasus khusus dari daftar multiply terkait, fakta bahwa dua perintah yang berlawanan satu sama lead lain untuk algoritma sederhana dan lebih efisien, sehingga mereka biasanya diperlakukan sebagai kasus yang terpisah.)
Dalam kasus daftar ganda terkait melingkar, satu-satunya perubahan yang terjadi adalah itu, atau "ekor", dari daftar kata dihubungkan kembali ke depan, atau "kepala", daftar dan sebaliknya.
Sentinel node
Artikel utama: simpul Sentinel
Dalam beberapa implementasi, sebuah sentinel tambahan atau node boneka dapat ditambahkan sebelum catatan data pertama dan / atau setelah yang terakhir. Konvensi ini menyederhanakan dan mempercepat beberapa daftar penanganan algoritma, dengan memastikan bahwa semua link dapat dengan aman dereferenced dan bahwa setiap daftar (bahkan salah satu yang tidak mengandung elemen data) selalu memiliki "terakhir" "pertama" dan node.
Daftar Kosong
Daftar kosong adalah daftar yang tidak mengandung catatan data. Ini biasanya sama dengan mengatakan bahwa ia memiliki nol node. Jika node sentinel yang digunakan, daftar ini biasanya dikatakan kosong bila hanya memiliki kelenjar sentinel.
Hash menghubungkan
Bidang link yang tidak perlu secara fisik bagian dari node. Jika catatan data disimpan dalam array dan direferensikan oleh indeks mereka, bidang Link dapat disimpan dalam array yang terpisah dengan indeks yang sama dengan catatan data.
Daftar menangani
Karena referensi ke simpul pertama memberikan akses ke seluruh daftar, referensi yang sering disebut alamat, pointer, atau pegangan daftar. Algoritma yang memanipulasi terkait berisi daftar biasanya mendapatkan pegangan seperti ke daftar input dan kembali pegangan ke daftar yang dihasilkan. Bahkan, dalam konteks algoritma tersebut, kata "daftar" sering berarti "menangani daftar". Dalam beberapa situasi, bagaimanapun, mungkin nyaman untuk merujuk kepada daftar dengan pegangan yang terdiri dari dua link, menunjuk ke node pertama dan terakhir.
Menggabungkan alternatif
Berbagai alternatif di atas dapat sewenang-wenang dikombinasikan di hampir segala hal, jadi satu mungkin memiliki penggandaan daftar melingkar tanpa penjaga, daftar sendiri-sendiri terkait melingkar dengan penjaga, dll
pengorbanan
Seperti pilihan paling dalam pemrograman komputer dan desain, tidak ada metode yang cocok untuk semua keadaan. Sebuah linked list struktur data mungkin bekerja dengan baik dalam satu kasus, tapi menyebabkan masalah di negara lain. Ini adalah daftar dari beberapa pengorbanan umum yang melibatkan struktur linked list.
Linked daftar vs array dinamis

Linked list
Susunan
Dinamis
susunan
Seimbang
pohon
Random akses
daftar
Pengindeksan
Θ (n)
Θ (1)
Θ (1)
Θ (log n)
Θ (log n)
Menyisipkan / menghapus awal
Θ (1)
N / A
Θ (n)
Θ (log n)
Θ (1)
Menyisipkan / menghapus pada akhir
Θ (1)
N / A
(1) Θ diamortisasi
Θ (log n)
Θ (log n) update
Menyisipkan / menghapus di tengah
mencari waktu +
Θ (1) [1] [2] [3]
N / A
Θ (n)
Θ (log n)
Θ (log n) update
Ruang terbuang (rata-rata)
Θ (n)
0
Θ (n) [4]
Θ (n)
Θ (n)
Sebuah array dinamis adalah struktur data yang mengalokasikan semua elemen contiguously dalam memori, dan membuat hitungan saat ini jumlah elemen. Jika tempat yang disediakan untuk array dinamis terlampaui, itu dialokasikan kembali dan (mungkin) disalin, operasi yang mahal.
Daftar link memiliki beberapa keunggulan dibandingkan array dinamis. Penyisipan atau penghapusan elemen pada titik tertentu dari daftar, dengan asumsi bahwa kita memiliki pointer ke node (sebelum satu yang akan dihapus, atau sebelum titik penyisipan) sudah, adalah operasi konstan-waktu, sedangkan penyisipan dalam array dinamis di lokasi secara acak akan membutuhkan setengah bergerak elemen rata-rata, dan semua elemen dalam kasus terburuk. Sementara satu dapat "menghapus" sebuah elemen dari sebuah array dalam waktu yang konstan dengan entah bagaimana menandai slotnya sebagai "kosong", ini menyebabkan fragmentasi yang menghambat kinerja iterasi.
Selain itu, unsur sewenang-wenang banyak dapat dimasukkan ke dalam linked list, hanya dibatasi oleh memori total yang tersedia, sedangkan array dinamis akhirnya akan mengisi array yang mendasarinya struktur data dan harus mengalokasikan kembali - operasi yang mahal, yang bahkan mungkin tidak mungkin jika memori terfragmentasi, meski biaya realokasi dapat setara dengan sisipan, dan biaya dari penyisipan karena realokasi masih akan diamortisasi O (1). Ini membantu dengan menambahkan elemen di akhir array, tetapi memasukkan ke dalam (atau menghapus dari) posisi tengah tetap membawa biaya mahal karena data bergerak untuk mempertahankan kedekatan. Sebuah array dari yang banyak unsur dihapus mungkin juga harus diubah ukurannya untuk menghindari pemborosan ruang terlalu banyak.
Di sisi lain, array dinamis (dan juga berukuran tetap struktur data array ) memungkinkan konstan-waktu akses acak , sementara daftar link hanya mengizinkan akses sekuensial untuk elemen. Daftar sendiri-sendiri terkait, pada kenyataannya, hanya dapat dilalui satu arah. Hal ini membuat daftar terkait tidak cocok untuk aplikasi di mana ini berguna untuk mencari suatu elemen dengan indeks dengan cepat, seperti heapsort . Akses sekuensial pada array dan array dinamis juga lebih cepat dari pada daftar link pada banyak komputer, karena mereka memiliki yang optimal lokalitas referensi dan dengan demikian memanfaatkan caching data.
Kelemahan lain dari daftar link adalah penyimpanan tambahan yang diperlukan untuk referensi, yang sering membuat mereka tidak praktis untuk daftar item data kecil seperti karakter atau nilai boolean , karena overhead penyimpanan untuk link dapat melebihi dengan faktor dua atau lebih ukuran data. Sebaliknya, array dinamis hanya membutuhkan ruang untuk data itu sendiri (dan jumlah yang sangat kecil data kontrol). [catatan 1] Hal ini juga bisa lambat, dan dengan pengalokasi naif, boros, untuk mengalokasikan memori secara terpisah untuk setiap baru elemen, masalah umum dipecahkan menggunakan kolam memori .
Beberapa solusi hibrida mencoba untuk menggabungkan keunggulan dari dua representasi. daftar link membuka gulungan menyimpan beberapa elemen dalam setiap node daftar, meningkatkan kinerja cache sekaligus mengurangi overhead memori referensi. CDR coding tidak baik ini juga, dengan mengganti referensi dengan data aktual direferensikan , yang membentang dari ujung catatan referensi.
Sebuah contoh yang baik yang menyoroti pro dan kontra dari menggunakan array dinamis vs daftar link adalah dengan menerapkan program yang menyelesaikan masalah Yosefus . Masalah Yosefus adalah metode pemilihan yang bekerja dengan memiliki sekelompok orang berdiri membentuk lingkaran. Mulai dari orang yang telah ditentukan, Anda menghitung sekitar lingkaran n kali. Setelah Anda mencapai orang ke-n, membawa mereka keluar dari lingkaran dan memiliki anggota menutup lingkaran. Kemudian menghitung sekitar lingkaran n sama kali dan ulangi proses, sampai hanya satu orang yang tersisa. Orang yang menang pemilu. Hal ini menunjukkan kekuatan dan kelemahan dari sebuah linked list vs array dinamis, karena jika Anda melihat orang sebagai terhubung node dalam linked list melingkar maka hal itu menunjukkan betapa mudahnya linked list dapat menghapus node (karena hanya harus mengatur ulang link ke node yang berbeda). Namun, linked list akan menjadi miskin dalam menemukan orang berikutnya untuk menghapus dan perlu mencari melalui daftar sampai menemukan orang itu. Sebuah array dinamis, di sisi lain, akan menjadi miskin di node menghapus (atau elemen) karena tidak dapat menghapus satu simpul individual tanpa menggeser semua elemen hingga daftar per satu. Namun, sangat mudah untuk menemukan orang yang ke-n dalam lingkaran ini dengan langsung referensi mereka dengan posisi mereka dalam array.
Para peringkat daftar masalah menyangkut konversi efisien representasi linked list ke array. Meskipun sepele untuk komputer konvensional, memecahkan masalah ini dengan sebuah algoritma paralel adalah rumit dan telah menjadi subyek banyak penelitian.
Sebuah pohon seimbang memiliki pola akses memori yang sama dan overhead ruang untuk linked list sementara memungkinkan pengindeksan jauh lebih efisien, mengambil O (log n) bukan O (n) untuk akses acak. Namun, penyisipan dan penghapusan operasi lebih mahal karena overhead dari manipulasi pohon untuk menjaga keseimbangan. Skema efisien ada untuk pohon untuk secara otomatis menjaga diri dalam keadaan hampir seimbang, seperti pohon AVL atau merah-hitam pohon .
linier daftar sendiri-sendiri terkait vs daftar lain
Sementara ganda terkait dan / atau daftar melingkar memiliki keunggulan dibandingkan daftar linear tunggal terkait, daftar linier menawarkan beberapa keuntungan yang membuat mereka lebih baik dalam beberapa situasi.
Untuk satu hal, daftar linear tunggal terkait adalah rekursif struktur data, karena mengandung pointer ke objek yang lebih kecil dari jenis yang sama. Untuk itu, banyak operasi pada tunggal daftar linier terkait (seperti penggabungan dua daftar, atau menyebutkan elemen dalam urutan terbalik) sering memiliki algoritma rekursif sangat sederhana, jauh lebih sederhana daripada solusi menggunakan perintah berulang . Sementara satu dapat beradaptasi mereka solusi rekursif untuk penggandaan daftar dan sirkuler terkait, prosedur umumnya memerlukan argumen tambahan dan kasus dasar yang lebih rumit.
Daftar sendiri-sendiri terkait linier juga memungkinkan ekor berbagi , penggunaan sebagian akhir umum dari sub-daftar sebagai bagian terminal dari dua daftar yang berbeda. Secara khusus, jika node baru ditambahkan di awal daftar, daftar mantan tetap tersedia sebagai ekor yang baru - sebuah contoh sederhana dari sebuah struktur data persisten . Sekali lagi, ini tidak benar dengan varian lainnya: sebuah node tidak pernah mungkin milik dua lingkaran yang berbeda atau penggandaan daftar.
Secara khusus, akhir-sentinel node dapat dibagi di antara tunggal terkait non-melingkar daftar. Satu bahkan dapat menggunakan node akhir sentinel sama untuk setiap daftar tersebut. Dalam Lisp , misalnya, setiap daftar yang tepat berakhir dengan link ke node khusus, dilambangkan dengan nil atau () , yang CAR dan CDR point link pada dirinya sendiri. Dengan demikian prosedur Lisp dapat dengan aman mengambil CAR atau CDR daftar apapun.
Memang, keuntungan dari varian mewah sering terbatas pada kompleksitas dari algoritma, bukan dalam efisiensi mereka. Daftar melingkar, khususnya, biasanya dapat ditiru dengan daftar linier bersama dengan dua variabel yang menunjuk ke node pertama dan terakhir, tanpa biaya tambahan.
Ganda terkait vs tunggal terkait
Double-linked list memerlukan lebih banyak ruang per node (kecuali satu menggunakan XOR-linking ), dan operasi dasar mereka lebih mahal, tetapi mereka sering lebih mudah untuk memanipulasi karena mereka memungkinkan akses sekuensial ke daftar di kedua arah. Dalam daftar ganda terkait, seseorang dapat memasukkan atau menghapus sebuah node dalam sejumlah operasi konstan diberikan hanya alamat node. Untuk melakukan hal yang sama dalam linked list tunggal, seseorang harus memiliki alamat pointer ke node yang, yang bisa berupa pegangan untuk daftar keseluruhan (dalam kasus node pertama) atau bidang link di simpul sebelumnya. Beberapa algoritma memerlukan akses di kedua arah. Di sisi lain, penggandaan daftar tidak mengijinkan ekor-sharing dan tidak dapat digunakan sebagai struktur data persisten .
sirkuler terkait vs linear terkait
Daftar sirkuler terkait mungkin pilihan yang alami untuk mewakili array yang secara alami melingkar, misalnya sudut sebuah poligon , kolam buffer yang digunakan dan dirilis pada FIFO order, atau serangkaian proses yang harus berbagi waktu dalam putaran order-robin . Dalam aplikasi ini, pointer ke setiap node berfungsi sebagai pegangan untuk seluruh daftar.
Dengan daftar melingkar, pointer ke node terakhir memberikan akses mudah juga untuk node pertama, dengan mengikuti satu link. Dengan demikian, dalam aplikasi yang memerlukan akses ke kedua ujung daftar (misalnya, dalam pelaksanaan antrian), struktur melingkar memungkinkan seseorang untuk menangani struktur dengan pointer tunggal, bukan dua.
Daftar melingkar dapat dibagi menjadi dua daftar melingkar, dalam waktu yang konstan, dengan memberikan alamat dari node terakhir dari masing-masing bagian. Operasi ini terdiri dalam swapping isi bidang link dari dua node. Menerapkan operasi yang sama untuk dua node dalam dua daftar yang berbeda bergabung daftar dua menjadi satu. Properti ini sangat menyederhanakan beberapa algoritma dan struktur data, seperti tepi quad- dan wajah-tepi .
Representasi paling sederhana untuk daftar melingkar kosong (hal seperti itu masuk akal) adalah pointer null, yang menunjukkan bahwa daftar tersebut tidak memiliki node. Tanpa pilihan ini, banyak algoritma harus menguji untuk kasus khusus ini, dan menanganinya secara terpisah. Sebaliknya, penggunaan nol untuk menunjukkan sebuah daftar linear kosong lebih alami dan seringkali menimbulkan kasus-kasus khusus yang lebih sedikit.
Menggunakan sentinel node
Sentinel node dapat menyederhanakan operasi list tertentu, dengan memastikan bahwa node berikutnya dan / atau sebelumnya ada untuk setiap elemen, dan bahwa daftar kosong bahkan memiliki minimal satu node. Satu juga dapat menggunakan sentinel node pada akhir daftar, dengan medan data yang sesuai, untuk menghilangkan beberapa akhir-daftar tes. Misalnya, ketika memindai daftar mencari node dengan nilai yang diberikan x, pengaturan bidang data sentinel untuk x membuat tidak perlu untuk menguji untuk end-daftar-di dalam loop. Contoh lain adalah penggabungan dua daftar diurutkan: jika penjaga mereka memiliki bidang data set dengan + ∞, pilihan output node berikutnya tidak perlu penanganan khusus untuk daftar kosong.
Namun, kelenjar sentinel menggunakan ruang tambahan (terutama dalam aplikasi yang menggunakan daftar singkat banyak), dan mereka dapat mempersulit operasi lain (seperti penciptaan daftar kosong baru).
Namun, jika daftar melingkar digunakan hanya untuk mensimulasikan daftar linear, orang dapat menghindari beberapa kompleksitas ini dengan menambahkan sentinel node tunggal untuk setiap daftar, antara terakhir dan node data pertama. Dengan konvensi ini, daftar kosong terdiri dari simpul sentinel sendiri, menunjuk ke dirinya sendiri melalui link berikutnya node. Gagang daftar kemudian harus pointer ke node data terakhir, sebelum sentinel, jika daftar tidak kosong, atau ke sentinel itu sendiri, jika daftar kosong.
Trik yang sama dapat digunakan untuk menyederhanakan penanganan daftar linear ganda terkait, dengan mengubahnya menjadi daftar ganda terkait melingkar dengan sentinel node tunggal. Namun, dalam kasus ini, pegangan harus pointer ke node tunggal boneka itu sendiri. [5]
Operasi daftar Linked
Ketika memanipulasi daftar link di tempat, perawatan harus diambil untuk tidak menggunakan nilai-nilai yang Anda telah batal dalam tugas-tugas sebelumnya. Hal ini membuat algoritma untuk menyisipkan atau menghapus node linked list agak halus. Bagian ini memberikan pseudocode untuk menambahkan atau menghapus node dari tunggal, ganda, dan daftar sirkuler terkait di tempat. Sepanjang kita akan menggunakan null untuk merujuk pada suatu penanda akhir-daftar atau sentinel , yang dapat diimplementasikan dalam beberapa cara.
daftar linear terkait
daftar sendiri-sendiri terkait
Simpul struktur data kita akan memiliki dua bidang. Kami juga menyimpan firstNode variabel yang selalu menunjuk ke node pertama dalam daftar, atau null untuk daftar kosong.
  catatan Node {
     data; / / Data yang disimpan dalam node
     Node / / A berikutnya referensi ke node berikutnya, null untuk node terakhir
  }
  Daftar rekor {
      Node firstNode / / menunjuk ke node pertama dari daftar; null untuk daftar kosong
  }
Traversal dari linked list tunggal sederhana, dimulai dari node pertama dan mengikuti setiap link berikutnya sampai kita sampai akhir:
  node: = list.firstNode
  sedangkan simpul tidak nol
      (Melakukan sesuatu dengan node.data)
      node: = node.next
Menyisipkan kode berikut simpul setelah simpul yang ada dalam linked list sendiri-sendiri. Diagram menunjukkan cara kerjanya. Memasukkan sebuah node sebelum yang sudah ada tidak dapat dilakukan secara langsung, melainkan kita harus melacak node sebelumnya dan menyisipkan simpul setelah itu.
CPT-LinkedLists-addingnode.svg
  fungsi insertAfter (Node node, node newNode) / / insert newNode setelah simpul
      newNode.next: = node.next
      node.next: = newNode
Memasukkan di awal daftar tersebut memerlukan fungsi yang terpisah. Hal ini memerlukan memperbarui firstNode.
  fungsi insertBeginning (Daftar list, Node newNode) / / insert simpul sebelum simpul pertama saat ini
      newNode.next: = list.firstNode
      list.firstNode: = newNode
Demikian pula, kita memiliki fungsi untuk menghapus node setelah node yang diberikan, dan untuk menghapus simpul dari awal daftar. Diagram menunjukkan mantan. Untuk menemukan dan menghapus node tertentu, satu lagi harus melacak elemen sebelumnya.
CPT-LinkedLists-deletingnode.svg
  fungsi removeAfter (node ​​node) / / menghapus simpul masa lalu yang satu ini
      obsoleteNode: = node.next
      node.next: = node.next.next
      menghancurkan obsoleteNode
  fungsi removeBeginning (daftar Daftar) / / menghapus simpul pertama
      obsoleteNode: = list.firstNode
      list.firstNode: node = list.firstNode.next / / titik dihapus lalu
      menghancurkan obsoleteNode
Perhatikan bahwa removeBeginning() set list.firstNode ke null ketika menghapus node terakhir dalam daftar.
Karena kita tidak bisa iterate mundur, efisien insertBefore atau removeBefore operasi tidak mungkin.
Menambahkan satu daftar link ke yang lain bisa tidak efisien kecuali referensi ke ekor disimpan sebagai bagian dari struktur Daftar, karena kita harus melintasi seluruh daftar pertama untuk menemukan ekor, dan kemudian menambahkan daftar kedua ini. Jadi, jika dua daftar linear terkait masing-masing panjang n, Menambahkan list memiliki kompleksitas waktu asimtotik dari O (n). Pada keluarga Lisp bahasa, menambahkan daftar ini disediakan oleh append prosedur.
Banyak kasus khusus operasi linked list dapat dihilangkan dengan memasukkan elemen bodoh di depan daftar. Hal ini memastikan bahwa tidak ada kasus khusus untuk awal daftar dan membuat kedua insertBeginning() dan removeBeginning() tidak perlu. Dalam hal ini, data yang berguna pertama dalam daftar akan ditemukan pada list. firstNode .next .
daftar sirkuler terkait
Dalam daftar sirkuler terkait, semua node yang terhubung dalam suatu lingkaran terus menerus, tanpa menggunakan null. Untuk daftar dengan depan dan belakang (seperti antrian), salah satu toko referensi ke node terakhir dalam daftar. Node berikutnya setelah node terakhir adalah node pertama. Elemen dapat ditambahkan ke bagian belakang daftar dan dihapus dari depan dalam waktu yang konstan.
Daftar sirkuler terkait dapat berupa tunggal atau ganda terkait.
Kedua jenis daftar sirkuler terkait manfaat dari kemampuan untuk melintasi awal daftar lengkap pada setiap node yang diberikan. Hal ini sering memungkinkan kita untuk menghindari firstNode menyimpan dan lastNode, meskipun jika daftar mungkin kosong kita perlu representasi khusus untuk daftar kosong, seperti variabel lastNode yang menunjuk ke beberapa node dalam daftar atau null jika itu kosong, kami menggunakan seperti lastNode sini. Representasi ini secara signifikan menyederhanakan menambahkan dan menghapus node dengan daftar yang tidak kosong, tetapi daftar kosong tersebut kemudian kasus khusus.
Algoritma
Dengan asumsi bahwa someNode beberapa node dalam daftar tidak kosong tunggal dihubungkan melingkar, kode ini beriterasi daftar yang dimulai dengan someNode:
  fungsi iterate (someNode)
    jika someNode ≠ nol
      node: = someNode
      melakukan
        melakukan sesuatu dengan node.value
        node: = node.next
      sedangkan simpul ≠ someNode
Perhatikan bahwa tes "sementara simpul ≠ someNode" harus di akhir loop. Jika tes dipindahkan ke awal loop, prosedur akan gagal setiap kali daftar hanya satu node.
Fungsi ini menyisipkan node "newNode" ke dalam linked list melingkar setelah node "" node yang diberikan. Jika "node" adalah null, diasumsikan bahwa daftar kosong.
  fungsi insertAfter (Node node, Node newNode)
      jika node = null
        newNode.next: = newNode
      lain
        newNode.next: = node.next
        node.next: = newNode
Misalkan "L" adalah variabel yang menunjuk ke node terakhir dari suatu linked list melingkar (atau null jika daftar kosong). Untuk menambahkan "newNode" ke akhir daftar, seseorang dapat melakukan
  insertAfter (L, newNode)
  L: = newNode
Untuk menyisipkan "newNode" di awal daftar, seseorang dapat melakukan
  insertAfter (L, newNode)
  jika L = null
    L: = newNode
Linked list menggunakan array dari node
Bahasa yang tidak mendukung semua jenis referensi masih dapat membuat link dengan mengganti pointer dengan indeks array. Pendekatan ini untuk menjaga berbagai dari catatan , di mana setiap record memiliki bidang bilangan bulat yang menunjukkan indeks dari node (dan mungkin sebelumnya) berikutnya dalam array. Tidak semua node dalam array perlu digunakan. Jika catatan juga tidak didukung, array paralel sering dapat digunakan sebagai gantinya.
Sebagai contoh, perhatikan catatan berikut linked list yang menggunakan array bukan pointer:
  catatan Masuk {
     integer berikutnya; / / indeks entri berikutnya dalam array
     bilangan bulat prev; masuk / / sebelumnya (jika ganda-linked)
     string nama;
     nyata keseimbangan;
  }
Dengan membuat sebuah array dari struktur, dan variabel integer untuk menyimpan index dari elemen pertama, linked list dapat dibangun:
 bilangan bulat listHead
 Masuk Records [1000]
Links between elements are formed by placing the array index of the next (or previous) cell into the Next or Prev field within a given element. Sebagai contoh:
Indeks
Berikutnya
Prev
Nama
Saldo
0
1
4
Jones, John
123.45
1
-1
0
Smith, Joseph
234.56
2 (listHead)
4
-1
Adams, Adam
0.00
3


Ignore, Ignatius
999.99
4
0
2
Another, Anita
876.54
5




6




7




In the above example, ListHead would be set to 2, the location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available for any additions to the list. By creating a ListFree integer variable, a free list could be created to keep track of what cells are available. If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries could be stored in the list.
The following code would traverse the list and display names and account balance:
i := listHead
while i ≥ 0 // loop through the list
     print i, Records[i].name, Records[i].balance // print entry
     i := Records[i].next
When faced with a choice, the advantages of this approach include:
  • The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly serialized for storage on disk or transfer over a network.
  • Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.
  • Locality of reference can be improved by keeping the nodes together in memory and by periodically rearranging them, although this can also be done in a general store.
  • Naïve dynamic memory allocators can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.
  • Seizing an entry from a pre-allocated array is faster than using dynamic memory allocation for each node, since dynamic memory allocation typically requires a search for a free memory block of the desired size.
This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. This leads to the following issues:
  • It increase complexity of the implementation.
  • Growing a large array when it is full may be difficult or impossible, whereas finding space for a new linked list node in a large, general memory pool may be easier.
  • Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear ( O (n)) instead of constant time (although it's still an amortized constant).
  • Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.
For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.
Language support
Many programming languages such as Lisp and Scheme have singly linked lists built in. In many functional languages , these lists are constructed from nodes, each called a cons or cons cell . The cons has two fields: the car , a reference to the data for that node, and the cdr , a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.
In languages that support abstract data types or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using references together with records .
Internal and external storage
When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called internal storage , or merely to store a reference to the data, called external storage . Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better locality of reference , and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).
External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. It also makes it easy to place the same data in multiple linked lists. Although with internal storage the same data can be placed in multiple lists by including multiple next references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. It is possible to create additional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data.
In general, if a set of data structures needs to be included in multiple linked lists, external storage is the best approach. If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine.
Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the next (and prev if double linked list) references in the same location. After defining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. The message type field is then used to call the correct routine to process the specific type of message.
Example of internal and external storage
Suppose you wanted to create a linked list of families and their members. Using internal storage, the structure might look like the following:
 record member { // member of a family
     member next;
     string firstName;
     integer age;
  }
 record family { // the family itself
     family next;
     string lastName;
     string address;
     member members // head of list of members of this family
  }
To print a complete list of families and their members using internal storage, we could write:
 aFamily := Families // start at head of families list
 while aFamily ≠ null // loop through list of families
     print information about family
     aMember := aFamily.members // get head of list of this family's members
     while aMember ≠ null // loop through list of members
         print information about member
         aMember := aMember.next
     aFamily := aFamily.next
Using external storage, we would create the following structures:
 record node { // generic link structure
     node next;
     pointer data // generic pointer for data at node
  }
 record member { // structure for family member
     string firstName;
     integer age
  }
 record family { // structure for family
     string lastName;
     string address;
     node members // head of list of members of this family
  }
To print a complete list of families and their members using external storage, we could write:
 famNode := Families // start at head of families list
 while famNode ≠ null // loop through list of families
     aFamily := (family) famNode.data // extract family from node
     print information about family
     memNode := aFamily.members // get list of family members
     while memNode ≠ null // loop through list of members
         aMember := (member)memNode.data // extract member from node
         print information about member
         memNode := memNode.next
     famNode := famNode.next
Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type. This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure ( node ), and this language does not have parametric types.
As long as the number of families that a member can belong to is known at compile time, internal storage works fine. If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary.
Speeding up search
Finding a specific element in a linked list, even if it is sorted, normally requires O( n ) time ( linear search ). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.
In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic , which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.
Another common approach is to " index " a linked list using a more efficient external data structure. For example, one can build a red-black tree or hash table whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).
Random access lists
A random access list is a list with support for fast random access to read or modify any element in the list. [ 6 ] One possible implementation is a skew binary random access list using the skew binary number system , which involves a list of trees with special properties; this allows worst-case constant time head/cons operations, and worst-case logarithmic time random access to an element by index). [ 6 ] Random access lists can be implemented as persistent data structures . [ 6 ]
Random access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations. [ 6 ]
A simple extension to random access lists is the min-list , which provides an additional operation that yields the minimum element in the entire list in constant time (without [ clarification needed ] mutation complexities). [ 6 ]
Related data structures
Both stacks and queues are often implemented using linked lists, and simply restrict the type of operations which are supported.
The skip list is a linked list augmented with layers of pointers for quickly jumping over large numbers of elements, and then descending to the next layer. This process continues down to the bottom layer, which is the actual list.
A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the subtrees below that node.
An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.
A hash table may use linked lists to store the chains of items that hash to the same position in the hash table.
A heap shares some of the ordering properties of a linked list, but is almost always implemented using an array. Instead of references from node to node, the next and previous data indexes are calculated using the current data's index.
A self-organizing list rearranges its nodes based on some heuristic which reduces search times for data retrieval by keeping commonly accessed nodes at the head of the list.
Catatan
1.      ^ The amount of control data required for a dynamic array is usually of the form K+B*n, Di mana Kis a per-array constant, Bis a per-dimension constant, and n is the number of dimensions. Kdan Bare typically on the order of 10 bytes.
Catatan kaki
1.      ^ Gerald Kruse. CS 240 Lecture Notes : Linked Lists Plus: Complexity Trade-offs . Juniata College. Spring 2008.
2.      ^ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
3.      ^ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
4.      ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (Technical Report CS-99-09), Resizable Arrays in Optimal Time and Space , Department of Computer Science, University of Waterloo
5.      ^ Ford, William and Topp, William Data Structures with C++ using STL Second Edition (2002). Prentice-Hall. ISBN 0-13-085850-1 , pp. 466-467
6.      ^ a b c d e C Okasaki, " Purely Functional Random-Access Lists "
Referensi
http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/40px-Text_document_with_red_question_mark.svg.png
Artikel ini berisi daftar referensi , tapi tetap tidak jelas sumber karena memiliki cukup inline citations . Harap membantu memperbaiki artikel ini dengan memperkenalkan citations lebih tepat. (Maret 2012)
Pranala luar
http://upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png
Wikimedia Commons has media related to: Lists

[hide]
Struktur data


Jenis


Abstrak


Array


Linked


Pohon


Grafik


View page ratings
Rate this page
What's this?
Trustworthy
Objective
Complete
Well-written
I am highly knowledgeable about this topic (optional)
Kategori :

Diposkan oleh di Wednesday, May 16, 2012
Label:

0 komentar:

Post a Comment

Subscribe to: Post Comments (Atom)
Copyright © 2014 Dunia Naeta All Right Reserved
Designed by Free Download Blogger Templates
Posts RSS
Comments RSS