Elemen
data yang dihubungkan dengan link pada Linked List disebut Node.
Biasanya didalam suatu linked list, terdapat istilah head dan tail.
- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
- Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list
Ada beberapa macam Linked List, yaitu :
1. Single Linked List2. Double Linked List
Single Linked List
Single Linked List
merupakan suatu linked list yang hanya memiliki satu variabel pointer
saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya
field pada tail menunjuk ke NULL.
contoh codingannya :
struct Mahasiswa{
char nama[25];
int usia;
struct Mahasiswa *next;
}*head,*tail;
Single Linked list: inserted
struct Mahasiswa *node =
(struct Mahasiswa*) malloc(sizeof(struct Mahasiswa));
node->value = x;
node->next = head;
head = node;
Operator -> has the same meaning as:
(*node).value
= x;
(*node).next = head;
Single Linked list: deleted
struct
tnode *curr = head;
•
// if x is in head node
if
( head->value == x ) {
head = head->next;
free(curr);
}
// if x is in tail node
else
if(tail->value == x){
while(curr->next!=tail) curr
= curr->next;
free(tail); tail = curr;
tail->next
= NULL;
}
// if x is not in head node, find the
location
else
{
while ( curr->next->value != x ) curr =
curr->next;
struct tnode *del = curr->next;
curr->next = del->next;
free(del);
}
Double Linked List
Double Linked List
merupakan suatu linked list yang memiliki dua variabel pointer yaitu
pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke
node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
contoh codingannya :
struct Mahasiwa{
char nama[25];
int usia;
struct Mahasiswa *next,*prev;
}*head,*tail;
Double linked list: inserted
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
Single Linked list: deleted
Jika node dihapus pada head
• head
= head->next;
• free(head->prev);
• head->prev = NULL;
Jika node dihapus pada tail
•tail
= tail->prev;
• free(tail->next);
• tail->next = NULL;
Memory Allocation
Dalam C/C++, alokasi memory dapat dilakukan dengan menggunakan malloc , sedangkan untuk dealokasi dapat menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak menghapus isi dari memory tersebut.
contoh penggunaan malloc:
int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));
contoh penggunaan free:
free(curr);
Alokasi suatu memory biasanya dibutuhkan didalam linked list saat akan menambah node/data baru.
