Linked List


Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer. Oleh karena itu, ada baiknya 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 :

1

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 :
2

Sebelum digunakan harus dideklarasikan terlebih dahulu :
3

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
4

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

5

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.

FIFO (Fisrt In Fisrt Out)

FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat di analogikan (dalam kehidupan  sehari-hari),  misalnya  saat  sekelompok  orang  yang  datang  (ENQUEUE) mengantri hendak membeli tiket di loket. Jika  linked  list  dibuat  dengan  metode  FIFO,  terjadi  penambahan  /  Insert  simpul didepan.

A. Circular Double Linked List
Ini adalah double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

Operasi-Operasi yang ada pada Linked List:

Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.

Find First
Fungsi ini mencari elemen pertama dari linked list

Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.

Retrieve
Fungsi  ini  mengambil  elemen  yang  ditunjuk  oleh  now.  Elemen  tersebut  lalu
dikembalikan oleh fungsi.

Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.

Delete Now
Fungsi  ini  menghapus  elemen  yang  ditunjuk  oleh  now.  Jika  yang  dihapus  adalah
elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

Delete Head
Fungsi  ini  menghapus  elemen  yang  ditunjuk  head.  Head  berpindah  ke  elemen
sesudahnya.

Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda
ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya,
data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal
di dalam memori.

Contoh Program :
1. Membuat Single Linked List
6

2. Pencarian Nilai Terkecil dan Nilai Terbesar dalam sebuah Single Linked List
7

2 comments

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