Materi Linked List - Single Link dan Double Link - Struktur Data

Materi Linked List


A. Single List

Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer.

Rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null.

Single Linked List hanya memiliki satu arah dan tidak memiliki dua arah atau bulak balik, dua arah tersebut disebut dengan double linked list.

Pada Implementasinya, Single Linked List terdapat dua variasi yaitu circular dan non-circular.
Berikut adalah ilustrasi single linked list Non-Circular

Single Linked List Non-Circular

sedangkan untuk single linked list Circular nya adalah sebagai berikut.

Single Linked List Circular
Single Linked List sendiri pun, terdapat beberapa metode yang dapat dilakukan yaitu :
  1. Creations
  2. Insert :
    3. 1. Depan
    2. Belakang
    3. Posisi
  3. Delete :
    4. 1. Depan
    2. Belakang
    3. Posisi
  4. Traversal
  5. Sorting
  6. Searching
  7. Termination
Souces Code :

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 show(self):
        current = self.head
        print('Head -> ',end='')
        while current != None:
            print(current.getData(),end=' -> ')
            current = current.getNext()
        print('None')
    
    def add(self,item):
        temp = Node(item)
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            print('adding',item)
            if current.getData() < item:
                    stop = True
            else:
                previous = current
                current = current.getNext()
            
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)
                
        
        
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
        
    def search(self,item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            print('search',current.getData())
            if current.getData() == item:
                found = True
            else:
                if current.getData() < item:
                    stop = True
                else:
                    current = current.getNext()

        return found
    
    def remove(self,item):
        current = self.head
        previous = None
        found = False
        stop = False
        while current != None and not found and not stop:
            print('remove',current.getData())
            if current.getData() == item:
                found = True
            else:
                if current.getData() < item:
                    stop = True
                else:
                    previous = current
                    current = current.getNext()
        if found:
            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())
        else:
            print('data tidak ada')
    
    def isEmpty(self):
        return self.head == None

def autoInsert(mylist,alist):
    for i in alist:
        mylist.add(i)

mylist = OrderedList()
alist = [1,2,3,4,5,6,7,8,9,10]
autoInsert(mylist,alist)
mylist.show()
print('Panjang List =',mylist.size())
print('found',mylist.search(3.5))
mylist.remove(10)
mylist.show()

Hasil Run :

Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
=========== RESTART: /home/rejeb/Downloads/1orderedListMenurun.py ===========
adding 2
adding 3
adding 4
adding 5
adding 6
adding 7
adding 8
adding 9
adding 10
Head -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> None
Panjang List = 10
search 10
search 9
search 8
search 7
search 6
search 5
search 4
search 3
found False
remove 10
Head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> None
>>>


B. Double Link List

Double Link List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau belakang.

Elemen double link list terdiri dari tiga bagian:

  • Bagian data informasi
  • Pointer next yang menunjuk ke elemen berikutnya
  • Pointer prev yang menunjuk ke elemen sebelumnya

Untuk menunjuk head dari double link list, pointer prev dari elemen pertama menunjuk NULL. Sedangkan untuk menunjuk tail, pointer next dari elemen terakhir menunjuk NULL.

Jenis-jenis Double Link :

  1. Double Linked List Circular

    2. Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:


    • 1 field pointer yang menunjuk pointer berikutnya “next“,
    • 1 field menunjuk pointer sebelumnya ” prev “,
    • 1 field yang berisi data untuk node tersebut .

    Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

  2. Double Linked List Non Circular

    3. DLLNC "Double linked list non circular" adalah Double Linked List yang memiliki 2 buah pointer yaitu pointer next dan prev. Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya.

    Pengertian:
    Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.
    Linked List : artinya node-node tersebut saling terhubung satu sama lain.
    Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL.
Sources Code :


class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None
        self.prev = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def getPrev(self):
        return self.prev

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

    def setPrev(self,newprev):
        self.prev = newprev

class OrderedList:

    def __init__(self):
        self.head = None

    def show(self):
        current = self.head
        print ('None <- -="" ead="" end="" print="">', end='')
        while current != None:
            if current.getNext() == None:
                print (current.getData(), end='->')
            else:
                print (current.getData(), end='<->')
            current = current.getNext()
        print ('None')
    def isEmpty(self):
        return self.head == None
        
    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        temp.setPrev(None)
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            print('adding',item)
            if current.getData() <= item:
                stop = True
            else:
                previous = current
                current = current.getNext()
            
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)        
        
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count
    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 remove(self,item):
        current = self.head
        previous = None
        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:
                    previous = current
                    current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            if current == None:
                previous.setNext(None)
            else:
                previous.setNext(current.getNext())
        if current is None:
            print("Data not in list")

