Struktur Data Linear ialah data yang dipresentasikan berhubungan dengan data lainnya dengan teratur (lurus) sehingga membentuk barisan antara data satu dengan data lainnya.
Linked
List ialah suatu record data yang dihubungkan satu dengan lainnya menggunakan
pointer.
Fungsi-fungsi
yang dapat dipakai dalam operasi linked list adalah:
1. Fungsi
menambah simpul di belakang. Langkah-langkahnya:
a. membuat
simpul baru kemudian diisi info baru.
b. simpul
paling akhir dihubungkan ke simpul baru.
c. penunjuk
pointer akhir diarahkan ke simpul simpul baru.
2. Fungsi
menambah simpul di depan. Langkah-langkahnya:
a. membuat
simpul baru, kemudian diisi info baru.
b. simpul
baru dihubungkan ke simpul awal.
c. penunjuk
pointer awal diarahkan ke simpul baru.
3. Fungsi
menyisipkan simpul di tengah. Langkah-langkahnya:
a. membuat
simpul bantu, kemudian diisi info baru.
b. menentukan
di mana simpul baru akan ditambahkan, yaitu dengan menempatkan pointer bantu
pada suatu tempat.
c. pointer
baru dihubungkan ke simpul setelah simpul yang ditunjuk oleh pointer bantu,
kemudian penunjuk pointer bantu diarahkan ke simpul baru.
4. Fungsi
menghapus simpul di depan. Langkah-langkahnya:
a. simpul
bantu diarahkan pada simpul awal.
b. simpul
awal diarahkan ke simpul berikutnya.
c. menghapus
simpul bantu.
5. Fungsi
menghapus simpul di tengah. Langkah-langkahnya:
a. meletakkan
pointer bantu di sebelah kiri simpul yang akan dihapus.
b. simpul
yang akan dihapus ditunjuk oleh pointer lain, misalnya pointer hapus.
c. pointer
bantu diarahkan ke simpul yang ditunjuk oleh hapus, kemudian simpul hapus
dihapus.
6. Fungsi
menghapus simpul di belakang. Langkah-langkahnya:
a. meletakkan
pointer bantu di sebelah kiri simpul yang akan dihapus.
b. simpul
yang akan dihapus ditunjuk oleh pointer lain, misalnya pointer hapus.
c. pointer
bantu, diarahkan ke simpul yang ditunjuk oleh hapus, kemudian simpul hapus
dihapus.
7. Fungsi
mencetak list dengan membaca maju. Langkah-langkahnya:
a. mengatur
agar pointer bantu menunjuk simpul yang ditunjuk oleh pointer awal.
b. setelah
isi simpul dibaca dan dicetak, pointer bantu digerakkan ke kanan untuk membaca
simpul berikutnya.
c. proses ini
diulang sampai pointer bantu sama dengan pointer akhir.
8. Fungsi
mencetak list dengan membaca mundur. Langkah-langkahnya:
a. mengatur
agar pointer bantu menunjuk simpul yang ditunjuk oleh pointer akhir.
b. setelah
pointer bantu menunjuk simpul akhir, baru dicetak.
c. proses
pencetakan dilanjutkan dengan mencetak isi simpul di sebelah kiri simpul akhir.
d. proses selesai
jika isi simpul paling awal telah selesai dicetak.
9. Fungsi
mencari data pada list. Langkah-langkahnya:
a. data yang
dicari disimpan dalam suatu variabel, misalkan elemen.
b. membuat
pointer bantu sama dengan pointer awal.
c. isi simpul
yang ditunjuk oleh pointer bantu dibandingkan dengan elemen. Jika sama, berarti
data yang dicari ditemukan. Jika belum sama, maka pointer bantu dipindahkan ke
simpul di sebelah kanannya dan proses perbandingan diulang. Proses ini diulang
sampai data yang dicari ditemukan atau sampai pada simpul akhir
1. Single Linked List Non Circular
Setiap node pada linked list mempunyai field yang berisi data dan pointer ke
node berikutnya & ke node sebelumnya. Untuk pembentukan node baru, mulanya
pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya pointer prev akan menunjuk ke node
sebelumnya, dan pointer next akan menunjuk ke node selanjutnya pada list.
Deklasari simpul :
Struct simpul{
int
angka;
simpul
*berikut;
};
a.
Tambah Depan
Prinsipnya
ketika data baru datang atau akan ditambahkan maka head atau awal akan menunjuk pada data baru tersebut dan data baru
tersebut menunjuk pada data yang lama. Sehingga data lama akan menjadi di bawah
data baru.
void tambahdepan(int x)
{
struct titik *baru;
baru=new titik;
baru->angka=x;
baru->berikut=awal;
awal=baru;
}
b. Tambah
Belakang
Pada prinsipnya sama dengan
antrian, siapa yang masuk dialah yang akan keluar terlebih dulu. Maka data lama
akan tetap menjadi awal bagi data
baru, sehingga data pertama kali masuk akan terus menjadi awal dan data baru akan terus menjadi setelah data sebelumnya.
void tambahbelakang(int x) {
struct simpul *baru;
baru=new simpul;
baru->angka=x;
if(awal==NULL){
awal=baru;}
else{
akhir->berikut=baru; }
akhir=baru;
akhir->berikut=NULL;
}
c. Tambah
List di tengah
Tambah
list ditengah ini berguna ketika kita telah menginputkan data ternyata terdapat
data yang terlewat untuk diinputkan dan harus berada diantara data yang telah
di inputkan. Untuk memudahkan pemahamannya saya akan memberikan langsung dengan
pengisian datanya. Yang pertama terdapat fungsi sisip_isi() ini berfungsi untuk menginputkan data dan fungsi sisip_list(simpul *first, int x, int posisi)
untuk menentukan data akan disimpan setelah data yang mana sehingga dapat
diisi diantara data-data yang lainnya.
void sisip_list(struct simpul *first,int x,int
posisi)
{
struct simpul *bantu,*baru;
baru = new simpul;
baru->angka=x;
bantu=first;
do
{
if (posisi!=bantu->angka)
{bantu=bantu->berikut;}
}
while (bantu!=NULL && posisi!=bantu->angka);
baru->berikut=bantu->berikut;
bantu->berikut=baru;
}
void sisip_isi_list()
{
int cari;
int ganti;
cout<<"\nBilangan : ";
cin>>ganti;
cout<<"\nDisipkan setelah :
";
cin>>cari;
sisip_list(awal,ganti,cari);
}
d.
Hapus Tengah
Tidak jauh
beda dengan isi list di tengah, kita membutuhkan 2 fungsi yang pertama untuk
mengiput data yang akan dihapus dan fungsi yang akan menghapus list. Fungsi carihapus() akan menjadi fungsi untuk
membawa parameter atau nilai yang akan dihapus sementara fungsi hapustengah(int info) akan menghapus data
yang sesuai dengan isi dari info yang
dibawa oleh fungsi carihapus().
void hapustengah(int info)
{
titik *bantu,*hapus;
bantu=awal;
while ((info!=bantu->berikut->angka)
&& (bantu->berikut!=NULL))
{
bantu=bantu->berikut;
}
hapus=bantu->berikut;
bantu->berikut=hapus->berikut;
delete hapus;
}
void carihapus()
{
int cari;
clrscr();
tampillist();
cout<<"\nData yang akan dihapus, Bilangan
:";
cin>>cari;
hapustengah(cari);
cout<<"\nData menjadi :";
tampillist();
}
e.
Hapus Depan
Hapus di
depan sebenarnya sangat simple karena kita bisa langsung menghapus *awal, namun disela itu sebelum tugas
kita menghapus *awal kita harus
mengganti *awal dengan pointer
berikutnya sehingga ketika ditampilkan, data masih akan terlihat.
Void hapusdepan()
{
Simpul *hapus;
Hapus=awal;
Awal=hapus->berikut;
Delete hapus;
}
f. Hapus Belakang
Tidak jauh
beda dengan hapus depan, namu hapus belakang membutuhkan looping untuk
mengetahui bahwa dia adalah simpul paling terakhir.
Void hapusbelakang()
{
Simpul *hapus, *bantu;
Bantu=awal;
While(bantu->berikut->berikut!=NULL){
bantu=bantu->berikut;
}
hapus=bantu->berikut;
bantu->berikut=NULL;
delete hapus;
}
g. Hapus Semua
Hapus semua merupakan cara penghapusan paling sederhana, kita hanya menentukan kapan *hapus berisi null dan disitulah dia berhenti.
void hapus()
{
simpul *hapus;
hapus=awal;
while(hapus!=NULL){
awal=hapus->berikut;
delete hapus;
hapus=awal;
}
}
2. Single Linked list Circular
Single
Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single
Linked List tersebut terdiri dari beberapa node, maka pointer next pada node
terakhir akan menunjuk ke node terdepannya.
Deklarasi
simpul :
struct simpul{
int
angka;
simpul *berikut;
};
a. Tambah
Depan
Pada prinsipnya adalah
mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru
tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan
node terakhir dengan node terdepan dibutuhkan pointer bantu.
void tambahdepan(int x)
{
simpul *baru, *bantu;
baru = new simpul;
baru->angka=x;
baru->berikut=baru;
if(awal==NULL){
awal=baru;
awal->berikut=awal;
}
else{
bantu=awal;
while(bantu->berikut!=awal){
bantu=bantu->berikut;
}
baru->berikut=awal;
awal=baru;
bantu->berikut=awal;
}
}
b. Tambah
Belakang
Penambahan di belakang lebih
sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang,
kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu
digunakan perulangan.
void tambahbelakang(int x)
{
simpul *baru, *bantu;
baru = new simpul;
baru->angka=x;
baru->berikut=baru;
if(awal==NULL){
awal=baru;
awal->berikut=awal;
}
else{
bantu=awal;
while(bantu->berikut!=awal){
bantu=bantu->berikut;
}
bantu->berikut=baru;
awal=baru;
baru->berikut=awal;
}
}
1. 3. Double
Linked List Circular
Setiap node pada linked list
mempunyai field yang berisi data dan pointer ke node berikutnya & ke node
sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk
ke dirinya sendiri. Jika sudah lebih
dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer
next akan menunjuk ke node sesudahnya.
Deklarasi simpul :
Struct simpul{
int angka;
simpul *next;
simpul *prev;
};
a.
a. Tambahdepan
Pada prinsipnya adalah mengkaitkan
data baru dengan head, kemudian head akan menunjuk pada data baru tersebut
sehingga head akan tetap selalu menjadi data terdepan. Dibutuhkan pointer bantu
yang digunakan untuk menunjuk node terakhir (head->prev) yang akan digunakan
untuk mengikat list dengan node terdepan.
void tambahdepan(int x){
simpul *baru, *bantu;
baru = new simpul;
baru->angka = x;
baru->next = baru;
baru->prev = baru;
if(awal==NULL){
awal=baru;
awal->next =awal;
awal->prev = awal;
}
else {
bantu = awal->prev;
baru->next = awal;
awal->prev = baru;
awal = baru;
awal->prev = bantu;
bantu->next = awal;
}
}
b b. Tambah Belakang
Penambahan di belakang lebih sulit
karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, namun
tidak diperlukan loop karena untuk mengetahui node terbelakang hanya perlu
menunjuk pada head->prev saja. Kemudian dikaitkan dengan data baru. Untuk
mengetahui data terbelakang perlu digunakan perulangan.
void tambahbelakang (int
x){
simpul *baru,*bantu;
baru = new simpul;
baru->data = x;
baru->next = baru;
baru->prev = baru;
if(awal==NULL){
awal=baru;
awal->next = awal;
awal->prev = awal;
}
else {
bantu=awal->prev;
bantu->next = baru;
baru->prev = bantu;
baru->next = awal;
awal->prev = baru;
}
}
1.
4. Double Linked List Non-Circular
Double Linked List Non Circular adalah linked
list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1
field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer
sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.
Deklarasi
simpul :
Struct simpul{
Int
angka;
simpul
*next;
simpul
*prev;
};
a. Tambah
depan
Pada prinsipnya
adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data
baru tersebut sehingga head akan tetap selalu menjadi data terdepan.
void tambahdepan(int x)
{
titik *baru;
baru=new simpul;
baru->nilai=x;
baru->next=NULL;
baru->prev=NULL;
if(awal==NULL){
awal=baru;
awal->next=NULL;
awal->prev=NULL;
}
else{
baru->next=awal;
awal->prev=baru;
awal=baru;
}
}
b. Tambah
belakang
Penambahan di belakang lebih sulit karena kita membutuhkan pointer
bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru.
Untuk mengetahui data terbelakang perlu digunakan perulangan.
void tambahbelakang(int x)
{
titik *baru, *bantu;
baru=new simpul;
baru->nilai=x;
baru->next=NULL;
baru->prev=NULL;
if(awal==NULL){
awal=baru;
awal->next=NULL;
awal->prev=NULL;
}
else{
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next=baru;
baru->prev=bantu;
}
}
Sumber : Antonius Rachmat C, S.Kom, Ibu Yuli