RANGKUMAN DATA STRUCTURE
MARCO 2301894022/CLASS: L301-LEC/CD01-CL
(submit pertama salah link)

Pointer adalah tipe data yang valuenya menunjuk ke value lain yang tersimpan pada memory computer menggunakan addresnya.

Dalam menggunakan pointer wajib menggunakan operator & dan *.

Contoh: 

int *ptr;

Array merupakan koleksi data yang memiliki element yang sama/homogenous. element array disimpan menggunakan index, index mulai dari angka 0.

Contoh: 

int arr[5];

Structure/ Struct adalah user defined data yang dapat menyimpan informasi yang berhubungan walaupun berbeda tipe data. sedangkan array hanya dapat menyimpan entities yang memiliki element /tipe data yang sama.

Contoh: 

Structdata{

int age;

char nama[100]

};

Data Structure merupakan data yang sudah diurutkan pada memory computer ataupun storage disk.

ada beberapa tipe data structure yaitu :

array: kumpulan data dengan element sama.

linked list: kumpulan data dimana element bisa ditambah atau dihapus darimanapun.

queue: First in First out

stack: First in last out

Binary tree: data yang memiliki koleksi element diberi nama node, setiap node memiliki pointer kanan dan kiri.

Singel linked list :

untuk membuat linked list sebelumnya harus define node structure untuk list.

untuk menambah value, kita harus allocate node baru , assign value ke node baru kemudian sambungkan dengan linked list yang sudah ada. 

untuk menghapus value kita harus mencari lokasi node yang ingin dihapus, hapus kemudian sambungkan kembali linked list yang sudah ada.

Algorithm delete:

struct tnode *curr = head;

// if x is in head node
if ( head->value == x ) {
head = head->next;
free(curr);
}
// 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);
}

Circular Linked list :
node terakhir = pointer untuk node pertama, dalam ciricular linked list tidak terdapat value null. circular doubly linked list memiliki perbedaan pada node memiliki 2 pointer.

Doubly Linked list merupakan linked list yang memiliki 2 pointer yaitu pointer head dan pointer tail.
contoh doubly linked list:

struct tnode {
int value;
struct tnode *next;
struct tnode *prev;
};

struct tnode *head = 0;
struct tnode *tail = 0;

Doubly linked list insert , insert pada double linked list sama dengan single linked list ,pertama kita mengalokasi node baru dan memberi value, lalu menyambungkan dengan linked list yang sudah ada.

Algorithm insert dibelakang tail:

struct tnode *node =

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

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

Algorithm insert diposisi tertentu:

struct tnode *a = ??;

struct tnode *b = ??;

//node baru akan berada diantara a dan 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;

Doubly linked list delete, dalam delete harus memenuhi 4 kondisi:

1. Apabila node yang ingin dihapus hanya satu satunya:

Algorithm:

free(head);

head = NULL;

tail = NULL;

2. Apabila node yang ingin dihapus berada pada head:

Algorithm: 

head = head->next;

free(head->prev);

head->prev = NULL;

3. Apabila node yang ingin dihapus berada pada tail:

Algorithm: 

tail = tail->prev;

free(tail->next);

tail->next = NULL;

4.Apabila node tidak berada pada head ataupun tail

Algorithm:

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);

Header linked list merupakan tipe linked list spesial yang mengandung header node di awal list, dalam header linked list header tidak menunjuk pada node pertama teteapi berisi address dari header node.