Seperti array, Linked List adalah struktur data linier. Tidak seperti array, elemen daftar tertaut tidak disimpan di lokasi yang berdekatan; elemen dihubungkan menggunakan pointer.
Mengapa Daftar
Tertaut?
Array dapat digunakan untuk menyimpan data
linier dengan tipe yang sama, tetapi array memiliki batasan sebagai berikut.
1) Ukuran array tetap: Jadi kita harus mengetahui
batas atas jumlah elemen terlebih dahulu. Juga, umumnya, memori yang
dialokasikan sama dengan batas atas terlepas dari penggunaannya.
2) Memasukkan elemen baru ke dalam array elemen
mahal karena ruangan harus dibuat untuk elemen baru dan untuk membuat ruangan
elemen yang ada harus digeser tetapi di Linked list jika kita memiliki simpul
kepala maka kita dapat melintasi ke mana saja simpul melaluinya dan masukkan
simpul baru pada posisi yang diperlukan.
Misalnya, dalam sebuah sistem, jika kita
mempertahankan daftar ID yang diurutkan dalam array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
Dan jika kita ingin memasukkan ID baru 1005,
maka untuk mempertahankan urutan terurut, kita harus memindahkan semua elemen
setelah 1000 (tidak termasuk 1000).
Penghapusan juga mahal dengan array sampai
kecuali beberapa teknik khusus digunakan. Misalnya, untuk menghapus 1010
di id[], semuanya setelah 1010 harus dipindahkan karena begitu banyak pekerjaan
yang dilakukan yang mempengaruhi efisiensi kode.
Keuntungan
dibandingkan array
1) Ukuran dinamis
2) Kemudahan penyisipan/penghapusan
Kekurangan:
1) Akses acak tidak diperbolehkan. Kita harus
mengakses elemen secara berurutan mulai dari node pertama (head node). Jadi
kami tidak dapat melakukan pencarian biner dengan daftar tertaut secara efisien
dengan implementasi defaultnya. Baca tentang itu di sini .
2)Ruang memori ekstra untuk pointer diperlukan dengan
setiap elemen daftar.
3) Tidak ramah cache. Karena elemen array
adalah lokasi yang berdekatan, ada lokalitas referensi yang tidak ada dalam
kasus daftar tertaut.
Representasi:
Daftar tertaut diwakili oleh penunjuk ke simpul
pertama dari daftar tertaut. Node pertama disebut head. Jika daftar
tertaut kosong, maka nilai kepala menunjuk ke NULL.
Setiap node dalam daftar terdiri dari setidaknya
dua bagian:
1) data (kita dapat menyimpan integer, string,
atau jenis data apa pun).
2) Pointer (Atau Referensi) ke node berikutnya
(menghubungkan satu node ke node lain)
Dalam C, kita dapat merepresentasikan sebuah
node menggunakan struktur. Di bawah ini adalah contoh node linked list
dengan data integer.
Di Java atau C#, LinkedList dapat
direpresentasikan sebagai kelas dan Node sebagai kelas terpisah. Kelas LinkedList
berisi referensi tipe kelas Node.
class LinkedList {
Node
head; // head of the list
/*
Linked list Node*/
class
Node {
int
data;
Node
next;
//
Constructor to create a new node
//
Next is by default initialized
//
as null
Node(int
d) { data = d; }
}
}
Daftar Tertaut
Sederhana Pertama di C Mari kita buat daftar tertaut sederhana dengan 3 node.
// A simple Java program to introduce a linked list
class LinkedList {
Node
head; // head of list
/*
Linked list Node. This inner class is made static so that
main()
can access it */
static
class Node {
int
data;
Node
next;
Node(int
d)
{
data
= d;
next
= null;
}
// Constructor
}
/*
method to create a simple linked list with 3 nodes*/
public
static void main(String[] args)
{
/*
Start with the empty list. */
LinkedList
llist = new LinkedList();
llist.head
= new Node(1);
Node
second = new Node(2);
Node third = new Node(3);
/*
Three nodes have been allocated dynamically.
We
have references to these three blocks as head,
second
and third
llist.head second third
| |
|
| |
|
+----+------+ +----+------+ +----+------+
|
1 | null | | 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.head.next
= second; // Link first node with the second node
/*
Now next of the first Node refers to the second. So they
both
are linked.
llist.head second third
| |
|
| |
|
+----+------+ +----+------+ +----+------+
|
1 | o-------->| 2 | null |
| 3 | null |
+----+------+ +----+------+ +----+------+ */
second.next
= third; // Link second node with the third node
/*
Now next of the second Node refers to third. So all three
nodes
are linked.
llist.head second third
| |
|
| |
|
+----+------+ +----+------+ +----+------+
|
1 | o-------->| 2 | o-------->| 3 | null |
+----+------+ +----+------+ +----+------+ */
}
}
Linked List
Traversal
Pada program sebelumnya, kita telah membuat
linked list sederhana dengan tiga node. Mari kita menelusuri daftar yang
dibuat dan mencetak data dari setiap node. Untuk traversal, mari kita
tulis fungsi tujuan umum printList() yang mencetak daftar yang diberikan.
//
A simple Java program for traversal of a linked list
class LinkedList {
Node
head; // head of list
/*
Linked list Node. This inner class is made static so that
main()
can access it */
static class Node {
int data;
Node
next;
Node(int d)
{
this.data
= d;
next
= null;
}
// Constructor
}
/*
This function prints contents of linked list starting from head */
public void printList()
{
Node
n = head;
while (n != null) {
System.out.print(n.data
+ " ");
n
= n.next;
}
}
/*
method to create a simple linked list with 3 nodes*/
public static void main(String[] args)
{
/*
Start with the empty list. */
LinkedList
llist = new LinkedList();
llist.head
= new Node(1);
Node
second = new Node(2);
Node
third = new Node(3);
llist.head.next
= second; // Link first node with the second node
second.next
= third; // Link second node with the third node
llist.printList();
}
}
0 Komentar