Single link List & Doubly link List
Linked List atau dikenal juga dengan sebutan senarai berantai adalah
struktur data yang terdiri dari urutan record data dimana setiap record
memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam
urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut
Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.
·
Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
·
Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list
Ada beberapa
macam Linked List, yaitu :
1.
Single Linked List
Single Linked List merupakan
sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan
data yang dikenal dengan sebutan node atau 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. Biasanya Linked List pada
node terakhir akan menunjuk ke NULL, dimana NULL memilik
nilai khusus yang artinya tidak menunjuk ke mana-mana.
Pembuatan Single Linked List dapat menggunakan 2 metode:
– LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
– FIFO (First In First Out), aplikasinya : Queue (Antrean)
2.
Doubly Linked List
Doubly Linked List sama seperti Single link list merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Akan tetapi, setiap node pada doubly linked list selain memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, juga memiliki pointer yang menunjuk ke simpul sebelumnya. Susunan berupa untaian model ini disebut Doubly Linked List.
Doubly Linked List sama seperti Single link list merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Akan tetapi, setiap node pada doubly linked list selain memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, juga memiliki pointer yang menunjuk ke simpul sebelumnya. Susunan berupa untaian model ini disebut Doubly Linked List.
contoh soal yang menggunakan single link list
1.
Buatlah program untuk Single Link List yang bertipical
OderedList(List yang terurut) dengan menggunakan class OrderedList yang
berisikan method berikut
·
Add , saat akan menambahkan data dalam list maka data yang baru
ditambahkan akan langsung diurutkan (nip genap : urutan menaik mulai
dari yang terkecil ke yang terbesar, nip ganjil : urutan menurun mulai
dari yang terbesar ke yang terkecil)
·
Remove /Search : jika
data yang dicari tidak ada dan lebih kecil/lebih besar dari data setelahnya
maka langsung keluar dari perulangan
2.
Buatlah program seperti
diatas untuk yang Double Link List
Ø Penjelas Tugas
Praktikum NO.1
1.
Class Node
Merupakan class untuk membuat node.
Memiliki fungsi :
a.
__init__, fungsi
pertama kali dipanggil ketika diinisialisasi (sebuah constractor)
b.
getData, mengambil
nilai data dari suatu node
c.
getNext,mengambil
nilai atau data yang berada dalam tail dari node
d.
setData,mengubah
nilai data dari suatu node
e.
setNext, menentukan
node berikutnya
2.
Class OrderedList
Suatu class yang digunakan untuk menghasilkan list terurut, dikarenakan
NIM saya ganjil 170411100039 maka saya membuat program urutan menurun mulai dari yang terbesar ke
yang terkecil dengan
Memiliki beberapa fungsi sebagai berikut :
a.
__init__ membuat
sebuah single link dengan head dan tail = None (constractor)
b.
Show , menampilkan isi dari single link ordered list melakukan looping sampai getNext == None. Dan
lakukan print setiap data yang dilewati.
c.
Add, menambahkan
element baru dengan urutan menurun
Analisis method Add :
1.
Tampung Item baru kedalam
temp
2.
Inisialisasi current =
self.head, previous = None, stop = None
3.
Lakukan pengulangan sampai
current masih ada isinya dan not stop
4.
Jika data pada current <
item maka stop dan berubah jadi True, sehingga looping otomatis akan berhenti.
5.
Jika < previous diinisialisai
dengan current lalu selanjutnya current di isi dengan current getNext
6.
Looping berhenti cek lagi
7.
Jika previous == None maka
isi temp setNext dengan self.head dan self.head dengan temp
8.
Jika previous ada isinya
maka setNext temp denagn current dan setNetx previous dengan temp
d.
Size, menghitung
panjang dari sebuah single link dengan melakukan looping sampai getNext == None
dengan setiap iterasi counter + 1.
e.
isEmpty, digunakan
untuk memeriksa apakah stack dalam kondisi kosong atau tidak dengan nilai
pengembalian true or False
f.
Search, mencari sebuah data dalam single link
tersebut.
g.
Remove, mencari
sebuah data dan menghapusnya dari single link tersebut
Analisis Search :
a.
Inisialisasi current dengan
self.head, found = False, stop = False
b.
Lakukan looping ketika
current masih ada nilainya dan belum ketemu dan belum berhenti
c.
Jika data diambil dari
current dan sama dengan data yang dicari maka
found dan jika True dan otomatis looping akan berhenti.
d.
Jika tidak sama maka cek
lagi, jika data dari current leih kecil dari data yg dicari maka inisialisasi
stop menjadi True otomatis looping berhenti ,
e.
Jika tidak maka inisialisasi
(current.getNext())
f.
Kembalikan nilai dari
ke found
Analisis Remove :
a.
Inisialisasi current dengan
self.head, found = False, stop = False, previous = None.
b.
Lakukan looping ketika
current masih ada nilainya dan belum ketemu dan belum bisa berhenti
c.
Jika diambil data dari
current dan sama dengan data yang dicari maka inisialisasi found dengan True
dan otomatis looping akan berhenti.
d.
Jika tidak sama maka cek
lagi, jika data dari current leih kecil dari data yg dicari maka inisialisasi
stop menjadi True otomatis looping berhentim jika tidak maka inisialisasi
previous dengan current and current dengan node Selanjutnya (current.getNext())
e.
Jika loping berhenti cek
lagi
f.
Jika found = True maka cek
lagi jika sebelum data tidak ada maka self.head diisi Current.getNext, jika
sebelum data ada maka sambungkan ekor dara sebelum dan data sesudah, maka data
yg dicari akan terhapus.
g.
Jika found == False maka
print data yang akan diremove tidak ada
3.
Main Program
mylist = OrderedList()
print('==================Program Linked List (Ordered List)==============')
mylist.add(31)
mylist.add(32)
mylist.add(77)
mylist.add(15)
mylist.add(13)
mylist.show()
print(mylist.remove(31))
mylist.show()
print(mylist.search(30))
mylist.show()
a.
Tampung class orderedlist
dalam variabel myList
b.
Buat sebuah list dengan
nama mylist = [data,data,...]
c.
Panggil auto insert dengan
parameter mylist
d.
Tampilkan single linked
list dengan myList.show()
e.
Print panjang single linked
list dengan myList.size()
f.
Print hasil pemanggilan
myList.search(30)
g.
Removo angka sepuluh dengan
myList.remove(31)
h.
Tampilkan single linked
list lagi dengan myList.show()
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() < item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def remove(self,item):
if self.size() != 0:
current = self.head
previous = None
found = False
while not found and current != None:
if current.getData() == item:
found = True
print('Data %s telah dihapus'%item)
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print('Data %s yang dihapus tidak ada di List'%item)
else:
print('List sudah Kosong')
def show(self):
current = self.head
print ('None <-')
print ('Head ->', end='')
while current != None:
if current.getNext() == None:
print (current.getData(), end='->')
else:
print (current.getData(), end='<->')
current = current.getNext()
print ('None')
mylist = OrderedList()
print('==================Program Double Linked List (Ordered List)==============')
mylist.add(21)
mylist.add(55)
mylist.add(32)
mylist.add(15)
mylist.add(10)
mylist.show()
print(mylist.search(30))
mylist.show()
Hasil Print nya
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() < item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def remove(self,item):
if self.size() != 0:
current = self.head
previous = None
found = False
while not found and current != None:
if current.getData() == item:
found = True
print('Data %s telah dihapus'%item)
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print('Data %s yang dihapus tidak ada di List'%item)
else:
print('List sudah Kosong')
def show(self):
current = self.head
print ('None <-')
print ('Head ->', end='')
while current != None:
if current.getNext() == None:
print (current.getData(), end='->')
else:
print (current.getData(), end='<->')
current = current.getNext()
print ('None')
mylist = OrderedList()
print('==================Program Double Linked List (Ordered List)==============')
mylist.add(21)
mylist.add(55)
mylist.add(32)
mylist.add(15)
mylist.add(10)
mylist.show()
print(mylist.search(30))
mylist.show()
Hasil Print nya
==================Program Double Linked List (Ordered List)==============
None <-
Head ->55<->32<->21<->15<->10->None
False
None <-
Head ->55<->32<->21<->15<->10->None
>>>
None <-
Head ->55<->32<->21<->15<->10->None
False
None <-
Head ->55<->32<->21<->15<->10->None
>>>
#Ordered List (NIP.Ganjil)
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() < item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def remove(self,item):
if self.size() != 0:
current = self.head
previous = None
found = False
while not found and current != None:
if current.getData() == item:
found = True
print('Data %s telah dihapus'%item)
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print('Data %s yang dihapus tidak ada di List'%item)
else:
print('List sudah Kosong')
def show(self):
current = self.head
print('Head',end="->"),
while current != None:
print (current.getData(),end= "-> "),
current= current.getNext()
print (None)
mylist = OrderedList()
print('==================Program Linked List (Ordered List)==============')
mylist.add(31)
mylist.add(32)
mylist.add(77)
mylist.add(15)
mylist.add(13)
mylist.show()
print(mylist.remove(31))
mylist.show()
print(mylist.search(30))
mylist.show()
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() < item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def remove(self,item):
if self.size() != 0:
current = self.head
previous = None
found = False
while not found and current != None:
if current.getData() == item:
found = True
print('Data %s telah dihapus'%item)
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print('Data %s yang dihapus tidak ada di List'%item)
else:
print('List sudah Kosong')
def show(self):
current = self.head
print('Head',end="->"),
while current != None:
print (current.getData(),end= "-> "),
current= current.getNext()
print (None)
mylist = OrderedList()
print('==================Program Linked List (Ordered List)==============')
mylist.add(31)
mylist.add(32)
mylist.add(77)
mylist.add(15)
mylist.add(13)
mylist.show()
print(mylist.remove(31))
mylist.show()
print(mylist.search(30))
mylist.show()
hasil printnya
==================Program Linked List (Ordered List)==============
Head->77-> 32-> 31-> 15-> 13-> None
Data 31 telah dihapus
None
Head->77-> 32-> 15-> 13-> None
False
Head->77-> 32-> 15-> 13-> None
>>>
Head->77-> 32-> 31-> 15-> 13-> None
Data 31 telah dihapus
None
Head->77-> 32-> 15-> 13-> None
False
Head->77-> 32-> 15-> 13-> None
>>>
Komentar ini telah dihapus oleh pengarang.
BalasHapusmakasih kakak
BalasHapus