Data Structure and Linked list
Data struktur adalah cara untuk menyimpan dan mengorganisir
suatu data dalam komputer supaya dapat digunakan secara efisien.
Kita biasa buat data struktur dalam kehidupan sehari hari.
Contohnya:
·
Secara Matematis/logika:
Biasanya dengan ini kita melihat
karakteristik suatu benda.
Misalnya Handphone adalah alat elektronik yang bisa dimatikan dan dinyalakan,
menerima dan mengirim signal, dan memproyeksi audio dan video.
Yang aku bold-kan merupakan pandangan abstrak/abstract view.
Dalam konsep komputer ini dpanggil sebagai Abstract data Types (ADT). Untuk
mengorganisir ADT kita gunakan List untuk simpan, baca, dan mengedit kumpulan
data tertentu. Dengan bahas komputer kita menggunakan Arrays.
Linked List:
Hampir sama seperti arrays, linked list merupakan data
struktur bersifat linear. Tapi bedanya linked list menggunakan pointer. Dalam
arti linked list terdiri dari zona/nodes yang mempunyai data dan referensi
Kalau lihat dari perbedaan Linked list lebih efektif dan
efisien dibandingi Array
·
Elemen dalam Array bersifat statis dan tidak
dapat di edit setelah array telah didefinisikan. Pembebasan memori dilakukan
saat program berhenti dan cara akses bersifat random dengan menggunakan nomor
index
·
Elemen dalam Linked List bersifat dianamis dan
ukurannya berubah-ubah tergantung keperluan. Pembebasan memori dilakukan setiap
kali ada penghapusan data, dan cara akses ke masing-masing kelas dilakukan
secara linear
Contoh: int arr[]=[1,3,4,5,6]
Kalau mau masukin 2 ke dalam array tersebut dengan masih
tersorted, arti kita harus majuin data setelah 1 aja(3,4,5,6). Untuk
menghapus/deletion hampir sama juga mis kita ambil nomor 1 di arr maka sisanya
mundur ke belakang
Kode Dev C untuk memakai linked list butuh:
// A linked list node
struct Node {
int
data;
struct
Node* next;
};
Contoh Kode dari Geeksforgeeks.com
// A simple C program to introduce
// a linked list
#include <stdio.h>
#include <stdlib.h>
struct
Node {
int data;
struct Node*
next;
};
// Program to create a simple linked
// list with 3 nodes
int
main()
{
struct Node* head
= NULL;
struct Node*
second = NULL;
struct Node*
third = NULL;
// allocate 3 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
/* Three blocks have been allocated
dynamically.
We have pointers to these
three blocks as head,
second and
third
head
second third
|
|
|
|
|
|
+---+-----+
+----+----+ +----+----+
| # | #
| | # | # | |
# | # |
+---+-----+
+----+----+ +----+----+
# represents any random value.
Data is random because we haven’t
assigned
anything yet */
head->data = 1; // assign data in
first node
head->next = second; // Link
first node with
// the second node
/* data has been assigned to the
data part of the first
block (block pointed by the
head). And next
pointer of first block points
to second.
So they both are linked.
head
second third
|
|
|
|
|
|
+---+---+
+----+----+ +-----+----+
| 1 | o----->| # |
# | | # | # |
+---+---+
+----+----+ +-----+----+
*/
// assign data to second node
second->data = 2;
// Link second node with the third
node
second->next = third;
/* data has been assigned to the
data part of the second
block (block pointed by
second). And next
pointer of the second block
points to the third
block. So all three blocks are
linked.
head
second third
|
| |
|
| |
+---+---+
+---+---+ +----+----+
| 1 | o----->| 2 |
o-----> | # | # |
+---+---+
+---+---+ +----+----+ */
third->data = 3; // assign data
to third node
third->next = NULL;
/* data has been assigned to data
part of third
block (block pointed by third). And
next pointer
of the third block is made NULL to
indicate
that the linked list is terminated
here.
We have the linked list
ready.
head
|
|
+---+---+
+---+---+ +----+------+
| 1 |
o----->| 2 | o-----> | 3 | NULL |
+---+---+
+---+---+ +----+------+
Note that only head is sufficient to
represent
the whole list. We can
traverse the complete
list by following next
pointers. */
return 0;
}
Inserting Node
Untuk meng-insert suatu node bisa di awal, tengah, akhir
dalam suatu Linked List.
Contoh ada linked list 1 2 3 4 5, untuk meletakan 0 kita
harus taru di paling belakang list dan
menggeser list yang sudah ada. Maka jadi 0 1 2 3 4 5
Dalam bentuk kode C kita butuh ini
void
push(struct
Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node*
new_node = (struct
Node*) malloc(sizeof(struct Node));
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head
*/
new_node->next = (*head_ref);
/* 4. move the head to point to the
new node */
(*head_ref) =
new_node;
}
Menghapus Node
Sama seperti untuk menginsert node, kita bisa menghapus node
yang ada di awal, tengah, dan akhir linked list.
Yang kita butuh dalam kode C adalah ini
void
deleteNode(struct Node **head_ref, int key)
{
// Store head node
struct Node* temp
= *head_ref, *prev;
// If head node itself holds the key
to be deleted
if (temp !=
NULL && temp->data == key)
{
*head_ref =
temp->next; // Changed head
free(temp);
// free old head
return;
}
// Search for the key to be deleted,
keep track of the
// previous node as we need to
change 'prev->next'
while (temp !=
NULL && temp->data != key)
{
prev = temp;
temp =
temp->next;
}
// If key was not present in linked
list
if (temp ==
NULL) return;
// Unlink the node from linked list
prev->next = temp->next;
free(temp); // Free memory
}
Circular Singly, Circular Doubly dan
Doubly Linked List
Circular single ini
berulang dari node akhir ke node pertama, dan tidak ada nilai NULL dalam list
ini
Circular Doubly Linked List sama seperti singly tapi ada 2
referensi
Doubly Linked list
merupakan linked list 2 arah dimana node satu memegang referensi ke node 2 dan
sebaliknya juga
Contoh Kodenya
struct tnode {
int value;
struct tnode
*next;
struct tnode
*prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
Untuk menginsert ada 2 cara tergantung posisi
·
Untuk dari belakang
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
·
Untuk antara depan dan belakang
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;
b->prev = node;
Untuk menghapus kita harus perhatiin kondisi
·
Yang dihapus hanya node di linked list
free(head);
head = NULL;
tail = NULL;
·
Node yang dihapus itu awal
head = head->next;
free(head->prev);
head->prev =
NULL;
·
Node yang dihapus yang akhir
tail = tail->prev;
free(tail->next);
tail->next = NULL;
·
Node yang tidak dihapusin bukan awal atau akhir
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);
