LINKED LIST

Sebagai mahasiswa informatika tentu pasti  telah belajar mengenai variabel array yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah di atas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali.
Jadi,bila kita ingin menambahkan data, harus selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer. Oleh karena itu, adabaiknya jika Anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked list adalah sekumpulan
elemen bertipe sama, yang mempunyai keterurutan tertentu
, yang setiap elemennya
terdiri dari dua bagian.
Bentuk Umum :

typedef struct telmtlist

{

infotype info;

address next;

}elmtlist;


infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
next address dari elemen berikutnya (suksesor)

Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu
dengan notasi :

first(L);

Seperti biasa sebelum kita menggunakan notasi tersebut, perlu dideklarasikan diheader program dengan

#define first(L)       (L)

Elemen yang nak diacu oleh P akan dikonsultasikan terlebih dahulu dengan cara:

info(P) dideklarasikan di header dengan cara #define info(P)    (P)->info

next(P) dideklarasikan diheader dengan cara  #define next(P)   (P)->next

Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null

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/simpul. Setiap node memiliki pointer yang menunjuk ke
simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan
sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked
List (NULL memilik 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)
LIFO ( Last In First Out)
Lifo adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir
adalah data yang keluar paling awal. Hal ini dapat dianalogikan (dalam kehidupan
sehari-hari) dengan saat Anda menumpuk barang seperti digambarkan dibawah ini.
Pembuatan sebuah simpul dalam suatu linked list seperti digambarkan dibawah ini.
Jika linked list dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di
belakang, dikenal dengan istilah INSERT.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s