Linked list

Dalam ilmu computer, Linked list adalah kumpulan linier elemen data, yang urutannya tidak diberikan oleh penempatan fisik mereka dalam memori. Sebaliknya, setiap elemen menunjuk ke yang berikutnya. Ini adalah struktur data yang terdiri dari kumpulan node yang bersama-sama mewakili urutan . Dalam bentuknya yang paling mendasar, setiap simpul berisi: data , dan referensi (dengan kata lain, tautan ) ke simpul berikutnya dalam urutan. Struktur ini memungkinkan penyisipan atau penghapusan elemen yang efisien dari posisi apa pun dalam urutan selama iterasi. Varian yang lebih kompleks menambah tautan tambahan, yang memungkinkan penyisipan atau penghapusan node yang lebih efisien pada posisi sewenang-wenang. Kelemahan dari linked list adalah bahwa waktu akses adalah linier (dan sulit untuk disalurkan ). Akses yang lebih cepat, seperti akses acak, tidak layak. Array memiliki lokalitas cache yang lebih baik dibandingkan dengan linked list.

 circuar single linked list

 Dalam singly linked list, untuk mengakses simpul mana pun dari daftar tertaut, kita mulai melintasi dari simpul pertama (first node). Jika kita berada pada titik di tengah daftar, maka tidak mungkin untuk mengakses node yang mendahului node yang diberikan. Masalah ini dapat diselesaikan dengan sedikit mengubah struktur singly linked list. Dalam singly linked list, bagian selanjutnya (pointer ke node berikutnya) adalah NULL, jika kita menggunakan tautan ini untuk menunjuk ke node pertama maka kita dapat mencapai node sebelumnya.

Struktur yang terbentuk adalah circular singly linked yang ditautkan melingkar seperti ini:

 






Penerapan  (Implementation)
Untuk menerapkan circular singly linked list, kami mengambil pointer eksternal yang menunjuk ke node terakhir dari daftar. Jika kita memiliki pointer terakhir yang menunjuk ke node terakhir, lalu terakhir -> selanjutnya akan menunjuk ke node pertama. 


Node dapat ditambahkan dengan empat cara:

• Insertion in an empty list
• Insertion at the beginning of the list
• Insertion at the end of the list
• Insertion in between the nodes

 doubly linked list

 Dalam ilmu komputer, doubly linked list adalah struktur data tertaut yang terdiri dari sekumpulan catatan yang terhubung secara berurutan yang disebut simpul. Setiap node berisi tiga bidang: dua bidang tautan (referensi ke simpul sebelumnya dan ke simpul berikutnya dalam urutan simpul) dan satu bidang data. Tautan awal dan akhir dari nodes 'sebelumnya dan selanjutnya, masing-masing, menunjuk ke semacam terminator, biasanya node atau null sentinel, untuk memfasilitasi traversal dari daftar. Jika hanya ada satu simpul sentinel, maka daftar itu terhubung secara melingkar melalui simpul sentinel. Ini dapat dikonseptualisasikan sebagai dua daftar tertaut tunggal yang dibentuk dari item data yang sama, tetapi dalam urutan berurutan yang berlawanan.

 contoh doubly linked list node di c:

 /* Node of a doubly linked list */
struct Node {
    int data;
    struct Node* next; // Pointer to next node in DLL
    struct Node* prev; // Pointer to previous node in DLL
};

doubly linked list: insert

Algorithm untuk memasukan node di bagian awal dari Doubly linked list

%% Input : head {A pointer pointing to the first node of the list}
Begin:
    alloc (newNode)
    If (newNode == NULL) then
        write ('Unable to allocate memory')
    End if
    Else then
        read (data)
        newNode.data ← data;
        newNode.prev ← NULL;
        newNode.next ← head;

        head.prev ← newNode;
        head ← newNode;
        write('Node added successfully at the beginning of List')
    End else
End

Algorithm untuk memasukan node di bagian akhir dari Doubly linked list

%% Input : last {Pointer to the last node of doubly linked list}
Begin:
    alloc (newNode)
    If (newNode == NULL) then
        write ('Unable to allocate memory')
    End if
    Else then
        read (data)
        newNode.data ← data;
        newNode.next ← NULL;
        newNode.prev ← last;
        
        last.next ← newNode;
        last ← newNode;
        write ('Node added successfully at the end of List')
    End else
End

Algorithm untuk memasukan node dimanapun dari Doubly linked list

%% Input : head {Pointer to the first node of doubly linked list}
        : last {Pointer to the last node of doubly linked list}
        : N {Position where node is to be inserted}
Begin:
    temp ← head
    For i←1 to N-1 do
        If (temp == NULL) then
            break
        End if
        temp ← temp.next;
    End for
    If (N == 1) then
        insertAtBeginning()
    End if
    Else If (temp == last) then
        insertAtEnd()
    End if
    Else If (temp != NULL) then
        alloc (newNode)
        read (data)
        
        newNode.data ← data;
        newNode.next ← temp.next
        newNode.prev ← temp
        If (temp.next != NULL) then
            temp.next.prev ← newNode;
        End if
        temp.next ← newNode;
        write('Node added successfully')
    End if
End

 doubly Linked List: Delete

Algorithm untuk menghapus node di awal doubly linked list

%% Input: head {Pointer to first node of the linked list}
Begin:
    If (head == NULL) then
        write ('Can't delete from an empty list')
    End if
    Else then
        toDelete ← head;
        head ← head.next;
        head.prev ← NULL;
        unalloc (toDelete)
        write ('Successfully deleted first node from the list')
    End if
End

Algorithm untuk menghapus node di akhir doubly linked list

%% Input: last {Pointer to last node of the linked list}
Begin:
    If (last == NULL) then
        write ('Can't delete from an empty list')
    End if
    Else then
        toDelete ← last;
        last ← last.prev;
        last.next ← NULL;
        unalloc (toDelete)
        write ('Successfully deleted last node from the list')

    End if
End

Algorithm untuk menghapus node dimanapun dari doubly linked list

%% Input : head {Pointer to the first node of the list}
         last {Pointer to the last node of the list}
         N {Position to be deleted from list}
Begin:
    current ← head;
    For i ← 1 to N and current != NULL do
        current ← current.next;
    End for
    If (N == 1) then
        deleteFromBeginning()
    End if
    Else if (current == last) then 
        deleteFromEnd()
    End if
    Else if (current != NULL) then
        current.prev.next ← current.next
        If (current.next != NULL) then
            current.next.prev ← current.prev;
        End if
        unalloc (current)
        write ('Node deleted successfully from ', N, ' position')
    End if
    Else then
        write ('Invalid position')
    End if
End

 

sumber:

https://en.wikipedia.org/wiki/Linked_list
https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/
https://en.wikipedia.org/wiki/Doubly_linked_list
https://www.geeksforgeeks.org/doubly-linked-list/
https://codeforwin.org/2015/10/c-program-to-insert-node-in-doubly-linked-list.html
https://codeforwin.org/2015/10/c-program-to-delete-node-from-doubly-linked-list.html