Pertemuan 2 - Linked List Implementation I

Linked List Implementation I

STRUCTURE

ü  Struktur pada dasarnya adalah tipe data yang ditentukan pengguna yang dapat menyimpan informasi terkait (bahkan dari tipe data yang berbeda) bersama-sama, sementara array hanya dapat menyimpan dari tipe data yang sama.

ü  Ini adalah kumpulan variabel dengan satu nama.

ü  variabel dalam struktur adalah tipe data yang berbeda dan masing-masing memiliki nama yang digunakan.

LINK LIST

ü  Linear collection dari elemen data yang disebut nodes

ü  Lebih efisien dalam penggunaan memori

SINGLE LINKED LIST

ü  Single linked list adalah yang paling sederhana dimana setiap node berisi beberapa data dan sebuah pointer ke node berikutnya dari tipe data yang sama (Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer).

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

ü  Sebuah linked list dikatakan kosong apabila isi pointer head adalah NULL

Metode yang dapat dilakukan adalah :

o   Insert

·         Case 1: insert data dari depan

·         Case 2: insert data dari belakang

·         Case 3: insert data dari sebelum node yang ditentukan

·         Case 4: insert data dari setelah node yang ditentukan

Node → next = head (depan)

Node → next = NULL (belakang)

Untuk menyisipkan nilai baru, pertama kita harus mengalokasikan node baru secara dinamis dan memberikan nilai padanya dan kemudian menghubungkannya dengan linked list yang ada.

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

node → value = x;

node → next  = head;

head = node;

  o   Delete

o   Untuk menghapus sebuah nilai, pertama kita harus mencari lokasi node yang menyimpan nilai yang ingin kita hapus, keluarkan, dan hubungkan sisa linked list.

o   Ada dua kondisi yang harus kita perhatikan: Jika x berada dalam head node atau x tidak berada dalam head node.

o   Cara paling cepat untuk mencari node yang ingin dihapus adalah dengan mencari yang ingin dihapus

o   Bila tidak terjadi validasi, maka data yang akan dihapus adalah data yang pertama kali ditemukan jika ada kesamaan data, dilihat dari head terlebih dahulu

struct tnode *curr = head;

// if x is in head node

if ( head->value == x ) {

          head = head->next;

          free(curr);

}

// if x is in tail node

else if(tail->value == x){

          while(curr->next!=tail) curr = curr->next;

          free(tail); tail = curr;

          tail->next = NULL;

}

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

Deleting 35 (not located at head)

POLYNOMIAL REPRESENTATION

ü  Setiap istilah polinomial dapat direpresentasikan sebagai simpul dari linked list.

ü  Setiap dari linked list terdapat 2  bagian yaitu; angka dan pangkat.

CIRCULAR SINGLE LINKED LIST

ü  Linked list yang paling belakang akan menuju ke head bukan ke null, dikarenakan circular.

ü  Dalam circular, node terakhir berisi pointer ke node pertama

ü  Tidak ada penyimpanan nilai NULL dalam List

DOUBLY LINKED LIST

     ü  Memiliki 2 pointer :

o   *Previous = menunjuk kebelakang

o   *Next = menunjuk kedepan

struct tnode {

 

int value;

struct tnode *next;  

struct tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

Metode yang dapat dilakukan adalah :

1.     Insert

ü  Sama seperti dalam single linked list, pertama kita harus mengalokasikan node baru dan memberikan nilai padanya, dan kemudian kita menghubungkan node dengan linked list yang ada.

ü  Memasukan simpul baru di belakang ekor dalam posisi tertentu (apapun lokasi antara kepala dan ekor)

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

node → value = x;

node → next  = NULL;

node → prev  = tail;

tail → next  = node;

tail = node

ü  Ada 4 kondisi yang harus kita perhatikan saat menghapus:

o   Node yang akan dihapus adalah satu-satunya Node dalam linked list.

o   Node yang akan dihapus adalah kepala.

o   Node yang akan dihapus adalah ekor.

o   Node yang akan dihapus bukan kepala atau ekor.

1. Jika Node yang akan dihapus adalah satu-satunya Node:

bebas (kepala);

kepala = NULL;

ekor = NULL;

2. Jika Node yang akan dihapus adalah kepala :

                                                head = head → next;

                                                free(head →  prev);

                                                head → prev = NULL;

3. Jika Node yang akan dihapus adalah ekor :

                                                tail = tail → prev;

                                                free(tail →  next);

                                                tail → next = NULL;

4.    If the node to be deleted is not in head or tail:

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

CIRCULAR DOUBLY LINKED LIST

ü  Terlihat sama dengan circular single linked list, tetapi total pointer di setiap node di sini adalah 2 (dua) pointer.

HEADER LINKED LIST

ü  Sebuah header linked list adalah tipe khusus linked list yang berisi node header di awal list

ü  Jadi, dalam sebuah header linked list, START (L) tidak akan mengarah ke node pertama dari list, tetapi START (L) akan berisi alamat nodel header.

Afrina Safira Dianirani

2101706772