linked list pertemuan III

Materi Pertemuan 3 mar 2020

Review Materi minggu lalu + contoh coding in c
Hal yang akan di bahas :
1.Circular Single Linked List
2.Doubly Linked List
3.Circular Double Linked List

1.Circular Single Linked List

Dalam linked list ini , tidak ada ada "last node" ,jika sudah sampai ke node terakhir , akan berisikan pointer node pertama , sehingga tidak ada node yang berisikan NULL value. Semua node dalam Circular Single Linked List dapat menjadi starting point.
contoh coding single linked list insert adn pop
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

struct emp{
 int age;
 char name[100];
 struct emp *next;
}*head = NULL, *tail = NULL;


/*LL operation:
1. Insert
2. Pop / Delete
3. Search
*/
void insertBack(int age, const char *name){
 struct emp *curr =
   (struct emp *)malloc(sizeof(struct emp));
 curr->age = age;
 strcpy(curr->name, name);
 curr->next = NULL;
 if(head == NULL){
  head = tail = curr;
 }else{
  tail->next = curr;
  tail = curr;
 }
}

void insertFront(int age, const char *name){
 struct emp *curr =
   (struct emp *)malloc(sizeof(struct emp));
 curr->age = age;
 strcpy(curr->name, name);
 curr->next = NULL;
 if(head == NULL){
  head = tail = curr;
 }else{
  curr->next = head;
  head = curr;
 }
}

void viewLL(){
 struct emp *curr = head;
 while(curr != NULL){
  printf("%2d : %-20s\n", curr->age, curr->name);
  curr = curr->next;
 }
 printf("\n");
}

void popFront(){ //QUEUE, Head will be removed first
 struct emp *curr = head;
 if(curr == tail){
  free(curr);
  head = tail = NULL;
 }else if(curr){ //curr != NULL
  head = head->next;
  free(curr);
 }
}

void popBack(){ //STACK, Tail will be removed first
 struct emp *curr = head;
 if(curr == tail){
  free(curr);
  head = tail = NULL;
 }else if(curr){
  while(curr->next != tail && curr){
   curr = curr->next;
  }
  free(tail);
  tail = curr;
  tail->next = NULL;
 }
}

int main(){

 insertBack(27, "Hanry Ham");
 insertBack(33, "Derwin Suhartono");
 insertBack(30, "Novita Hanafiah");
 insertBack(26, "Reinert Y Rumagit");
 insertBack(27, "Yohan Muliono");
 viewLL();

 popFront();
 popFront();
 viewLL();

 popBack();
 popBack();
 popBack();
 viewLL();

 return 0;
}

2.Doubly Linked List

Di dalam Doubly Linked List,setiap node memiliki 2 link , 1 untuk menuju ke node selanjutnya , 1 nya lagi untuk menuju ke node sebelumnya.

seperti kita lihat di gambar , jika single linked list memiliki 1 kotak , sedangkan doubly linked list memiliki 2 kotak berisi next dan previous.


2.1 Doubly Linked List Insertion

Push merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert depan dan insert dari belakang. Insert dari depan akan memasukan data paling baru ke depan data sebelumnya , jika insert dari belakang berarti akan menempatkan data paling baru ke belakang data sebelumnya . Contoh : 

 1. Insert dari depan : 1 ,2 ,3 ,4 maka hasilnya akan mejadi 4,3,2,1

 2. Inser dari belakang : 1,2,3,4 maka hasilnya akan 1,2,3,4

2.2 Doubly Linked List Deletion
Pop merupakan operasi delete diaman ada 2 cara yaitu pop dari depan , berarti akan mengahapus data yang paling depan , sedangkan pop belakang akan menghapus data dari paling belakang.

Operasi pop dari depan

Operasi pop dari belakaang

contoh coding double linked list pop and insert

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct emp{
 int age;
 char name[100];
 struct emp *next;
 struct emp *prev;
}*head = NULL, *tail = NULL;

void insertBack(int age, const char *name){
 struct emp *curr = (struct emp*)
      malloc(sizeof(struct emp));
 curr->age = age;
 strcpy(curr->name, name);
 curr->next = NULL;
 if(head == NULL){
  head = tail = curr;
  head->prev = NULL;
 }else{
  tail->next = curr;
  curr->prev = tail;
  tail = curr;
 }
}

void insertFront(int age, const char *name){
 struct emp *curr = (struct emp*)
      malloc(sizeof(struct emp));
 curr->age = age;
 strcpy(curr->name, name);
 curr->next = NULL;
 if(head == NULL){
  head = tail = curr;
  head->prev = NULL;
 }else{
  curr->next = head;
  head->prev = curr;
  head = curr;
 }
}

void popBack(){
 struct emp *curr = tail;
 if(curr){
  tail = tail->prev;
  free(curr);
  tail->next = NULL;
 }
}

void popFront(){
 struct emp *curr = head;
 if(curr){
  head = head->next;
  free(curr);
  head->prev = NULL;
 }
}

void viewLL(){
 struct emp *curr = head;
 while(curr != NULL){
  printf("%2d : %-20s\n", curr->age, curr->name);
  curr = curr->next;
 }
 printf("\n");
}

int main(){
 insertBack(27, "Hanry Ham");
 insertBack(33, "Derwin Suhartono");
 insertBack(30, "Novita Hanafiah");
 insertBack(26, "Reinert Y Rumagit");
 insertBack(27, "Yohan Muliono");
 viewLL();

 head = tail = NULL;
 insertFront(27, "Hanry Ham");
 insertFront(33, "Derwin Suhartono");
 insertFront(30, "Novita Hanafiah");
 insertFront(26, "Reinert Y Rumagit");
 insertFront(27, "Yohan Muliono");
 viewLL();

 return 0;
}
3.Circular Doubly Linked List
 Circular Doubly Linked List hampir sama seperti CIrcular Single Linked List , akan tetapi setiap node memiliki 2 pointer yaitu next dan previous.

Nama ; Joviandy Widyananda
NIM ; 2301846225
Kelas ; CB01/LK01