[2018] 2 - Linked List Implementation I - 2101673042 - Kevin Surya Pranata

SELAMAT DATANG KEMBALI !
Kali ini kita akan memperlajari implementasi dari Linked List (LL)

According to our Learning Outcome, diharapkan setelah mempelajari ini kita dapat menjelaskan konsep dan kegunaannya (LL) dalam pengaplikasiannya dan dapat mengaplikasikan data struct ke dalam aplikasi. Oke mari langsung saja

Sub Topic

Sub topik dari blog kali ini antara lain:

• Single Linked List
• Circular Single Linked List
• Double Linked List
• Circular Doubly Linked List

Single Linked List
Nah, untuk menciptakan suatu(sebuah) list, kita harus mendefine struct node untuk list nya, bingung ya? Jangan bingung, saya akan berusaha menjelaskannya

Berikut contoh jika kita ingin menciptakan suatu list dari tipe data integer

struct tnode{
     int value;
     struct tnode *next; //di mana setiap struct tnode memiliki 
                         //int dan pointer penunjuk ke node        
                         //berikutnya
};
 struct tnode *head = NULL; //karena ini diasumsikan data awalnya
                            //belum ada 
                            //dan list itu punya suatu urutan, 
                            //urutan dari head(kepala) ke tail(ekor)
                            //maka ketika data awal diset head dari 
                            //data = NULL
//head is the pointer to the first element in our linked list

Single Linked  List

nah, ketika kita menciptakan suatu list, tentu kita ingin meng-insert datanya bukan?

Untuk insert a new value, pertama kita harus mengalokasikan memori sebanyak struct node kita punya

Ada 4 cara menginsert new node di linked list

1. Insert dari awal node (head)
2. Insert dari akhir node (tail)
3. Insert di belakang node yang ditentukan
4. Insert di depan node yang ditentukan

Berikut contoh insert node dari awal node (pushHead) 

 

 

 Nah penjelelasannya seperti ini, pertama tama kita mengalokasikan meori untuk node kita

kemudian kita ingin menambah data angka 31(sesuai contoh di atas) kedalam linkedlist yang sudah ada kita punya 10,35,27 (sesuai contoh di atas).

Maka logikanya jika kita ingin menambah data nya di depan linked list yang sudah kita punya maka

(curr) (current) node yang kita punya di linked list kan ke head kita atau

node->next=head;

lalu sekarang node baru kita (curr) dijadikan sebagai head linked list kita 

head=node;

nah seperti itu kira kira insertion di Linked List, jika pushTail bagaimana?

ada tips dan tricknya, jika kamu sudah menguasai pushHead

 maka tinggal membalikkan syntax-nya 

head jadi tail

tail jadi head

berarti  jika misalnya kita ingin menambah data di belakang 27, maka logicnya 

27 itu tail,

tail->next=node;

lalu awalnya kan tail ->next kan NULL maka sekarang

node->next=NULL //dan

tail=node;

kemudian kita akan membahas cara mendelete data di Node

nah logikanya adalah kita akan mencari terlebih dahulu yang akan kita cari setelah dicari,  setelah ditemukan datanya difree(hapus) dan linked list kita punya dihubungkan list nya

Kita asumsikan value yang ingin kita remove adalah x dan x itu datanya berada di linked list

ada 2 kondisi yang harus diperhatikan di single linked list yaitu

1. apakah x berada di head
2. atau apakah tidak berada di head

 berikut contoh syntax-nya

 

 

 kasus di atas merupakan contoh popHead (menghapus data dari head linkedlist)

pertama kita mendeklarasikan struct node curr adalah head

lalu kita geser head yang kita miliki awalnya menjadi node berikutnya

head=head->next;

lalu setelah kita menggeser head nya kita free curr yang kita

free(curr);

 kira kira demikian cara popHead

sekarang kita akan membahas cara pop di tengah data

pertama kita set curr kita dari head karena kita mencari data yang ingin kita cari dari awal data yang kita miliki di mana data yang ingin kita cari (hapus) adalah x

lalu kita looping while sampai data nya ketemu, jika sudah ketemu maka kita deklarasikan lagi struct node pembantu (temp) untuk delete kita 

setelah kita set struct del kita lalu kita hubungkan curr kita ke dell->next 

dan terakhir kita free(del) [yang ingin kita hapus datanya]

Dan terakhir dari Single Linked List adalah Circular Single Linked List

yakni di mana dalam circular, last node memiliki pointer yang menuju ke node awal

lalu berarti di mana tidak ada data yang menyimpan nilai NULL karena tadi tail->next=head

dan berarti jika ada circular single linked list maka akan memungkinkan circular double linked list

 

Double Linked List 

Double Linked List atau disebut juga two-way linked list adalah list data struct yang memiliki 2 link, satu link nya menuju ke data berikutnya dan satu linknya menuju ke data sebelumnya

Insert dalam Doubly Linked List

sama seperti di single linked list, pertama tama kita hendak mengalokasikan node yang ingin kita pakai dan mengassign value ke dalamnya, lalu setelah itu kita mengconnect node itu dengan node yang sudah ada di linked list

misalnya kita ingin menambah node di belakang linked list

struct tnode *node =

  (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

nah sekarang jika kita ingin menambah node di antara head atau tail

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;

 Delete dalam Doubly Linked List juga terbagi ke dalam 4 kondisi

- Jika node yang akan dihapus satu satunya node yang ada di linked list
- Jika node yang akan dihapus adalah head
- Jika node yang akan dihapus adalah tail
- Jika node yang akan dihapus bukan head dan bukan tail

Jika node yang dihapus satu satunya node di linked list caranya
free(head);
head=NULL;
tail=NULL; // atau head=tail=NULL;

Jika node yang akan dihapus adalah head
head=head->next;
free(head->prev);
head->prev=NULL;

Jika node yang akan dihapus adalah tail
tail=tail->prev;
free(tail->next);
tail->next=NULL;

Jika node yang akan dihapus bukan tail dan bukan head
pertama kita memerlukan struct temp (curr)
struct tnode *curr=head;
search node yang ingin dihapus , diasumsikan x adalah data yang dicari(ingin dihapus)
while(curr->next->value!=x) curr=curr->next;
jika data sudah ketemu, deklarasikan node temp a, b dan del di mana
struct tnode *a=curr;
struct tnode *del=curr->next;
struct tnode *b=curr->next->next;
di mana a adalah curr kita
del adalah data yang ingin di free
dan b adalah data yang akan menjadi data setelah a bukan lagi del karena akan di free maa
a->next=b; //dan
b->prev=a; //lalu
free(del);

Circular Doubly Linked List

serupa dengan circular single linked list, tapi total pointer dari setiap node sekarang ada 2(dua) pointerr

head->prev=tail;
tail->next=head;

berikut ilustrasinya

 Header Linked List

Header Linked List adalah header spesial dari linked list yang mengandung header node di awal dari linked list maka start tidak akan menuju ke node pertama melaikan start akan mengandung alamat dari head node

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 coeficients 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.

 Kira kira seperti itu rangkuman pelajaran saya hari ini
Selasa, 27 Februari 2018

terima kasih
Kevin Surya Pranata
2101673042