Pendahuluan
Dalam suatu linear list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.
Misalkan ada 1500 item yang merupakan elemen dari suatu linear list.
Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linear list tersebut. Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.
Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.
Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.
Definisi
Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
¨ INFO , berisi informasi tentang elemen data yang bersangkutan.
¨ NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju.
¨ Berikut ini sebuah contoh linked list yang terdiri atas 4 node :
¨ Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.
¨ Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :
Operasi Pada Linked List
Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :
¨ Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang dituju.
¨ Operasi yang didefinisikan pada suatu variabel pointer adalah :
1. Test apakah sama dengan NULL.
2. Test untuk kesamaan dengan variabel pointer lain.
3. Menetapkan sama dengan NULL.
4. Menetapkan menuju ke node lain.
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :
- NODE(P), artinya node yang ditunjuk oleh pointer P.
- INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.
- NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.
Sebagai contoh, perhatikan linked list disamping:
NODE(P) = node yang ditunjuk oleh P yaitu node pertama.
INFO(P) = A
NEXT(P) = node ke-dua
INFO(NEXT(NEXT(P))) = C
Menghapus Node List
Pendahuluan
Dalam suatu linear list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.
Misalkan ada 1500 item yang merupakan elemen dari suatu linear list.
Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linear list tersebut. Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.
Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.
Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.
Definisi
Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
¨ INFO , berisi informasi tentang elemen data yang bersangkutan.
¨ NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju.
¨ Berikut ini sebuah contoh linked list yang terdiri atas 4 node :
¨ Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.
¨ Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :
Operasi Pada Linked List
Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :
¨ Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang dituju.
¨ Operasi yang didefinisikan pada suatu variabel pointer adalah :
1. Test apakah sama dengan NULL.
2. Test untuk kesamaan dengan variabel pointer lain.
3. Menetapkan sama dengan NULL.
4. Menetapkan menuju ke node lain.
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :
- NODE(P), artinya node yang ditunjuk oleh pointer P.
- INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.
- NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.
Sebagai contoh, perhatikan linked list disamping:
NODE(P) = node yang ditunjuk oleh P yaitu node pertama.
INFO(P) = A
NEXT(P) = node ke-dua
INFO(NEXT(NEXT(P))) = C
Menghapus Node List
Sebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih dahulu dilakukan. Bila node yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan node tersebut dari linked list dan kemudian menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam linked list adalah O(n). Perhatikan gambar berikut ini: 
/*PROGRAM LINKED-LIST
_ _ _ _ _ _ _ _ _ _ _ _ */
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
class Node
{
public:
int x;
Node *ka;
};
void main()
{
int n,i;
Node *awal, *akhir, *temp;
awal = new Node;
akhir = awal;
cout<<"N = " ; cin>>n;
for ( i=1; i<=n; ++i)
{
temp = new Node;
temp->ka = NULL;
cout<<"Data ke " <<i <<" = ";
cin>> temp->x;
akhir->ka = temp;
akhir = temp;
}
cout<<"Seluruh Data1\n";
temp = awal->ka;
while (temp->ka !=NULL)
{
cout << temp->x <<endl;
temp = temp-> ka;
}
cout<< temp-> x <<endl;
cout<<"Seluruh Data2\n";
temp = awal->ka;
while (temp !=NULL)
{
cout << temp->x <<endl;
temp = temp-> ka;
}
int p;
cout<<"Hapus posisi ke " ; cin>>p;
Node *temp1, *temp2;
temp1 = awal;
for ( i= 1; i<p; ++i)
temp1=temp1->ka;
temp2 = temp1->ka;
temp1->ka = temp2->ka;
delete temp2;
cout<<"Seluruh Data\n";
temp = awal->ka;
while (temp !=NULL)
{
cout << temp->x <<endl;
temp = temp-> ka;
}
getch();
}
berikut adalah outputan programSebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih dahulu dilakukan. Bila node yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan node tersebut dari linked list dan kemudian menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam linked list adalah O(n). Perhatikan gambar berikut ini:
/*PROGRAM LINKED-LIST
_ _ _ _ _ _ _ _ _ _ _ _ */
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
class Node
{
public:
int x;
Node *ka;
};
void main()
{
int n,i;
Node *awal, *akhir, *temp;
awal = new Node;
akhir = awal;
cout<<"N = " ; cin>>n;
for ( i=1; i<=n; ++i)
{
temp = new Node;
temp->ka = NULL;
cout<<"Data ke " <<i <<" = ";
cin>> temp->x;
akhir->ka = temp;
akhir = temp;
}
cout<<"Seluruh Data1\n";
temp = awal->ka;
while (temp->ka !=NULL)
{
cout << temp->x <<endl;
temp = temp-> ka;
}
cout<< temp-> x <<endl;
cout<<"Seluruh Data2\n";
temp = awal->ka;
while (temp !=NULL)
{
cout << temp->x <<endl;
temp = temp-> ka;
}
int p;
cout<<"Hapus posisi ke " ; cin>>p;
Node *temp1, *temp2;
temp1 = awal;
for ( i= 1; i<p; ++i)
temp1=temp1->ka;
temp2 = temp1->ka;
temp1->ka = temp2->ka;
delete temp2;
cout<<"Seluruh Data\n";
temp = awal->ka;
while (temp !=NULL)
{
cout << temp->x <<endl;
temp = temp-> ka;
}
getch();
}
berikut adalah outputan program
Tidak ada komentar:
Posting Komentar