[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

[2018] 1 - Pointer, Array and Introcution to Data Stuctures and Introduction to Linked List - 2101673042 - Kevin Surya Pranata

KEVIN SURYA PRANATA

2101673042

Sebelumnya saya mengucapkan selamat datang ke blog saya, pada postingan kali ini kita akan membahas mengenai Array, Pointer, Data Stucture, dan Linked List

Seperti yang pernah kita semua pelajari di kelas Algo pada semester satu, Array  adalah sekumpulan data yang homogen atau setipe. Berikut contoh-contoh array yang harusnya sudah familiar di kalangan anak IT Binus

in C language :

int score[5] = { 7 , 8 , 9 , 9 , 6 }; // array of int

float GPA[3] = { 3.99 , 4.00 , 2.98 }; // array of float

char name[3][30] = { "Kevin" , "Evania" , "Pranata" };

// array of Character

// array of String [?]

Pada contoh di atas dapat kita temukan bahwa ada kotak [5], [3], dan [3][30] yang kita temukan di atas, seharusnya ini sudah dijelaskan oleh dosen kita di semester satu tapi saya akan mencoba menjelaskan maksud dari kurung-kurung siku tersebut, kurung-kurung siku tersebut ramah dikenal dengan dimensi dalam suatu array, jadi seperti yang kita ketahui dalam bahasa C kita dapat menginisialisasi suatu tipe data pada saat program belum dijalankan, nah oleh karena itu jika kita ingin membuat suatu array dari data type, kita dapat menambah [ ] setelah nama tipe data yang kita tentukan, berikut syntax sederhananya 

int C language :

<Data Type> <Name of Data Type> [total size] ; // don't forget ( ; )

jadi kalian mungkin bertanya bagaimana cara mengakses data dari suatu array itu, dalam C array dapat diakses dengan menggunakan index, index dari setiap array dimulai dari index ke-0 dan pada index terakhir dari setiap array ada NULL. Oleh karena itu dapat disimpulkan array dengan size N memiliki index dari 0 sampai dengan N-1.

Cara mengakses nilai dari suatu array seperti contoh berikut

in C language :

int score[5] = { 7 , 8 , 9 , 9 , 6 };

float GPA[3] = { 3.99 , 4.00 , 2.98 };

char name[3][30] = { "Kevin" , "Evania" , "Pranata" };

int i;

for(i=0;i<5;i++) printf("%i ",score[i]);

puts(""); for(i=0;i<3;i++) printf("%.2f ",GPA[i]);

puts(""); for(i=0;i<3;i++) puts(name[i]);

Perhatikan contoh array di atas, bisa kita ketahui kalau array merupukan sekumpulan data yang sama.

Muncul pertanyaan ketika kita melihat array of character di atas karena jika diperhatikan ada lebih dari satu [] yang ditemukan pada codingan di atas yaitu yang menjadi pertanyaan dosen saya hari ini,

Berapa jumlah maksimal dimensi yang dapat digunakan dalam array ?

Jawabannya adalah 256 (sumber Internet).

Berikut contoh multidimensi array yang lebih kompleks (dari Resources Binusmaya)

•Multi Dimensional Array

•Declaration:

•int arr[4][3][7][10];

•Accessing:

•arr[0][2][2][9]= 2;

•arr[2][1][6][0]= 9;

•arr[3][0][0][6]= 13;

•arr[2][1][3][8]= 10;

      Sekarang kita akan membahas bagaimana cara menginisialisasi suatu array, menginput nilai dalam suatu elemen dan mengubah atau mengisi nilai dari suatu array

Diketahui ada beberapa hal yang dapat kamu lakukan dalam array yaitu

1. Transversal

2. Insertion

3. Searching

4. Deleting

5. Merging

6. Sorting

dan akhirnya selesai tentang Array >,<''

      lanjut kita sekarang membahas tentang pointer, tapi sebelumnya saya minta maaf kalau penjelasan saya mengenai pointer akan sedikit kurang efisien karena saya belum paham sepenuhnya apa itu pointer.

Pointer

Pointer is a data type whose value refers to another value stored 

elsewhere in computer memory using its address.

The two most important operators used with pointer type are:

• &  the address operator

• *   the dereferencing operator

itu materi dari Binusmaya penjelasannya berikut,

pointer itu datatype yang menyimpan isi dari suatu data lain yang disimpan di memori 

komputer dan didapatkan dengan menggunakan alamat dari data tersebut.

Ada 2 operator penting ketika kita menggunakan pointer antara lain:

& adalah alamat datanya

* adalah simbol operator pointer

tadi Bapak Dosen ada memberi pertanyaan, 
Apa perbedaan single pointer dan double pointer? 
Dan berapa jumlah bintang ** maksimal yang dapat digunakan sebagai pointer?

Jumlah bintang maksimal yang dapat digunakan sebagai pointer ada 12.

Sedangkan perbedaanya single dan double pointer adalah, double pointer sepertinya hanya bisa di assign adress dari single pointer dan single pointer hanya bisa di assign adress dari int atau data type biasa.

===============================Pointer SELESAI >,<======================

Kemudian, kita membahas mengenai Data Structure

Data Sturcture adalah suatu kumpulan (urutan) data

Beberapa contoh umum dari data structure meliputi

- Arrays

- Linked list

- Queues

- Stacks

- Binary trees

- Hash tables

Berikut beberapa penjelasannya

Array itu kumpulan dari data yang satu jenis

Size of Array itu ditentukan sebelum suatu program jalankan dan tidak dapat berubah seringin program berjalan (statis)

Linked List itu, sekumpulan data structure yang sangat dinamis dimana dia tidak menggunakan array sebagai penampung dari data itu melainan data itu dapat berubah ubah seringin program berjalan (dinamis)

Queue atau yang biasa kita dengar antrian,

berarti elemen dari tipe data tersebut bersistem FIFO, yang berarti First In First Out

Stacks biasa direpresentasikan sebagai suatu tumpukan, 

maka berarti tiap tipe data yang terakhir masuk juga tipe data yang pertama diakses, maka data yang pertama diinput pada sistem ini akan menjadi data yang terakhir dikaeluarkan dari tumpukan paling bawah, berikut ilustrasinya

dan terakhir penjelasan dari Binary Trees yakni data structure yang diset sebagai kumpulan elemen yang disebut node

setiap node memiliki pointer kiri, pointer kanan, dan isi data dari node tersebut, ilustrasinya sebagai berikut

Data Types is a collection of objects and a set of operations that act on those objects, artinya data type itu kumpulan dari object dan operator dari data tersebut

contohnya

data type int mengandung 

object      : 0 , +1, +2, +3, -1, -2, etc.

operation : +,-,*,/,%, etc

contoh dari data type seperti int, char, float.

Abstract Data Type

adalah data type yang diatur dalam spesifikasi yang sudah diatur oleh user (user-defined). Biasa akrab dikenal dengan struct dalam bahasa C.

========================================================================

========================================================================

Berakhirlah pembahasan mengenai Pointer, Array and Introduction to Data Structures

Sekarang saya akan menjelaskan mengenai Introduction to Linked List versi Bapak Dosesn tamu tadi dan sedikit modifikasi versi saya >,<''

sebelumnya kita tidak bisa minggalkan materi dari Binusmaya yaitu Struct.

Apa itu Struct, adalah suatu tipe data user-defined yang penggunannya dapat menyimpan banyak tipe data lain dalam suatu struct tersebut, sementara sebuah array hanya dapat menyimpan data dari sejenis(data type-nya).

Setelah nama structnya user defined, nama tersebut dapat menjadi array yang mewakili kumpulan tipe data yang berbeda itu

nah saya ingin bertanya terlebih dahulu, jika saya punya suatu struct berikut

struct Data{

 char nama[40];

 int age;

 char gender[10];

 char NIM[15];

}student[20];

Apa yang terjadi jika ternyata saya memiliki siswa sebanyak lebih dari 20 orang (>20) ?

Akan terjadi break pada applikasi karena ditemukan suatu error, error yang disebabkan oleh biasanya saya tahu dengan stack overflow, yaitu array yang kepenuhan. Maka

Linked List merupakan solusi dari masalah ini dimana kita menentukan size dari data yang kita tentukan seiring dengan kebutuhan kita, tanpa harus diset di awal program sebelum dijalankan, makanya Linked List bersifat dinamis dan direkomendasikan untuk optimisasi dari penggunaan memori yang dibutuhkan dari program yang akan kita jalankan.

Linked List adalah data struct yang mengandung urutan dari data yang terekam(simpan) dan setiap rekanan data yang tersimpan mengandung arah atau sudah terarah untuk menuju ke arah urutan berikutnya

Berdasarkan contoh di atas dapat dilihat bahwa setiap node memiliki sebuah nilai integer dan link untuk menuju ke node berikutnya.

Linked list yang mengandung hanya tepat satu link ke node lainnya disebut single linked list

Maka dapat disimpulkan perbedaan dari array vs linked list sebagai berikut

Array

- Kumpulan dari tipe data sejenis 

- Menyimpan data di memori yang dialokasikan secara berurutan

- Bisa random dalam pengaksesan data

Linked List 

- Kumpulan dari node

- Tidak menyimpan node di memori berurutan

- Dapat diakses dengan cara yang sesuai urutan

KEVIN SURYA PRANATA

2101673042