Tag Archive: double linked list


Selamat siang semua,,

kali ini saya akan mencoba posting sebuah program QUEUE tak terbatas menggunakan double linked list.

Double Linked List yaitu sebuah linked list yang mempunyai satu atau lebih data dengan 2 penunjuk, yaitu penunjuk simpul sebelum dan penunjuk simpul sesudah.

Akan saya definisikan terlebih dahulu struktur sebuah double linked list (DNode) sebagai berikut :

typedef int itemtype;
typedef struct simpul dnode;
struct simpul
{
	itemtype data;
	dnode *prev;
	dnode *next;
};

Dan membuat sebuah rumusan QUEUE juga sebagai penunjuknya sebagai berikut :

typedef struct
{
	dnode *front;
	dnode *rear;
} queue;

Setiap membuat linked list diperlukan sebuah fungsi untuk meng alokasikan ke memori. fungsi tersebut bisa menggunakan seperti biasanya :

void alokasi_node(itemtype x)
{
	baru = (dnode *) malloc(sizeof(dnode));
	if(baru==NULL)
	{
		printf("Alokasi GAGAL\n");
		exit(1);
	}
	else
	{
		baru->data = x;
		baru->next = NULL;
		baru->prev = NULL;
	}
}

Dan jangan lupa untuk membuat sebuah variabel global yaitu :

dnode *baru;

Lalu buat beberapa fungsi untuk queue yaitu fungsi inisialisasi, kosong, enqueue, dequeue. contohnya sebagai berikut :

void inisialisasi(queue *q)
{
	q->front = NULL;
	q->rear = NULL;
}

int kosong(queue *q)
{
	return (q->front==NULL && q->rear==NULL);
}

void enqueue(queue *q, itemtype x)
{
	if(kosong(q))
	{
		q->front = baru;
		q->rear = baru;
		printf("Anda Telah Menginput Data Pertama\n");
	}
	else
	{
		baru->prev = q->rear;
		q->rear->next = baru;
		q->rear = baru;
	}
}

itemtype dequeue(queue *q)
{
	dnode *temp;
	if(kosong(q))
	{
		printf("Data Kosong\n");
		return -1000;
	}
	else
	{
		temp = q->front;
		if(q->front==q->rear)
		{
			q->front=NULL;
			q->rear=NULL;
		}
		else
		{
			q->front = q->front->next;
			q->front->prev = NULL;
		}
		return temp->data;
		free(temp);
		temp = NULL;
	}
}

Dan untuk menampilkan data queue yang ada gunakan fungsi tampil seperti dibawah ini :

void tampil(queue *q)
{
	queue temp;
	temp = *q;
	printf("\nData Simpul ==> ");
	while(temp.front!=NULL)
	{
		printf("%d ", temp.front->data);
		temp.front = temp.front->next;
	}
	printf("\n\n");
}

Dan untuk main() bisa direpresentasikan seperti dibawah ini :

void main()
{
	char lagi='y';
	queue simpul;
	itemtype data;
	int pil;
	inisialisasi(&simpul);
	while(lagi=='y' || lagi=='Y')
	{
		system("CLS");
		tampil(&simpul);
		printf("Menu :\n");
		printf("1. Enqueue\n");
		printf("2. Dequeue\n");
		printf("Masukkan pilihan : ");
		scanf("%d", &pil);
		switch(pil)
		{
		case 1 :
			printf("Masukkan data : ");
			scanf("%d", &data);
			alokasi_node(data);
			enqueue(&simpul, data);
			break;
		case 2 :
			dequeue(&simpul);
			break;
		default :
			printf("Pilihan salah\n");
			break;
		}
		fflush(stdin);
		printf("Lagi (y/n) ? ");
		scanf("%c", &lagi);
	}
}

Untuk mendownload contoh program disini

Jika ada yang kurang mengerti dengan program seperti diatas, bisa ditanyakan langsung. tinggalkan komentar anda, kirim pesan email, dan apa saja boleh yang penting bisa bertanya 😀 😀 hehe

