Pertemuan 1 - Array, Pointer, Linked List - 2101711122 - Bela Kristianti

Struktur data adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.

Beberapa contoh umum dari struktur data meliputi :

1. Arrays

Kumpulan elemen data yang serupa. Elemen data memiliki tipe data yang sama

2. Linked List

Struktur data yang sangat dinamis dimana elemen dapat ditambahkan ke atau dihapus dari mana saja sesuka hati. Setiap elemen disebut node

3. Queue

Queue pada struktur data atau antrian adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisi belakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front). 

Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out).

4. Stacks

Pengertian Stack atau Tumpukan adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  

Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan “di atas“ TOP dan Penghapusan selalu dilakukan pada TOP

5. Binary Trees

Sebuah pohon biner (binary tree) adalah himpunan terbatas yang mungkin kosong atau terdiri dari sebuah simpul yang disebut sebagai akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai sub pohon kiri (left) dan sub pohon kanan (right) dari pohon biner tersebut. Pohon biner merupakan tipe yang sangat penting dari struktur data dan banyak dijumpai dalam berbagai terapan. Karakteristik yang dimiliki oleh pohon biner adalah bahwa setiap simpul paling banyak hanya memiliki dua buah anak, dan mungkin tidak punya anak. Istilah-istilah yang digunakan sama dengan istilah pada pohon secara umum.

Tipe Data Struktur

Tipe Data adalah kumpulan objek dan satu set operasi yang bekerja pada objek tersebut.

Sebagai contoh, tipe data int terdiri dari:

objek: 0, +1, -1, +2, -2, dll

operasi: +, -, *, /,%, dll

Contoh tipe data yang telah ditentukan adalah int, char, float.

Abstract Data Type

Abstract Data Type (ADT) adalah tipe data yang disusun sedemikian rupa sehingga spesifikasi objek dan spesifikasi operasi pada objek dipisahkan dari representasi objek dan pelaksanaan operasi.

C / C ++ memiliki konsep yang disebut class dan struct yang membantu programmer dalam mengimplementasikan tipe data abstrak.

Contoh :

structure Number is

            objects : an integer x

            functions :

                        bool is_zero()  if ( x == 0 ) return TRUE else return FALSE

                        bool equal(y)  if ( x == y ) return TRUE else return FALSE

                        void set(y)       x = y

                        void add(y)     x = x + y

                        int get ()                      return x

 A. Array

• Kumpulan elemen data yang serupa
• Elemen data ini memiliki tipe data yang sama (homogen) 
• Elemen-elemen array disimpan di lokasi memori berturut-turut dan direferensikan oleh sebuah indeks 
• Indeks Array dimulai dari nol

1.      Array Declaration & Accessing Array

• One Dimensional Array

Sebelum digunakan, variabel array perlu dideklarasikan terlebih dahulu. Cara mendeklarasikan variabel array sama seperti deklarasi variabel yang lainnya, hanya saja diikuti oleh suatu indek yang menunjukan jumlah maksimum data yang disediakan

• Two Dimensional Array

Array dimensi dua tersusun dalam bentuk baris dan kolom, dimana indeks pertama menunjukan baris dan indeks kedua menunjukan kolom. Array dimensi dua dapat digunakan seperti pendatan penjualan, pendataan nilai dan lain sebagainya

• Multi Dimensional Array

2.     Storing Array Values

Initialization of Arrays

Contoh :    int marks[5] = {10, 20, 30, 40, 50};

Inputting Values

Contoh :    int i, marks[10];

                              for (i=0; i<10; i++)

                                          scanf(“%d”, &marks[i]);

Assigning Values

      Example:         int i, arr1[10], arr2[10];

                              for(i=0; i<10; i++)

                                          arr2[i] = arr1[i];

3.     Operations in Array

Ada sejumlah operasi yang bisa dilakukan
pada array, yaitu :

• Traversal 
• Insertion 
• Searching 
• Deletion 
• Merging 
• Sorting

B. Pointer
 
 Pointer adalah tipe data yang nilainya mengacu pada nilai lain yang tersimpan. Di tempat lain dalam memori komputer menggunakan alamatnya.

Dua operator terpenting yang digunakan dengan tipe pointer adalah : 

•  Operator alamat (&)

Operator & bersifat unary (hanya memerlukan satu operand saja).

Operator & menghasilkan alamat dari operandnya.

 

• Operator dereferencing (*)

Operator * bersifat unary (hanya memerlukan satu operand saja).

Operator * menghasilkan nilai yang berada pada sebuah alamat.

 

Deklarasi Pointer :

      int x;

      int *px;

maka x adalah integer dan px adalah pointer ke integer. Jika kita mengatakan:

px = & x;

maka & x mengembalikan alamat x dan menugaskannya sebagai nilai px.

Untuk menetapkan nilai x bisa kita katakan

x = 5;

atau

* px = 5;

C. Linked List

• Linked List adalah sekumpulan elemen bertipe sama yang mempunyai keterurutan

tertentu, yang setiap elemennya terdiri dari dua bagian.

• Struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan

elemen lain melalui pointer (alamat elemen). Penggunaan pointer untuk mengacu

elemen berakibat elemen-elemen bersebelahan secara logik, walau tidak bersebelahan

secara fisik di memori.

1. Single Linked List
Pada gambar di atas, tampak bahwa sebuah data terletak pada sebuah lokasi memori area.
Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal
dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul
berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah
variable pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL
memiliki nilai khusus yang artinya tidak menunjuk ke mana-mana, biasanya Linked List pada
titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode : LIFO (Last In First Out), aplikasinya: Stack (tumpukan), FIFO (First In First Out), aplikasinya: Queue (antrean)

2. Double Linked List
Salah satu kelemahan Single Linked List adalah pointer hanya dapat bergerak satu arah saja,
maju/mundur, kanan/kiri, sehingga pencarian data pada Single Linked List hanya dapat
bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan
metode Double Linked List. Linked List ini dikenal dengan nama Linked List berpointer ganda
atau Double Linked List.

3. Circular Double Linked List
Merupakan Double Linked List yang simpul terakhirnya menunjuk ke simpul terakhirnya
menunjuk ke simpul awalnya menunjuk ke simpul akhir, sehingga membentuk suatu lingkaran.

4. Operasi pada Linked List

Operasi yang terpenting pada linked list, yaitu menambahkan node (insert) dan menghapus node (delete).

5. Structure Declaration

 

struct tdata { 

int age; 

char name [100]; 

float score;
};
 

Kode di atas mendefinisikan sebuah struktur bernama tdata yang memiliki tiga anggota: age (int), name (char []) dan score (float).
Membuat variabel struktur mirip dengan membuat variabel tipe data primitif.
tdata x; // variabel dari tdata
tdata arr [100]; // array tdata

6. Linked List versus Array

• Array :

Kumpulan data elemen linier

Simpan nilai di lokasi memori berurutan

Bisa acak dalam mengakses data

• Linked :

Linear koleksi dari node

Tidak menyimpan simpulnya di lokasi memori berturut-turut

Dapat diakses hanya secara berurutan