Struktur Data – Double Linked List dengan Bahasa C

Mahir Koding – Double Linked List adalah salah satu contoh lain implementasi linked list selain single linked list yang telah kita bahas di tutorial sebelumnya. Sesuai namanya, Double artinya blok data yang kita miliki akan memiliki 2 penunjuk kiri dan kanan untuk menentukan data sebelum/sesudahnya. Berbeda dengan single linked list yang hanya mempunyai satu penunjuk, double linked list mempunyai 2 penunjuk kiri dan kanan untuk menentukan urutan datanya. Agar lebih paham, bisa perhatikan gambar di bawah ini :

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 pembuatan double 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 dan sebelumnya
	human *next, *prev;
}*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 variabel

Push Head

void pushHead(int age, char name[]){
	//membuat blok data baru
	current = (struct human *)malloc(sizeof human);
	//mengisi data
	strcpy(current->name, name);
	current->age=age;
	//membuat penunjuk data lain menjadi NULL terlebih dahulu
	current->next = current->prev=NULL;

	//jika tidak ada data
	if(head==NULL){
		//maka akan jadi data pertama, head dan tail akan sama dengan data baru
		head=tail=current;
	//jika ada data
	}else{
		//pergantian head menjadi data terbaru
		head->prev=current;
		current->next=head;
		head=current;
	}
}

Push Tail

void pushTail(int age, char name[]){
	//membuat blok data baru
	current = (struct human *)malloc(sizeof human);
	//mengisi data
	strcpy(current->name, name);
	current->age = age;
	//membuat penunjuk data lain menjadi NULL terlebih dahulu
	current->prev = current->next = NULL;

	//jika tidak ada data
	if(head==NULL){
		//maka akan jadi data pertama, head dan tail akan sama dengan data baru
		head=tail=current;
	//jika ada data
	}else{
		//pergantian tail menjadi data terbaru
		current->prev = tail;
		tail->next = current;
		tail = current;
	}
}

Push Mid – Mengurutkan sesuai umur

void PushMid(int age, char name[]){
	//jika tidak ada data
	if(head==NULL){
		//pushHead
		pushHead(age,name);
	//jika umur yang akan dimasukkan lebih kecil dari umur data ke head
	}else if(age < head->age){
		//pushHead
		pushHead(age,name);
	//jika umur yang akan dimasukkan lebih kecil dari umur data ke tail
	}else if(age > tail->age){
		//pushTail
		pushTail(age,name);
	}else{
		//buat blok data
		current = (struct human *)malloc(sizeof human);
		//mengisi data
		strcpy(current->name, name);
		current->age = age;
		//buat penunjuk data sebelum/sesudahnya menjadi NULL terlebih dahulu
		current->next = current->prev = NULL;
		
		struct human *temp=head;
		//mencari posisi dimana data akan dimasukkan
		while(temp!=NULL && temp->age < current->age){
			temp=temp->next;
		}
		//memasukkan data dan menunjuk alamat-alamat data selanjutnya/sebelumnya
		current->prev=temp->prev;
		current->next=temp;

		temp->prev->next=current;
		temp->prev=current;
	}
}

Pop Head

void popHead(){
	//jika tidak ada data
	if(head==NULL){
		printf("No Data\n");
	//jika hanya ada 1 data
	}else if(head==tail){
		current=head;
		head=tail=NULL;
		free(current);
	//jika lebih dari 1 data
	}else{
		current=head;
		head=head->next;
                head->prev=NULL;
		free(current);
	}
}

Pop Tail

void popTail(){
	//jika tidak ada data
	if(head==NULL){
		printf("No Data\n");
	//jika hanya ada 1 data
	}else if(head==tail){
		current=tail;
		head=tail=NULL;
		free(current);
	//jika lebih dari 1 data
	}else{
		current=tail;
		tail=tail->prev;
                tail->next=NULL;
		free(current);
	}
}

Pop Mid – Mencari umur yang ingin dihapus

void popMid(int age){
	//inisialisasi flag sebagai penanda eksistensi data
	int temu=0;
	//jika tidak ada data
	if(head==NULL){
		printf("No Data\n");
	//jika ada data
	}else{
		current=head;
		//mencari posisi data
		while(current!=NULL){
			//pengecekan data,jika sesuai, ubah flag dan langsung break looping
			if(current->age==age){
				temu=1;
				break;
			}
			current=current->next;
		}
		//jika data ketemu
		if(temu==1){
			//jika hanya data yang ditemukan adalah Head
			if(current==head){
				popHead();
			//jika hanya data yang ditemukan adalah Tail
			}else if(current==tail){
				popTail();
			//jika hanya data yang ditemukan bukan Head dan bukan Tail
			}else{
				current->prev->next=current->next;
				current->next->prev=current->prev;
				free(current);
			}
		}else{
			printf("Data Not Found\n");
		}
	}
}

Pop All – Menghapus semua data

void popAll(){
	while(head!=NULL){
		popHead();
	}
}

Print Data

void print(){
	current=head;
	if(current!=NULL){
		while(current!=NULL){
			printf("Name : %s | Age : %d\n", current->name, current->age);
			current=current->next;
		}
	}else{
		printf("No Data\n");
	}
}

Main Function

void main(){
	pushHead(23, "Hery");
	pushHead(20, "Budi");
	pushHead(13,"Tono");
	pushHead(11, "Andi");
	pushTail(15, "MahirKoding");
	PushMid(17, "Budi");
	popMid(11);
	//popMid(6);
	//popAll();
	print();
	getchar();
}

Source code secara lengkap bisa dicek ke github saya, di link ini.

Jika ada pertanyaan yang kurang jelas silahkan berkomentar di bawah. Atau, jika ingin request tutorial juga dapat ke halaman ini. Dukung terus Mahir Koding agar dapat selalu mengupdate artikel dengan share dan like artikel ini. Terima Kasih.


Notice: Undefined offset: 0 in /var/www/mahirkoding/wp-content/themes/portus-premium-theme/includes/single/about-author.php on line 25