Semoga bermanfaat.

Program Double Linked List pada C++

Double Linked List adalah :

Sebuah struktur data yang memiliki 2 pointer penunjuk, sehingga bisa saling terhubung antara elemen satu dengan elemen lainnya.

dengan menggunakan struktur data seperti berikut :

  • data
  • pointer penunjuk elemen setelahnya (next)
  • pointer penunjuk elemen sebelumnya (prev)

Linked List biasa disebut simpul atau node.

dalam program ini diperlukan beberapa library yaitu :

#include<stdio.h>
#include<stdlib.h>

untuk merepresentasikannya bisa seperti ini

typedef struct simpul node;
struct simpul
{
	int data;
	node *prev;
	node *next;
};

lalu membuat variabel global untuk head, tail, dan baru

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

lalu buat fungsi untuk alokasi memori, dan disini diperlukan stdlib.h

void allocate_node (int x)
{
	baru = (node *) malloc (sizeof(node));
	if(baru==NULL)
	{
		printf("Alokasi Gagal\n");
		exit(1);
	}
	else
	{
		baru->data=x;
		baru->next=NULL;
		baru->prev=NULL;
	}
}

setelah simpul baru dialokasikan, maka simpul baru bisa dibuat :

	head = tail = baru;

ada beberapa fungsi yang diperlukan untuk menambahkan (menyisipkan) simpul baru, yaitu :

  • sisip awal
  • sisip akhir
  • sisip sebelum
  • sisip sesudah

dan untuk menghapus simpul, diperlukan beberapa fungsi, yaitu :

  • hapus awal
  • hapus akhir
  • hapus simpul

Untuk menyisipkan fungsi-fungsinya adalah :

  • fungsi buat list
void buat_list()
{
	printf("Data Masih Kosong, List akan dibuat dengan data tersebut\n");
	system("PAUSE");
	head = tail = baru;
}
  • fungsi sisip awal
void sisip_awal()
{
	if(head==NULL && tail==NULL)
		buat_list();
	else
	{
		baru->next=head;
		head->prev=baru;
		head=baru;
	}
}
  • fungsi sisip akhir
void sisip_akhir()
{
	if(head==NULL && tail==NULL)
		buat_list();
	else
	{
		baru->prev=tail;
		tail->next=baru;
		tail=baru;
	}

}
  • fungsi sisip sebelum
void sisip_sebelum(int s)
{
	node *before=head;
	int cek=0;
	if(before->next==NULL)
		cek=1;
	else
	{
		while(before->next->data!=s)
		{
			before=before->next;
			if(before->next==NULL)
			{
				cek = 1;
				break;
			}
		}
	}
	if(cek==0)
	{
		baru->prev = before;
		baru->next = before->next;
		before->next->prev = baru;
		before->next = baru;
	}
	else
		gatot();
}
  • fungsi sisip sesudah
void sisip_sesudah(int s)
{
	node *after=tail;
	int cek=0;
	if(after->prev == NULL)
		cek=1;
	else
	{
		while(after->prev->data!=s)
		{
			after=after->prev;
			if(after->prev==NULL)
			{
				cek = 1;
				break;
			}
		}
	}
	if(cek==0)
	{
		baru->next = after;
		baru->prev = after->next;
		after->prev->next = baru;
		after->prev = baru;
	}
	else
		gatot();
}

Lalu untuk menghapus diperlukan beberapa fungsi, yaitu :

  • hapus simpul
void free_node(node *p)
{
	free(p);
	p=NULL;
	printf("DATA TERHAPUS\n");
}
  • hapus satu
void hapus_satu()
{
	node *hapus = head;
	head = NULL;
	tail = NULL;
	free_node(hapus);
}
  • hapus awal
void hapus_awal()
{
	node *hapus = head;
	head->next->prev = NULL;
	head =  head->next;
	free_node(hapus);
}
  • hapus akhir
void hapus_akhir()
{
	node *hapus = tail;
	tail->prev->next = NULL;
	tail =  tail->prev;
	free_node(hapus);
}
  • hapus simpul tertentu
