Struktur Data : Linked list in python

Dalam struktur “Struktur data dalam Python” ini, saya akan membahas struktur data utama sering muncul dalam segala jenis pekerjaan insinyur / wawancara magang yaitu linked list

Apa itu linked list?

ini adalah gambaran dari linked list. ada 2 hal penting yang harus di perhatikan:
1. Sebuah linked list berisikan node.

2. Setiap node berisikan value (nilai) dan penunjuk (panah) ke node lain.

value

penunjuk

node di paling awal dalam linked list biasa disebut dengan header.

pada dasarnya linked list adalah rangkaian nilai yang terhubung dengan penghubung (pointer).

Mengapa harus menggunakan Linked List?

Linked list sering dibandingkan dengan array (list). Sedangkan array adalah ukuran tetap dari rangkaian, daftar yang ditautkan dapat memiliki elemen untuk dialokasikan secara dinamis. Apa pro dan kontra dari karakteristik ini? Berikut beberapa hal yang utama:

Keuntungan

Linked list dapat menghemat memori. Dia hanya mengalokasikan memori yang diperlukan untuk nilai yang akan disimpan. Dalam array, Anda harus mengatur ukuran array sebelum mengisinya dengan nilai, yang berpotensi membuang memori.

Node linked list dapat tinggal di mana saja dalam memori. Sedangkan array membutuhkan urutan memori yang akan dimulai, selama referensi diperbarui, setiap node dalam linked list dapat dipindahkan secara fleksibel ke alamat yang berbeda.

Kerugian

Ketika mencari nilai dalam linked list, Anda harus mulai dari awal rantai, dan periksa satu elemen pada suatu waktu untuk nilai yang Anda cari. Jika linked list n memiliki elemen panjang, ini bisa memakan waktu hingga n time. Sebaliknya banyak bahasa memungkinkan pencarian konstan dalam array.

penerapan linked list:
untuk kelas node

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None # the pointer initially points to nothing

setelah memiliki kelas node kita bisa mengimplementasikan linked list berikut:

node1 = Node(12) 
node2 = Node(99) 
node3 = Node(37) 

node1.next = node2 # 12->99
node2.next = node3 # 99->37

# the entire linked list now looks like: 12->99->37

Anda mungkin bertanya-tanya mengapa saya tidak menerapkan kelas LinkedList. sebenarnya, linked list hanyalah sekelompok node yang terhubung bersama. Kami dapat merujuk ke header node sebagai linked list awal. Dalam contoh di atas, node1 adalah header node, dan itu juga dapat mewakili posisi dimulainya linked list.