Summary of Data Struct

Nama : Michael
Nim : 2301864184

Single Linked List Circular

Single Linked List Circular adalah Single Linked List yang pointer selanjutnya menunjuk ke dirinya sendiri. Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke pointer terdepan.

          Single : artinya field pointer-nya hanya satu buah saja dan satu arah.

Circular : artinya pointer next-nya akan menunjuk ke dirinya sendiri sehingga akan membuat sebuah sirkuit atau sirkular

Ilustrasi

-         Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya yang juga memiliki field yang berisi data

-         Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head.

Rangkaian Single Linked List tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan diakhiri dengan node yang mengarah ke pointer null yang akan menunjuk ke salah satu node kembali.

Pengenalan Double Linked List

Pengertian Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. 

Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.

//
	// Created by rizki on 10/15/16.
	//
	#ifndef DOUBLE_LINKED_LIST_DOUBLE_LINKED_H
	#define DOUBLE_LINKED_LIST_DOUBLE_LINKED_H
	#include <stdlib.h>
	#include <iostream>
	//struktur tipe data
	typedef struct Node* address;
	struct Node{
	int data;
	address prev;
	address next;
	};
	struct List{
	address head;
	address tail;
	};
	//alokasi memori
	address allocate(Node n);
	//membuat list kosong, head(l) = null
	void createEmpty(List *l);
	// cek status kosong atau tidak
	bool isEmpty(List l);
	// cari elemen pada list berdasar data masukan, mengembalikan alamat node
	address findElm(int data, List l);
	// INSERT
	void insertFirst(List *l, Node n);
	void insertLast(List *l, Node n);
	void insertAfter(List *L, int data, Node n);
	void insertBefore(List *l, int data, Node n);
	void printForward(List l);
	void printBackward(List l);
	// DELETE
	void deleteFirst(List *l);
	void deleteLast(List *l);
	void deleteElm(List *l, Node node);
	#endif //DOUBLE_LINKED_LIST_DOUBLE_LINKED_H

view rawdouble_linked.h hosted with ❤ by GitHub

Implementasi Method dan Fungsi

Setelah header didefinisikan, terdapat implementasi double linked list dengan C++.

Contoh Program Utama

Berikut adalah contoh program utama untuk pengujian dan validasi implementasi double linked list. Program ini dapat dimodifikasi sesuai keinginan, kode yang saya tulis hanyalah contoh saja.

	#include <iostream>
	#include <stdlib.h>
	#include "double_linked.h"
	using namespace std;
	int main() {
	cout << "Doubly Linked List" << endl;
	address pointer;
	List list;
	Node node;
	createEmpty(&list);
	for(int i=0;i < 2;i++){
	node.data = i;
	insertFirst(&list,node);
	node.data = node.data + 1;
	insertLast(&list,node);
	}
	node.data = 4;
	insertAfter(&list,2,node);
	node.data = 5;
	insertAfter(&list,0,node);
	node.data = 3;
	insertBefore(&list,1,node);
	node.data = 6;
	insertBefore(&list,5,node);
	deleteFirst(&list);
	deleteLast(&list);
	node.data = 6;
	deleteElm(&list,node);
	node.data = 2;
	deleteElm(&list,node);
	node.data = 1;
	deleteElm(&list,node);
	cout << "Head : " << list.head->data << endl;
	cout << "Tail : " << list.tail->data << endl;
	printForward(list);
	printBackward(list);
	return 0;
	}

	//
	// Created by rizki on 10/15/16.
	//
	#include <stdlib.h>
	#include "double_linked.h"
	using namespace std;
	address allocate(Node n){
	address p = (address) malloc(sizeof(struct Node));
	p->data = n.data;
	p->prev = NULL;
	p->next = NULL;
	return p;
	}
	void createEmpty(List *l){
	l->head = NULL;
	l->tail = NULL;
	}
	bool isEmpty(List l){
	return l.head == NULL && l.tail == NULL;
	}
	address findElm(int data,List l){
	if (isEmpty(l))
	cout << "List kosong" << endl;
	else{
	address p = l.head;
	while (p->data!= data && p!=NULL)
	p = p->next;
	return p;
	}
	}
	void insertFirst(List *l, Node n){
	address p = allocate(n);
	if (isEmpty(*l)) {
	l->head = p;
	l->tail = p;
	} else{
	p->next = l->head;
	l->head->prev = p;
	l->head = p;
	}
	}
	void insertLast(List *l, Node n){
	address p = allocate(n);
	if(isEmpty(*l)){
	l->head = p;
	l->tail = p;
	} else{
	p->prev = l->tail;
	l->tail->next = p;
	l->tail = p;
	}
	}
	void insertAfter(List *l, int data, Node n){
	address prev = findElm(data,*l);
	address p = allocate(n);
	if(prev->next!=NULL){
	p->next = prev->next;
	p->prev = prev;
	prev->next = p;
	p->next->prev = p;
	} else{
	p->prev = prev;
	prev->next = p;
	l->tail = p;
	}
	}
	void insertBefore(List *l, int data, Node n){
	address elm = findElm(data,*l);
	address p = allocate(n);
	if(elm->prev!=NULL){
	p->next = elm;
	p->prev = elm->prev;
	elm->prev->next = p;
	elm->prev = p;
	} else{
	p->next = elm;
	elm->prev = p;
	l->head = p;
	}
	}
	void deleteFirst(List *l){
	if(isEmpty(*l))
	cout << "List kosong" << endl;
	else{
	address tmp = l->head;
	l->head->next->prev = NULL;
	l->head = l->head->next;
	free(tmp);
	}
	}
	void deleteLast(List *l){
	if(isEmpty(*l))
	cout << "List kosong" << endl;
	else{
	address tmp = l->tail;
	l->tail->prev->next = NULL;
	l->tail = l->tail->prev;
	free(tmp);
	}
	}
	void deleteElm(List *l,Node node){
	if(isEmpty(*l))
	cout << "List kosong" << endl;
	else{
	if(node.data == l->head->data)
	deleteFirst(l);
	else if(node.data == l->tail->data)
	deleteLast(l);
	else{
	address p = l->head;
	while (p!=NULL && p->data!=node.data)
	p = p->next;
	if(p!=NULL){
	p->prev->next = p->next;
	p->next->prev = p->prev;
	free(p);
	}
	}
	}
	}
	void printForward(List l){
	if(isEmpty(l))
	cout << "List kosong" << endl;
	else{
	address p = l.head;
	while (p!=NULL){
	cout << p->data << " ";
	p = p->next;
	}
	cout << endl;
	}
	}
	void printBackward(List l){
	if(isEmpty(l))
	cout << "List kosong" << endl;
	else{
	address p = l.tail;
	while (p!=NULL){
	cout << p->data << " ";
	p = p->prev;
	}
	cout << endl;
	}