void hapus_tengah(int s)
{
	node *hapus=head;
	int cek=0;
	while(hapus->data!=s)
	{
		if(hapus->next==NULL)
		{
			cek=1;
			break;
		}
		hapus = hapus->next;
	}
	if(cek==0)
	{
		hapus->prev->next = hapus->next;
		hapus->next->prev = hapus->prev;
		free_node(hapus);
	}
	else
		gadel();
}

untuk menampilkan pesan diperlukan fungsi tambahan :

void gatot()
{
	printf("SIMPUL BARU TIDAK DAPAT DISISIPKAN\n");
	system("PAUSE");
}

void gadel()
{
	printf("TIDAK ADA DATA YANG DIHAPUS\n");
	system("PAUSE");
}

Dan juga untuk menampilkan data yang berada pada list bisa di representasikan seperti ini :

void tampil()
{
	node *p= head;
	printf("\nData Simpul ==>  ");
	while(p!=NULL)
	{
		printf("%d ", p->data);
		p=p->next;
	}
	printf("\n\n");
}

Dan pada main bisa menggunakan code seperti ini :

void main()
{
	head=baru;
	int pilih, data, s;
	char lagi='y';
	while(lagi=='y')
	{
		system("CLS");
		awal();
		tampil();
		printf("Menu Pilihan : \n");
		printf("1. Sisip Awal\n");
		printf("2. Sisip Akhir\n");
		printf("3. Sisip Sebelum Simpul\n");
		printf("4. Sisip Sesudah Simpul\n");
		printf("5. Hapus Awal\n");
		printf("6. Hapus Akhir\n");
		printf("7. Hapus Tengah\n");
		printf("\nPilih No            : ");
		scanf("%d", &pilih);
		switch(pilih)
		{
		case 1 :
			printf("Masukkan data       : ");
			scanf("%d", &data);
			allocate_node(data);
			sisip_awal();
			break;
		case 2 :
			printf("Masukkan data       : ");
			scanf("%d", &data);
			allocate_node(data);
			sisip_akhir();
			break;
		case 3 :
			printf("Masukkan data       : ");
			scanf("%d", &data);
			allocate_node(data);
			if(head==NULL && tail==NULL)
				buat_list();
			else
			{
				printf("Dimasukkan sebelum  : ");
				scanf("%d",&s);
				if(s==head->data)
					sisip_awal();
				else
					sisip_sebelum(s);
			}
			break;
		case 4 :
			printf("Masukkan data       : ");
			scanf("%d", &data);
			allocate_node(data);
			if(head==NULL && tail==NULL)
				buat_list();
			else
			{
				printf("Dimasukkan sesudah  : ");
				scanf("%d",&s);
				if(s==tail->data)
					sisip_akhir();
				else
					sisip_sesudah(s);
			}
			break;
		case 5 :
			if(head == NULL && tail == NULL)
				gadel();
			else if(head == tail)
				hapus_satu();
			else
				hapus_awal();
			break;
		case 6 :
			if(head == NULL && tail == NULL)
				gadel();
			else if(head == tail)
				hapus_satu();
			else
				hapus_akhir();
			break;
		case 7 :
			printf("Data yang dihapus   : ");
			scanf("%d", &data);
			if(head == NULL && tail == NULL)
				gadel();
			else if(data == head->data && data == tail->data && head == tail)
				hapus_satu();
			else if(data == head->data)
				hapus_awal();
			else if(data == tail->data)
				hapus_akhir();
			else
				hapus_tengah(data);
			break;
		}
		fflush(stdin);
		printf("Lagi (y/t) ? ");
		scanf("%c", &lagi);
	}
}

system(“PAUSE”) digunakan untuk menghentikan program sejenak.
system(“CLS”) digunakan untuk menghapus layar.
kedua command tersebut membutuhkan <stdlib.h> sama hal nya dengan penggunaan alokasi memori yang menggunakan malloc() , sizeof() , dan free() .

untuk download programnya bisa di download DISINI