Deretan data dapat disimpan dalam bentuk array. Hal ini mustahil dilakukan jika data tersebar acak (noncontiguous) dalam memori. Array dapat menyimpan data berderet dalam ukuran dan jumlah yang tetap. Jika ingin menyimpan data dalam jumlah yang bervariasi, sebuah array harus disiapkan dengan menyediakn ruang kosong untuk menampung hingga beberapa jumlah elemen.
Apabila jumlah elemen yang akan disimpan dalam deretan tersebut tidak bisa diramalkan, tentu ini akan menjadi masalah. Misalnya array kosong yang disediakan sebanyak 10, namun ternyata sistem harus menyimpan 20 elemen. Saat ini terjadi, sistem bisa mengalokasikan deretan array kosong lagi. Kebalikannya, jika array kosong ada 10, namun sistem hanya perlu menambahkan 2 elemen, ini tak akan menjadi masalah besar. Namun, bagaimanapun manajemen memori harus dilakukan sebaik-baiknya.
Daripada menyimpan elemen dalam linked list, sistem lebih baik mengalokasikan memori cukup sebesar ukuran elemen yang perlu disimpan. Lokasi memori hasil alokasi tentu akan acak (noncontiguous), sehingga setiap elemen perlu dilengkapi dengan pointer untuk menunjukkan dimana alamat memori lokasi elemen sebelumnya dan sesuadahnya disimpan.
Setiap elemen/node dalam list akan selalu memiliki 2 pointer untuk menunjukkan lokasi elemen sebelum dan sesudahnya; belakang dan depannya; atau sebelah kiri dan kanannya. Oleh karena itu, setiap elemen akan diwakili oleh sebuah DLIST_NODE yang memiliki field pointer untuk menunjukkan lokasi elemen lainnya.
typedef struct _DLIST_NODE{
struct _DLIST_NODE *next;
struct _DLIST_NODE *prev;
int data;
} DLIST_NODE;
Untuk memudahkan pencarian, sebuah data struktur diperlukan sebagai parameter pengelompok deretan elemen. Kita akan menyebutnya sebagai DLIST.
typedef struct _DLIST {
DLIST_NODE *first;
DLIST_NODE *last;
} DLIST;
Field first akan selalu menujuk pada elemen pertama dalam sebuah list, dan field last menunjuk pada elemen paling terakhir. Saat tidak ada satupun data tersimpan dalam list, kedua field ini harus bernilai 0. Ketika satu buah elemen pertama dimasukkan, kedua field ini akan menunjuk ke satu elemen yang sama, yaitu elemen baru itu sendiri –elemen pertama dan terakhir–.
Menambahkan data ke list
Elemen dapat dimasukkan dalam beberapa metode, antara lain adalah sebagai berikut.
- tambahkan di posisi paling awal (prepend)
- tambahkan di posisi paling akhir (append)
- sisipkan sebelum salah satu elemen (insert before)
- sisipkan sesudah salah satu elemen (insert after)
Prepend
Proses prepend harus diawali dengan memeriksa apakah ada elemen dalam kelompok DLIST. Apabila kita menemukan DLIST→first bernilai 0, elemen baru harus diperlakukan sebagai node pertama sekaligus terakhir. Sehingga first dan last pada DLIST akan menunjuk ke elemen baru. Lalu field prev dan next dari elemen baru harus diset 0 untuk menunjukkan bahwa tidak ada element lain.
elemen pertama = elemen terakhir = elemen baru
elemen baru→sebelumnya = 0
elemen baru→sesudahnya = 0
Namun, jika ditemukan satu atau lebih elemen dalam grup DLIST, yaitu ketika terindikasi DLIST→first ≠ 0; elemen baru harus dikaitkan dengan benar. Elemen pertama diubah menjadi elemen sesudahnya (elemen kedua), lalu elemen baru diubah peranannya sebagai elemen pertama dalam grup DLIST.
elemen baru→sebelumnya = 0
elemen baru→sesudahnya = elemen pertama
elemen pertama→sebelumnya = elemen baru
elemen pertama = elemen baru
HINT : Gambarlah elemen-elemen yang mengalami perubahan dalam secarik kertas untuk memudahkan visualisasi.
Kode:
void DListPrepend(DLIST *list,DLIST_NODE *newNode){
if(!list->first){
list->first = list->last = newNode;
newNode->prev = newNode->next = 0;
}
else{
newNode->prev = 0;
newNode->next = list->first;
list->first->prev = newNode;
list->first = newNode;
}
}
Append
Tidak berbeda jauh dengan prepend, append juga harus memeriksa apakah grup DLIST sudah memiliki elemen. Hal ini dilakukan untuk menentukan apakah elemen baru harus diperlakukan sebagai elemen pertama dan terakhir. Jika bukan:
elemen baru→sesudahnya = 0
elemen baru→sebelumnya = elemen terakhir
elemen terakhir→sesudahnya = elemen baru
elemen terakhir = elemen baru
Kode:
void DListAppend(DLIST *list,DLIST_NODE *newNode){
if(!list->last){
list->last = newNode;
list->first = newNode;
newNode->prev = 0;
newNode->next = 0;
}
else {
newNode->next = 0;
newNode->prev = list->last;
list->last->next = newNode;
list->last = newNode;
}
}
Insert before
Sebelum menyisipkan elemen ke posisi sebelum elemen target, perlu dipastikan apakah elemen target itu ada. Jika tidak, mungkin lebih baik kita menempatkan elemen baru ke posisi awal (prepend).
Jika tidak, lakukan prosedur berikut.
elemen baru→sesudahnya = elemen target
Jika elemen target = elemen pertama:
elemen pertama = elemen baru
Jika bukan:
elemen baru→sebelumnya = elemen target→sebelumnya
elemen target→sebelumnya→sesudahnya = elemen baru
elemen target→sebelumnya = elemen baru
Kode:
void DListInsertBefore(DLIST *list,DLIST_NODE *node,DLIST_NODE *newNode){
if(!node) //nothing? prepend!
{
if(!list->first){
list->first = newNode;
list->last = newNode;
newNode->prev = 0;
newNode->next = 0;
}
else{
newNode->prev = 0;
newNode->next = list->first;
list->first->prev = newNode;
list->first = newNode;
}
return;
}
newNode->next = node;
if(!node->prev){
list->first = newNode;
}
else {
newNode->prev = node->prev;
node->prev->next = newNode;
node->prev = newNode;
}
}
Insert after
Tidak perlu dijelaskan detail. Prosedur ini murni kebalikan dari prosedur insert before. Jika anda sudah paham prosedur tersebut, tentu sangat mudah membaca kode implementasi di bawah ini.
Kode:
void DListInsertAfter(DLIST *list,DLIST_NODE *node,DLIST_NODE *newNode){
if(!node){ //nothing? append!
if(!list->last){
list->last = newNode;
list->first = newNode;
newNode->prev = 0;
newNode->next = 0;
}
else {
newNode->next = 0;
newNode->prev = list->last;
list->last->next = newNode;
list->last = newNode;
}
return;
}
newNode->prev = node;
if(!node->next){
list->last = newNode;
}
else {
newNode->next = node->next;
node->next->prev = newNode;
node->next = newNode;
}
}
Menghapus elemen dari list
Dalam kasus ini, elemen perlu diperiksa apakah ia berperan sebagai elemen pertama. Jika demikian, elemen pertama akan digantikan perannya oleh elemen sesudahnya. Apabila kondisi ini tidak ditemukan, field next dari “elemen sebelum elemen target” harus diarahkan ke “elemen sesudah elemen target”.
Kemudian, elemen target juga dipastikan peranannya sebagai elemen terakhir atau bukan. Jika elemen terakhir, peranan elemen terakhir dgantikan dengan elemen sebelum elemen target. Atau, jika tidak, field prev dari “elemen sesudah elemen target” harus diarahkan pada “elemen sebelum elemen target”.
Untuk menghindari human error saat penggunaan linked list; terakhir, elemen yang baru dilepas sebaiknya dihapus referensi prev dan next nya.
Jika elemen target = elemen pertama:
elemen pertama = elemen target→sesudahnya
Bukan:
elemen target→sebelumnya→sesudahnya = elemen target→sesudahnya
Jika elemen target = elemen terakhir:
elemen terakhir = elemen target→sebelumnya
Bukan:
elemen target→sesudahnya→sebelumnya = elemen target→sebelumnya
elemen target→sebelumnya = elemen target→sesudahnya = 0
Kode:
void DListUnlink(DLIST *list,DLIST_NODE *node){
if(!node->prev)
list->first = node->next;
else
node->prev->next = node->next;
if(!node->next){
list->last = node->prev;
}
else
node->next->prev = node->prev;
}
Contoh Penggunaan
Dari beberapa fungsi yang telah ditampilkan di atas, kita belum dapat melihat bagaimana keseluruhan fungsi tersebut dengan baik, sebelum mempraktekkannya sendiri. Oleh karena itu, berikut saya sertakan code snippet sederhana :
void DListDump(DLIST *list){
DLIST_NODE *node = list->first;
while(node){
printf("node at %x data: %i prev: %x next: %x\n",node,node->data,node->prev,node->next);
node = node->next;
}
}
DLIST dlist = {0,0};
int main(){
char action;
DLIST_NODE *node;
DLIST_NODE *node_addr;
int node_data;
first:
printf("[a]ppend [p]repend Insert a[f]ter Insert [b]efore [d]ump [r]emove [q]uit:");
scanf("\n%c",&action);
switch (action){
case 'd':
DListDump(&dlist);
break;
case 'a':
node = malloc(sizeof(DLIST_NODE));
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListAppend(&dlist,node);
break;
case 'p':
node = malloc(sizeof(DLIST_NODE));
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListPrepend(&dlist,node);
break;
case 'f':
node = malloc(sizeof(DLIST_NODE));
printf("Node addr (hex):");
scanf("\n%x",&node_addr);
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListInsertAfter(&dlist,node_addr,node);
break;
case 'b':
node = malloc(sizeof(DLIST_NODE));
printf("Node addr (hex):");
scanf("\n%x",&node_addr);
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListInsertBefore(&dlist,node_addr,node);
break;
case 'r':
node = malloc(sizeof(DLIST_NODE));
printf("Node addr (hex):");
scanf("\n%x",&node_addr);
DListUnlink(&dlist,node_addr);
free(node_addr);
break;
case 'q':
goto last;
break;
default:
printf("Invalid option\n");
goto first;
break;
}
goto first;
last:
return 0;
}
Bagaimana hasilnya?
Wow, cool...
0 comments