Pengertian, Jenis, Operasi, dan Contoh Program dalam Linked List

Linked List atau yang biasanya dikenal dengan sebutan senarai berantai merupakan 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 merupakan elemen yang berada pada posisi pertama dalam linked list. Sedangkan Tail merupakan elemen yang berada pada posisi terakhir dalam linked list.

Linked list terdapat beberapa jenis. Jenis jenis tersebut antara lain adalah single linked list, double linked list, circular linked list, dan multiple linked list.

• Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Dan biasanya  field pada tail simpul menunjuk ke NULL.

• Double Linked List

Double Linked List merupakan suatu Linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya.Setiap Head dan tail juga menunjuk ke NULL.

• Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail menunjuk ke head. Jadi tidak ada pointer yang menunjuk ke NULL.

• Multiple Linked List

Multiple Linked list merupakan suatu linked list yang mempunyai lebih dari 2 buah variable pointer.

Di dalam Linked list juga terdapat beberapa operasi didalamnya. Operasi operasi tersebut antara lain

• Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

• IsEmpty

Fungsi ini digunakan untuk menentukan apakah linked list kosong atau tidak.

• Find First

Fungsi ini digunaka untuk mencari elemen pertama dari linked list

• Find Next

Fungsi ini digunaka untuk mencari elemen sesudah elemen yang ditunjuk now

• Retrieve

Fungsi ini merupakan fungsi untuk mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

• Update

Fungsi ini merupakan fungsi untuk mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

• Delete Now

Fungsi ini digunakan untuk menghapus elemen yang ditunjuk. Jika yang dihapus

adalah elemen pertama dari linked list atau head, head akan berpindah ke

elemen berikut.

• Delete Head

Fungsi ini merupakan fungsi untuk menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

• Clear

Fungsi ini merupakan fungsi untuk menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan

bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda

melakukannya, data-data yang dialokasikan ke memori pada program

sebelumnya akan tetap tertinggal di dalam memori.

contoh algoritma dan program linked list.

• Single Linked List
#include <iostream>

using namespace std;

struct Node{

int data;

Node* next;

};

//inisialisasi hanya untuk node pertama

void initNode(struct Node *head,int n){

head->data = n;

head->next =NULL;

}

//fungsi menambahkan node

void addNode(struct Node *head,int n){

Node *newNode = new Node;

newNode->data = n;

newNode->next =NULL;

Node *cur = head;

while(cur){

if(cur->next==NULL){

cur->next= newNode;

return;

}

cur = cur->next;

}

}

//insert node dari depan

void insertFront(struct Node **head, int n){

Node *newNode = new Node;

newNode->data = n;

newNode->next =*head;

*head = newNode;

}

struct Node *searchNode(struct Node *head,int n){

Node *cur = head;

while(cur){

if(cur->data == n)return cur;

cur = cur->next;

}

cout<<" Tidak ada Node "<< n <<" Pada list \n:";

}

bool deleteNode(struct Node **head,Node *ptrDel){

Node *cur = *head;

if(ptrDel== *head){

*head = cur->next;

delete ptrDel;

return true;

}

while(cur){

if(cur->next == ptrDel){

cur->next = ptrDel->next;

delete ptrDel;

return true;

}

cur = cur->next;

}

return false;

}

void display(struct Node *head){

Node *list =head;

while(list){

cout<< list->data<<" ";

list = list->next;

}

cout<<"\n\n";

}

int main(){

struct Node *newHead;

struct Node *head = new Node;

cout<<"LINKED LIST \n=========================\n\n";

initNode(head,10);

cout<<"Node Awal : ";

display(head);

addNode(head,20);

cout<<"Tambah 20: ";

display(head);

addNode(head,30);

cout<<"Tambah 30: ";

display(head);

addNode(head,35);

cout<<"Tambah 35: ";

display(head);

addNode(head,40);

cout<<"Tambah 40: ";

display(head);

insertFront(&head,5);

cout<<"Insert depan 5: ";

display(head);

int numDel = 35;

Node *ptrDelete = searchNode(head,numDel);

if(deleteNode(&head,ptrDelete))

cout<<"setelah Node "<< numDel<<" dihapus!\n";

display(head);

return 0;

}

 setelah program dijalankan maka output yang keluar adalah

• Double Linked List
#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int pil;

void pilih();

void buat_baru();

void tambah_depan();

void hapus_depan();

void tampil();

struct node{

char nama[20];

int nim;

char asal[30];

node *prev, *next;

};

node *baru, *head=NULL, *tail=NULL,*hapus,*bantu;

int main(){

do{

system("CLS");

cout<<"DOUBLE LINKEDLIST "<<endl;

cout<<"=========================\n";

cout<<"1. Penambahan Depan"<<endl;

cout<<"2. Hapus Depan"<<endl;

cout<<"3. Tampilkan"<<endl;

cout<<"4. Keluar"<<endl;

cout<<"Pilihan : ";cin>>pil;

pilih();

}

while(pil!=4);

}

void pilih(){

if(pil==1)

tambah_depan();

else if(pil==2)

hapus_depan();

else if(pil==3)

tampil();

else

cout<<"selesai";

}

void buat_baru(){

baru =new(node);

cout<<"Nama \t: ";cin>>baru->nama;

cout<<"Nim \t: ";cin>>baru->nim;

cout<<"Asal \t: ";cin>>baru->asal;

baru->prev=NULL;

baru->next=NULL;

}

void tambah_depan(){

buat_baru();

if(head==NULL){

head=baru;

tail=baru;

}else{

baru->next=head;

head->prev=baru;

head=baru;

}

cout<<endl<<endl;

tampil();

}

void hapus_depan() {

if (head==NULL)

cout<<"Kosong";

else if(head->next==NULL){

hapus=head;

head=NULL;

tail=NULL;

delete hapus;

}else {

hapus=head;

head=hapus->next;

head->prev=NULL;

delete hapus;

}

cout<<endl<<endl;

tampil();

}

void tampil(){

if (head==NULL)

cout<<"Kosong";

else {

bantu=head;

while(bantu!=NULL){

cout<<" Nama \t: "<<bantu->nama<<" | ";

cout<<" NIM \t: "<<bantu->nim<<" | ";

cout<<" Asal \t: "<<bantu->asal<<" | "<<endl;

bantu=bantu->next;

}

}

getch();

}

Setelah program dijalankan maka output yang akan muncul adalah

referensi:
http://suciantinovi.blogspot.co.id/2014/03/linked-list-i_14.html
http://vannyjw030911.blogspot.co.id/2013/04/operasi-didalam-linked-list.html
Wantoro, Jan, dan Sukirman.2017. Algoritma & Struktur Data dalam Bahasa C++. Surakarta:MUP.