Array:
1. Disimpan di memori statis.
2. Penggunaan memori kurang efisien, karena melebihi kapasitas array dideklerasi terlebih dahulu sebelum tau jumlah atau kapasitas yang dibutuhkan.
Linked List:
1. Disimpan di memori dinamis.
2. Lebih efisien, karena jika ingin menambahkan data, kita dapat langsung mengalokasikannya, jadi semua memori pasti digunakan.
Untuk menggunakan linked list, kita harus melakukan memory allocation atau alokasi memori terlebih dahulu. Berikut cara deklarasi suatu linked list:
int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
*px = 205;
*pc = ‘A’;
printf( “%d %c\n”, *px, *pc );
free(px);
free(pc);
Jenis-Jenis Linked list:
- Single linked list
Contoh:
struct
tnode
{
int value;
struct tnode *next;
};
•
struct
tnode *head = 0;
head nerupakan pointer menuju ke elemen pertama dari linked list kita. Untuk memasukan nilai baru kita pertama-tama harus mengalokasikan node baru dan memberi nilai ke node baru tersebut, baru disambungkan dengan linked list yang ada. contoh jika kita ingin membuat node baru di depan head :
struct
tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value
= x;
node->next = head;
head
= node;
Untuk menghapus data dalam linked list, pertama-tama kita
harus mengetahui lokasi node dimana data yang akan dihapus berada, lalu menghapus
dan menghilangkan data tersebut, lalu merangkai kembali linked list tersebut.
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);
}
Dalam menghapus data dalam linked list ada 2 hal yang perlu diperhatikan, apakah data yang ingin di hapus ada di head node atau tidak.
 |
| jika ingin menghapus 31 di head |
 |
| jika ingin menghapus 35 tidak di head node |
- Circular single linked list
- Doubly linked list
contoh :
struct
tnode {
int value;
struct tnode *next;
struct tnode *prev;
};
•
struct
tnode *head = 0;
struct
tnode *tail = 0;
struct
tnode *a = ??;
struct
tnode *b = ??;
// the
new node will be inserted between a and b
struct
tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = b;
node->prev = a;
a->next = node;
b->prev = node;
Sedangkan untuk menghapus data, ada 4 cara dengan syarat :
1.jika node yang di hapuskan hanya ada satui:
–free(head);
–head
= NULL;
–tail
= NULL;
2.jika node yang ingin di hapus adalah head
head
= head->next
free(head->prev);
head->prev = NULL;
3.If
the node to be deleted is tail:
- tail = tail->prev;
free(tail->next);
tail->next
= NULL;
4.jika node yang ingin di hapus bukan
head atau tail:
struct
tnode *curr = head;
while ( curr->next->value != x ) curr =
curr->next;
struct tnode *a = curr;
struct tnode *del = curr->next;
struct tnode *b = curr->next->next;
a->next = b;
b->prev = a;
free(del);
- Circular Doubly Linked list
Nama : Benedick Asdyo
NIM : 2101631090
