alah
satu jenis struktur data adalah linked list. Dalam bahasa melayunya, linked
list adalah data yang bersambungan antara satu sama lain. Setiap elemen linked
list dipanggil node. Manakala setiap node terbahagi kepada dua bahagian iaitu
bahagian data yang akan menyimpan data dan bahagian sambungan (link) yang
berfungsi sebagai penyambung elemen-elemen di dalam linked list ini.
Di
dalam bahagian sambungan, biasanya ia terdiri dari hanya satu pembolehubah
pointer yang akan merujuk kepada address (lokasi) node seterusnya. Linked list
ini dipanggil single-linked linked list. Untuk double-linked linked list,
terdapat dua pointer, di mana satu merujuk kepada address node seterusnya dan
satu lagi merujuk kepada address node sebelumnya.
Node
biasanya adalah struktur C untuk menyimpan lebih daripada satu jenis pemboleh
ubah Salah satu contoh
mudah sebuah node adalah:
struct tnode {
int data;
struct tnode *next;
};
Di
mana data merujuk kepada bahagian data dan next merujuk kepada bahagian link.
Jadi dengan ini kita boleh bayangkan yang kita membuat satu linked list dengan
3 node seperti contoh di bawah.
#include
#include
struct tnode {
int data;
struct tnode *next;
};
int main(int argc, char *argv[])
{
struct tnode *node = (struct tnode *)malloc(sizeof(struct tnode));
// menyambung node
node->data = 100;
node->next = (struct tnode *)malloc(sizeof(struct tnode));
printf("Data node1 %d \n", node->data);
printf("Link node1 %p \n", node->next);
printf("Lokasi node1 %p \n\n", node);
node->next->data = 200;
node->next->next = (struct tnode *)malloc(sizeof(struct tnode));
printf("Data node2 %d \n", node->next->data);
printf("Link node2 %p \n", node->next->next);
printf("Lokasi node2 %p \n\n", node->next);
node->next->next->data = 300;
node->next->next->next = NULL;
printf("Data node3 %d \n", node->next->next->data);
printf("Link node3 %p \n", node->next->next->next);
printf("Lokasi node3 %p \n\n", node->next->next);
system("PAUSE");
return 0;
}
Seperti
yang boleh digambarkan seperti di bawah.
Berikut
adalah hasil output kod di atas setelah dijalankan menggunakan Dev-C++.
Jadi
setelah melihat bagaimana linked list berfungsi, mari kita lihat bagaimana
membina satu program linked list yang lengkap. Dalam program linked list, saya
membayangkan beberapa fungsi yang boleh membantu kita memanipulasi linked list
yang dihasilkan.
Membina node baru
Fungsi ini bertujuan untuk memperuntukkan (allocate) ruang memori untuk node baru dan memasukkan data ke dalamnya.
Fungsi ini bertujuan untuk memperuntukkan (allocate) ruang memori untuk node baru dan memasukkan data ke dalamnya.
struct tnode * createnode(int data){
struct tnode * node;
node = (struct tnode *)malloc(sizeof(struct tnode));
node->next = NULL;
node->data = data;
return node;
}
Menambah node
Fungsi ini akan menggunakan fungsi createnode di atas dan kemudiannya memasukkan node tersebut ke dalam linked list yang sedia ada di posisi yang diberi.
Fungsi ini akan menggunakan fungsi createnode di atas dan kemudiannya memasukkan node tersebut ke dalam linked list yang sedia ada di posisi yang diberi.
void tambahnode(int data, int pos)
{
int i;
struct tnode *temp, *prev, *current;
current = head;
if(pos > (length()+1) || pos <= 0){
printf("Posisi tidak sah.\n ");
}
else {
if (pos == 1){
temp = createnode(data);
temp->next = head;
head = temp;
}
else{
for(i=1;inext;
}
temp = createnode(data);
prev->next = temp;
temp->next = current;
}
}
}
Memaparkan data node
Fungsi ini digunakan untuk memaparkan kesemua data yang terkandung di dalam node-node yang ada.
Fungsi ini digunakan untuk memaparkan kesemua data yang terkandung di dalam node-node yang ada.
void paparnode(void){
struct tnode * current = head;
while(current != NULL) {
printf("Data node %d \n", current->data);
printf("Link node %p \n", current->next);
printf("Lokasi node %p \n\n", current);
current = current->next;
}
}
Mengira jumlah node
Fungsi ini bertujuan untuk memberikan jumlah node yang berada di dalam linked list.
Fungsi ini bertujuan untuk memberikan jumlah node yang berada di dalam linked list.
int length(void) {
struct tnode* current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
Membuang node
Fungsi ini bertujuan untuk membuang node di posisi yang ditetapkan.
Fungsi ini bertujuan untuk membuang node di posisi yang ditetapkan.
void deletenode(int pos){
struct tnode * current = head;
struct tnode * prev;
int i;
if(pos > (length()) || pos <= 0){
printf("Posisi tidak sah.\n");
}
else {
if(pos == 1){
head = current->next;
free(current);
}
else{
for(i=1; inext;
}
prev->next = current->next;
free(current);
}
}
}
Jika
kita gabungkan kesemua fungsi-fungsi di atas, kita sudahpun mempunyai satu
program linked list yang lengkap.
#include
#include
struct tnode {
int data;
struct tnode *next;
} *head;
struct tnode * createnode(int data){
struct tnode * node;
node = (struct tnode *)malloc(sizeof(struct tnode));
node->next = NULL;
node->data = data;
return node;
}
void tambahnode(int data, int pos)
{
int i;
struct tnode *temp, *prev, *current;
current = head;
if(pos > (length()+1) || pos <= 0){
printf("Posisi tidak sah.\n ");
}
else {
if (pos == 1){
temp = createnode(data);
temp->next = head;
head = temp;
}
else{
for(i=1;inext;
}
temp = createnode(data);
prev->next = temp;
temp->next = current;
}
}
}
void paparnode(void){
struct tnode * current = head;
printf("*****************************\n");
while(current != NULL) {
printf("Data node %d \n", current->data);
printf("Link node %p \n", current->next);
printf("Lokasi node %p \n\n", current);
current = current->next;
}
}
int length(void) {
struct tnode* current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
void deletenode(int pos){
struct tnode * current = head;
struct tnode * prev;
int i;
if(pos > (length()) || pos <= 0){
printf("Posisi tidak sah.\n");
}
else {
if(pos == 1){
head = current->next;
free(current);
}
else{
for(i=1; inext;
}
prev->next = current->next;
free(current);
}
}
}
int main(int argc, char *argv[])
{
head = NULL;
tambahnode(100, 1);
tambahnode(200, 1);
tambahnode(300, 1);
tambahnode(400, length() + 1);
paparnode();
deletenode(3);
paparnode();
system("PAUSE");
return 0;
}
