PENGERTIAN LINKED LIST BESERTA JENIS DAN CONTOHNYA PADA C++
PENGERTIAN LINKED LIST BESERTA JENIS DAN CONTOHNYA
Pengertian Linked list :
• Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.
Single Linked List
Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).Pembuatan Single Linked List dapat menggunakan 2 metode:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)
Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.Operasi-Operasi yang ada pada Linked List
Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
Find First
Fungsi ini mencari elemen pertama dari linked list
Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
Skenario
1. Dasar Linked List
Sebelum masuk dalam pembuatan program Linked List, kita akan melihat terlebih dahulu sebagaian dari cara kerja linked list. Yaitu adalah cara masing-masing element terhubung.Langkah-langkah :
- Bukalah C++ IDE yang ada pada komputer anda atau notepad.
- Salinlah kode berikut
#include<iostream>
using namespace std;
struct node {
int data;
node* next;
};
node *head = NULL;
int main(){
node *satu; satu = new node;
node *dua; dua = new node;
node *tiga; tiga = new node;
satu->data = 3;
dua->data = 5;
tiga->data = 7;
satu->next = dua;
dua->next = tiga;
tiga->next = NULL;
head = satu;
node *temp = head;
while( temp!=NULL ){
cout<< temp->data<<" ";
temp = temp->next;
}
cout<<"\n";
return 0;
}
- berikutnya compile dan jalankan program tersebut. Jika program anda benar maka akan memunculkan keluaran seperti gambar dibawah ini.
2. Program Linked List dalam C++
Pada skenario 1 kita sudah melihat bagaimana linked list dapat terhubung satu dengan yang lainnya. Sekarang kita akan mengimplmentasi Linked secara penuh.Langkah pertama bukalah IDE yang ada pada komputer anda atau notepad. Kemudian salinlah kode berikut ini.
#include<iostream>
using namespace std;
struct node {
int data;
node* next;
};
node *head = NULL;
node *tail = NULL;
int Length(struct node* head) {
int count = 0;
struct node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return(count);
}
void add(int data){
node *temp;
temp = new node;
temp->data = data;
if(head == NULL){
head = temp;
tail = temp;
head->next = NULL;
tail->next = NULL;
}else{
tail->next = temp;
temp->next = NULL;
tail = temp;
}
}
void printNode(){
node *temp = head;
while( temp!=NULL ){
cout<< temp->data<<" ";
temp = temp->next;
}
cout<<"\n";
}
int main(){
add(18);
add(17);
add(20);
printNode();
cout<<Length(head);
return 0;
}