def autoInsert(mylist,alist):
    for i in alist:
        mylist.add(i)

mylist = OrderedList()
alist = [1,2,3,4,5,6,7,8,9,10]
autoInsert(mylist,alist)
mylist.show()
print('Panjang List =',mylist.size())
print('found',mylist.search(3))
print('found',mylist.search(3.5))
mylist.remove(10)
mylist.show()


Hasil Run :


Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
============ RESTART: /home/rejeb/Downloads/2DoubleLinkMenurun.py ============
adding 2
adding 3
adding 4
adding 5
adding 6
adding 7
adding 8
adding 9
adding 10
None <-head -="">10 <-> 9 <-> 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1-> None
Panjang List = 10
found True
found False
None <-head -="">9 <-> 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1-> None
>>>

Comments

Post a Comment

Popular posts from this blog

Searching - Linier Search & Binary Search Python

Image
Kelompok: Sitti Suwaibah (170411100009) Wijanarko Putra Rajeb (170411100061)  Assalamualaikum Wr. Wb. Kali ini kita akan membagikan Materi dan beberapa script python tentang linier search dan binary search. Berikut scriptnya: ### Mencari Keberadaan Suatu Angka di Dalam List Data ### A. Metode Linier Search Linear search merupakan program search yang mudah dipahami, linear search memiliki kelebihan apabila data yang di cari letaknya pada data – data awal sehingga prosesnya berjalan cepat, namun apabila data yang di cari letaknya pada data terakhir maka pencarian lebih memakan waktu yang cukup lama pula. karena di linear search mengunjungi setiap elemen data yang ada.   1. Biasa ### myList = [1,5,10,15,20,25,30,2,6,8,9] # Example List cari = int(input("Masukkan Angka Yang Anda Cari : ")) # angka yang ingin dicari counter = 0 while counter != len(myList): if myList[counter] == cari: print("Found The Search Number.",counter) cou
Read more

Sorting Data 1 - Bubble Sort dan Selection Sort

Image
Sorting adalah pengurutan data dimana di dalam sorting ituada 2 macam proses sorting. Ada bubble sort sama selection sort. 1. Bubble Sort Adalah algoritma pengurutan sederhana yang berulang kali melewati daftar yang akan diurutkan, membandingkan setiap pasangan item yang berdekatan dan menukar mereka jika mereka berada di urutan yang salah. def BubbleSort(val): counter = 0 for passnum in range(len(val)-1,0,-1): for i in range(passnum): counter += 1 if val[i]>val[i+1]: val[i],val[i+1] = val[i+1],val[i] print(val) print('jumlah iterasinya',counter) DaftarAngka = [23,7,32,99,4,15,11,20] BubbleSort(DaftarAngka) Video Tutorial Bubble Sort https://goo.gl/r8EAA5 2. Selection Sort Menemukan nilai minimum dalam array dan memindahkannya ke posisi pertama. Langkah ini adalah pengulangan untuk nilai terendah kedua, lalu yang ketiga, dan seterusnya sampai array diurutkan. def SelectionSort(val):
Read more

Materi Hashing - Struktur Data

Image
Materi Hashing A. Pengertian      Hashing adalah proses pengindeksan dan pengambilan elemen (data) dalam struktur data untuk menyediakan cara yang lebih cepat untuk menemukan elemen menggunakan kunci hash. Hash Value=Key mod (n+1) B. Collision      Collision terjadi ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua dalam tabel hash. Memecahkan: - Open Addressing : dalam hal itu mencoba untuk menemukan slot atau alamat terbuka berikutnya di tabel hash. Linear Probbing : Kita melihat secara berurutan, slot demi slot, sampai kita menemukan posisi terbuka. Quadratic Probbing : Ini berarti bahwa jika nilai hash pertama adalah h, nilai berturut-turut adalah h + 1, h + 4, h + 9, h + 16. seterusnya - Closed Address (Separate Chaining)      Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linke
Read more