Linked List
- adamfadilah678
- Feb 26, 2020
- 4 min read
Apa Itu Linked List?
Linked List adalah bagian dari Struktur Data
Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimoan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node. Biasanya didalam suatu lnked list, terdapat istilah head and tail.
• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
• Tail adalah element yang berada pada posisis terakhir dalam suatu linked list
Linked List terbagi menjadi 4 Bagian, yaitu:
Single Linked List
Double Linked List
Circular Linked List
Multiple Linked List
Jadi di kesempatan kali ini saya akan menjelaskan macam-macam Linked List.
• Single Linked List
Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL
Contoh :
Dalam pembelajaran struktur data, kita akan lebih sering mengenal dengan istilah :
Push untuk menambah data.
PushHead – Menambah data ke barisan paling awal
PushTail – Menambah data ke barisan paling akhir
PushMid – Menambah data ke barisan di tengah (sorting)
Pop untuk menghapus data.
PopHead – Menghapus data paling awal
PopTail – Menghapus data paling akhir
PopMid – Menghapus data ditengah (sesuai parameter value).
Contoh Deklarasi Struct Linked List untuk menyimpan nama seseorang beserta umurnya.
Deklarasi Struct
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct human{
//menampung integer umur
int age;
//menampung nama manusia
char name[30];
//menampung alamat dari data selanjutnya
human *next;
}*head, *tail, *current;
//head adalah pointer yang menyimpan alamat data pertama
//tail adalah pointer yang menyimpan alamat data terakhir
//current adalah pointer yang digunakan sebagai temporary variabelPush Head
void pushHead(int age, char name[]){
//alokasi memory untuk data baru
current = (human*)malloc(sizeof(struct human));
//assign data ke dalam struct
current->age = age;
strcpy(current->name, name);
//apabila linked list kosong/tidak ada data
if(head == NULL){
head = tail = current;
}
//kondisi tidak kosong
else{
current->next = head;
head = current;
}
}Push Tail
void pushTail(int age, char name[]){
//alokasi memory untuk data baru
current = (human*)malloc(sizeof(struct human));
//assign data ke dalam struct
current->age = age;
strcpy(current->name, name);
//apabila linked list kosong/tidak ada data
if(head == NULL){
head = tail = current;
}
//kondisi tidak kosong
else{
tail->next = current;
tail = current;
}
tail->next = NULL;
}Push Mid
void pushMid(int age, char name[]){
//alokasi memory untuk data baru
current = (human*)malloc(sizeof(struct human));
//assign data ke dalam struct
current->age = age;
strcpy(current->name, name);
//apabila linked list kosong/tidak ada data
if(head == NULL){
head = tail = current;
}
//jika umur data yang barusan dimasukkan lebih kecil dari umur data pertama (head)
else if(current->age < head->age){
pushHead(age, name);
}
//jika umur data yang barusan dimasukkan lebih besar dari umur data terakhir (tail)
else if(current->age > tail->age){
pushTail(age, name);
}
//push ditengah-tengah
else{
human *temp = head;
//mencari posisi data yang sesuai untuk diselipkan
while(temp->next->age < current->age){
temp = temp->next;
}
current->next = temp->next;
//mengarahkan penunjuk ke alamat data baru
temp->next = current;
}
}Pop Head
void popHead(){
//inisialisasi current sebagai head
current=head;
//jika head kosong (tidak ada data)
if(head==NULL){
//cetak tidak ada data
printf("No data");
//jika head dan tail itu sama (hanya 1 data)
}else if(head==tail){
//head dan tail dikosongkan
head=tail=NULL;
//hapus data current (head)
free(current);
}else{
//set head menjadi data selanjutnya dari head
head=head->next;
//hapus data current (head)
free(current);
}
}Pop Tail
void popTail(){
//jika head kosong (tidak ada data)
if(head==NULL){
//cetak tidak ada data
printf("No data");
//jika head dan tail itu sama (hanya 1 data)
}else if(head==tail){
//head dan tail dikosongkan
head=tail=NULL;
//hapus data current (head)
free(current);
}else{
//buat variabel penampung baru dan assign nilai mulai dari head
human *temp=head;
//looping untuk mencari posisi 1 data sebelum tail
while(temp->next!=tail){
//temp diubah menjadi 1 data selanjutnya
temp=temp->next;
}
//set data current menjadi tail
current=tail;
//set tail menjadi 1 data sebelum tail (hasil looping)
tail=temp;
//hapus data current (tail)
free(current);
//data setelah next dikosongkan/pointer next punya tail diberi NULL
tail->next=NULL;
}
}Pop Mid
//kita akan menghapus data sesuai dengan umurnya.
void popMid(int age){
//jika head kosong (tidak ada data)
if(head==NULL){
printf("No data");
//jika umur si head(data pertama) sama dengan data umur yang mau dihapus
}else if(head->age==age){
//pop head
popHead();
//jika umur si tail(data terakhir) sama dengan data umur yang mau dihapus
}else if(tail->age==age){
//pop tail
popTail();
}else{
//buat variabel penampung baru dan assign nilai mulai dari head
human *temp=head;
//looping untuk mencari posisi 1 data sebelum tail
while(temp->next->age!=age && temp!=tail){
//temp diubah menjadi 1 data selanjutnya
temp=temp->next;
}
//set data current menjadi data selanjutnya dari temp
current=temp->next;
//data selanjutnya dari temp diubah menjadi 2 data setelah temp
temp->next=temp->next->next;
//hapus data current
free(current);
}
}Pop Mid
void popAll(){
while(head!=NULL){
popHead();
}
}Print Data
void print(){
current = head;
while(current != NULL){
printf("%s - %d\n",current->name,current->age);
current = current->next;
}
}Main Function
int main(){
pushMid(18, "hery");
pushMid(17, "mahirkoding");
pushTail(22, "andi");
pushHead(15, "tono");
pushMid(11, "vandoro");
pushMid(23, "budi");
popHead();
popTail();
popMid(15);
//popAll();
print();
getchar();
return 0;
}Double Linked List
Double Linked List Merupakan suatau linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
Contoh:
Contoh Program:
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int pil;
void pilih();
void buat_baru();
void tambah_belakang();
void tambah_depan();
void hapus_belakang();
void hapus_depan();
void tampil();
struct node
{
char nama [20];
int umur;
float tinggi;
node *prev, *next;
};
node *baru, *head=NULL, *tail=NULL,*hapus,*bantu;
void main()
{
do
{
clrscr();
cout<<"MENU DOUBLE LINKEDLIST"<<endl;
cout<<"1. Tambah Depan"<<endl;
cout<<"2. Tambah Belakang"<<endl;
cout<<"3. Hapus Depan"<<endl;
cout<<"4. Hapus Belakang"<<endl;
cout<<"5. Tampilkan"<<endl;
cout<<"6. Selesai"<<endl;
cout<<"Pilihan Anda : ";
cin>>pil;
pilih();
} while(pil!=6);
}
void pilih()
{
if(pil==1)
tambah_depan();
else if(pil==2)
tambah_belakang();
else if(pil==3)
hapus_depan();
else if(pil==4)
hapus_belakang();
else if(pil==5)
tampil();
else
cout<<"selesai";
}
void buat_baru()
{
baru = new(node);
cout<<"input nama : ";cin>>baru->nama;
cout<<"input umur : ";cin>>baru->umur;
cout<<"input tinggi : ";cin>>baru->tinggi;
baru->prev=NULL;
baru->next=NULL;
}
void tambah_belakang()
{
buat_baru();
if(head==NULL)
{
head=baru;
tail=baru;
}
else
{
tail->next=baru;
baru->prev=tail;
tail=baru;
}
cout<<endl<<endl;
tampil();
}
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 hapus_belakang()
{
if (head==NULL)
cout<<"Kosong";
else if (head->next==NULL)
{
hapus=head;
head=NULL;
tail=NULL;
delete hapus;
}
else
{
hapus=tail;
tail=hapus->prev;
tail->next=NULL;
delete hapus;
}
cout<<endl<<endl;
tampil();
}
void tampil()
{
if (head==NULL)
cout<<"Kosong";
else
{
bantu=head;
while(bantu!=NULL)
{
cout<<" nama : "<<bantu->nama;
cout<<" umur : "<<bantu->umur;
cout<<" tinggi : "<<bantu->tinggi<<endl;
bantu=bantu->next;
}
}
getch();
}
Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head(node pertama).Jadi tidak ada pointer yang menunjuk NULL ada 2 jenis Circular Linked List yaitu:
Circular Single Linked List:
2.Circular Double Linked List
Pada dua jenis senarai sebelumnya, node terakhir dalam senarai tersebut merujuk pada null yang artinya akhir dari sebuah senarai, begitu pula null sebagai rujukan node sebelumnya pada node pertama bila senarai yang dimaksudkan adalah Double Linked List. Pada Circular Linked List, informasi rujukan pada node terakhir akan merujuk pada node pertama, dan rujukan pada node pertama akan merujuk pada node terakhir bila yang digunakan sebagai dasar implementasi adalah Double Linked List.
Sekian penjelasan yang dapat saya berikan, Terimakasih.
Sumber:
https://www.mahirkoding.com/struktur-data-single-linked-list-dengan-bahasa-c/ http://alvinstrukturdata.blogspot.com/2016/01/apa-itu-linked-list.html
Comments