2 - Linked List Implementation I - 2101667405 - Evania Joycelin Anthony
1. Single Linked List
Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.
- Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.
- Di dalam sebuah linked list, ada 1 pointer yang menjadi gambaran besar, yakni pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri.
- Setiap link membawa field data dan field link yang disebut next.
- Setiap link dihubungkan dengan link berikutnya menggunakan next link tersebut.
- Link terakhir berisi NULL sebagai penanda bahwa itu adalah yang terakhir.
- Tipe datanya harus sama
- Arah dari single linked list adalah satu arah saja
Untuk membuat sebuah list kita harus menetapkan sebuah struktur node untuk list tersebut. Misal kita mau membuat sebuah list integers.
struct tnode {
int
value;
struct
tnode *next;
};
struct tnode *head = NULL; (head di sini adalah pointer untuk ke pergi ke element pertama dari list kita)
Bagaimana Cara Memasukan Node Baru ke Linked List Kita?
Ada 4 kasus untuk memasukan data:
- Node baru dimasukkan di awal
- Node baru dimasukkan di akhir
- Node baru dimasukkan setelah node yang diinginkan
- Node baru dimasukkan sebelum node yang diinginkan
1. Inserting a node at the beginning of a linked list
Misal kita mau memasukkan sebuah node baru yaitu angka 9 dan menjadikannya sebagai node pertama dari list.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num=9;
new_node = (struct node *) malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = start;
start = new_node;
return start;
}
2. Inserting a node at the end of linked list
Misal kita mau memasukkan sebuah node baru yaitu angka 9 dan menjadikannya sebagai node terakhir dari list.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *insert_end(struct node *start)
{
struct node *ptr, *new_node;
int num=9;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = NULL;
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
return start;
}
3. Inserting a node after the given node in a linked list
Misal kita mau memasukkan sebuah node baru yaitu angka 9 dan menjadikannya dibelakang node yang sudah kita pilih.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr, *preptr;
int num=9, val=3;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
preptr = ptr;
while(preptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next=new_node;
new_node -> next = ptr;
return start;
}
4. Inserting A Node Before the given node in a linked list
Misal kita mau memasukkan sebuah node baru yaitu angka 9 dan menjadikannya di depan node yang sudah kita pilih.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr, *preptr;
int num=9, val=3;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = new_node;
new_node -> next = ptr;
return start;
}
Bagaimana cara menghapus node dari linked list kita?
Ada 4 kasus untuk menghapus data:
struct node *delete_end(struct node *start)
{
struct node *ptr, *preptr;
ptr = start;
while(ptr -> next != NULL)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
return start;
}
- Menghapus Node di awal
- Menghapus Node di akhir
- Menghapus Node setelah node yang diinginkan
1. Menghapus Node di awal
Misal kita mau menghapus data yang berisi angka 1, dimana data tersebut terletak di depan.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *delete_beg(struct node *start)
{
struct node *ptr;
ptr = start;
start = start -> next;
free(ptr);
return start;
}
2. Menghapus node di akhir
Misal kita mau menghapus data di data terakhir yaitu 5
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *delete_end(struct node *start)
{
struct node *ptr, *preptr;
ptr = start;
while(ptr -> next != NULL)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
return start;
}
3. Menghapus node setelah node yang diinginkan
Misal kita mau menghapus data dimana data tersebut berisi angka 2, dan data tersebut terletak di depan angka 4.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *delete_after(struct node *start)
{
struct node *ptr, *preptr;
int val=4;
ptr = start;
preptr = ptr;
while(preptr -> data != val)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next=ptr -> next;
free(ptr);
return start;
}
2. Circular Single Linked List
- Di suatu Circular Linked List, node terakhirnya memiliki pointer untuk terhubung ke node pertama/head/first
- Di Curcular Linked List kita dapat memulai dari node manapun dan melalui arah manapun (forward/backward)
- Tidak ada nilai NULL di akhiran nodes manapun
Bagaimana Cara Memasukan Node Baru ke Circular Single Linked List?
Ada 2 cara untuk memasukan data baru ke circular single linked list:
- Dimasukkan di awal
- Dimasukkan di akhir
1. Dimasukkan di awal
Misal kita mau memasukkan angka 9 dan menjadikannya sebagai node awalan/start/head/first
Step 1: Kita harus mengalokasikan memori untuk node yang baru
Step 2: Tetapkan data yang mau dicari dengan varabel VAL dan NEXT diinisialisasikan dengan alamat dari node pertama yang disimpan di varabel START
Step 3: Setelah node baru ditambahkan maka ia menjadi node pertama dari list yang kita sebut sebagai START. Variabel pointer START sekarang akan mempunyai alamat dari node yang baru
Step 4: Ketika memasukan node baru di circular single linked list kita harus menggunakan while looping untuk mencapai node paling terakhir. Karena node terakhir mengandung pointer menuju START maka NEXT nya dari node terakhir diperbaharui dan menuju ke node baru yang disebut juga dengan START.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *insert_beg(struct node *start)
{
struct node *new_node, *ptr;
int num;
new_node = (struct node *)malloc(sizeof(struct node)); new_node -> data = num;
ptr = start;
while(ptr -> next != start)
ptr = ptr -> next; ptr -> next = new_node;
new_node -> next = start; start = new_node; return start;
}
2. Dimasukkan di akhir
Misal kita mau memasukkan angka 9 dan menjadikannya sebagai node terakhir.
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *insert_end(struct node *start)
{
struct node *ptr, *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node)); new_node -> data = num;
ptr = start;
while(ptr -> next != start)
ptr = ptr -> next; ptr -> next = new_node;
new_node -> next = start; return start;
}
Bagaimana Cara Menghapus Node Di Circular Single Linked List?
Ada 2 cara untuk memasukan data baru ke circular single linked list:
- Hapus node di awal
- Hapus node di akhir
1. Hapus di Awal
Misal kita mau menhapus node pertama/head/start yang berisi integer 1
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *delete_beg(struct node *start)
{
struct node *ptr;
ptr = start;
while(ptr -> next != start) ptr = ptr -> next; ptr -> next = start -> next;
free(start);
start = ptr -> next; return start;
}
2. Hapus di akhir
Misal kita mau menghapus node terakhir dari list yang mempunyai nilai integer 5
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *delete_end(struct node *start)
{
struct node *ptr, *preptr; ptr = start;
while(ptr -> next != start)
{
preptr = ptr; ptr = ptr -> next;
}
preptr -> next = ptr -> next; free(ptr);
return start;
}
2. Doubly Linked List
Sebuah doubly linked list atau 2 arah linked lisr adalah linked list complex yang mengandung pointer untuk selanjutnya dan untuk sebelumnya dari barisan tersebut. Doubly linked list mengandung 3 bagian yaitu data, pointer menuju selanjutnya dan pointer menuju sebelumnya.
DI C structure dari doubly linked list dapat ditulis seperti ini,
struct node {
PREV field dari node pertama dan the NEXT field dari node terakhir akan bernilai NULL. PREV field digunakan untuk menyimpan alamat dari node yang di depannya yang mana digunakan untuk menjalankan link dari arah yang berlawanan.
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num=9;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
start -> prev = new_node;
new_node -> next = start;
new_node -> prev = NULL;
start = new_node;
return start;
}
struct node {
struct node *prev;
int data;
struct node *next;
};
PREV field dari node pertama dan the NEXT field dari node terakhir akan bernilai NULL. PREV field digunakan untuk menyimpan alamat dari node yang di depannya yang mana digunakan untuk menjalankan link dari arah yang berlawanan.
Bagaimana Cara Memasukan Node Baru ke Doubly Linked List?
Ada 2 cara untuk memasukan node baru ke doubly linked list:
- Node baru dimasukkan di awal
- Node baru dimasukkan di akhir
- Node baru dimasukkan setelah node yang diinginkan
- Node baru dimasukkan sebelum node yang diinginkan
1. Dimasukkan di awal
Misal kita mau memasukan node baru yang bernilai 9 di awal linked lis
{
struct node *new_node;
int num=9;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
start -> prev = new_node;
new_node -> next = start;
new_node -> prev = NULL;
start = new_node;
return start;
}
2. Dimasukkan di akhir
Misal kita mau memasukan node baru yang bernilai 9 di akhir linked list kita
struct node *insert_end(struct node *start)
{
struct node *ptr, *new_node;
int num=9;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr=start;
while(ptr -> next != NULL)
ptr = ptr -> next; ptr -> next = new_node;
new_node -> prev = ptr;
new_node -> next = NULL;
return start;
}
3. Dimasukkan setelah node yang diinginkan
Misal kita mau memasukkan suatu node yang bernilai 9 setelah node yang bernilai 3
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr;
int num=9, val=3;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> prev = ptr;
new_node -> next = ptr -> next;
ptr -> next -> prev = new_node;
ptr -> next = new_node;
return start;
}
4. Dimasukkan sebelum node yang diinginkan
Misal kita mau memasukan node baru yang bernilai 9 sebelum node yang bernilai 3
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr;
int num=9, val=3;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> next = ptr;
new_node -> prev = ptr-> prev;
ptr -> prev -> next = new_node;
ptr -> prev = new_node; r
return start;
}
Bagaimana Cara Menghapus Node dari Doubly Linked List?
Ada 2 cara untuk menghapus node dari doubly linked list:
- Hapus node di awal
- Hapus node di akhir
- Hapus node setelah node yang diinginkan
- Hapus node sebelum node yang diinginkan
1. Hapus node di awal
Misal kita mau menghapus node pertama yang bernilai 1
struct node *delete_beg(struct node *start)
{
struct node *ptr; ptr = start;
start = start -> next;
start -> prev = NULL;
free(ptr);
return start;
}
2. Hapus node di akhir
Misal kita mau menghapus node terakhir yang bernilai 9
struct node *delete_end(struct node *start)
{
struct node *ptr;
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next; ptr -> prev -> next = NULL;
free(ptr);
return start;
}
3. Hapus node setelah node yang diinginkan
Misal kita mau menghapus node yang bernilai 7 setelah node yang bernilai 4
struct node *delete_after(struct node *start)
{
struct node *ptr, *temp;
int val=4;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
return start;
}
4. Hapus node sebelum node yang diinginkan
Misal kita mau menghapus node yang bernilai 3 sebelum node yang bernilai 4
struct node *delete_before(struct node *start)
{
struct node *ptr, *temp;
int val=4;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next; temp = ptr -> prev;
if(temp == start)
start = delete_beg(start);
else {
ptr -> prev = temp -> prev; temp -> prev -> next = ptr;
}
free(temp);
return start;
}
4. Circular Doubly Linked List
Serupa dengan circular single linked list tapi total pointer dari setiap node sekarang ada 2 pointer
5. Header Linked List
Header linked list adalah tipe spesial dari linked list yang mengandung header node di awal dari linked list
maka start tidak akan menuju ke node pertama melainkan start akan mengandung alamat dari header node
6. Implementasi Linked List dalam Polinomial
Consider a polynomial
6x3 + 9x2 + 7x + 1. Every individual term in a polynomial consists of two parts, a coef cient
and a power. Here, 6, 9, 7, and 1 are the coef cients of the terms that have 3, 2, 1, and 0 as their
powers respectively.
Every term of a polynomial can be represented as a node of the linked list.
Every term of a polynomial can be represented as a node of the linked list.
Referensi:
Reema Thareja,. 2014. Data
structures using C. OXFORD. New Delhi. ISBN:978-0-19-809930 Chapter 6
Komentar
Posting Komentar