Linked List

LINKED LIST

Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian.

Bentuk Umum :

typedef struct telmtlist
{
infotype info;
address next;
} elmtlist;

infotype :sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list.
next :address dari elemen berikutnya (suksesor).


Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :

first (L)

Sebelum digunakan harus dideklarasikan terlebih dahulu :

#define first (L) (L)

Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :

info (P) deklarasi #define info (P) (F)->info
next (P) deklarasi #define next (P) (P)->next



Beberapa Definisi :
1. List 1 adalah list kosong, jika First(L)=Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena Next(Last)=Nil.
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Jenis – jenis Linked List :
Single Linked List
Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node/simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memiliki nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).

Pembuatan Single Linked List dapat menggunakan 2 metode :
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)

LIFO (Last In First Out)
LIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling akhir adalah data yang keluar paling awal. Hal ini dapat di analogikan (dalam kehidupan sehari-hari) dengan saat anda menumpuk barang. Jika Linked List dibuat dengan metode LIFO, terjadi penambahan / Insert simpul di belakang, dikenal dengan istilah INSERT.

FIFO (First In First Out)
FIFO adalah suatu metode pembuatan Linked List di mana data yang masuk paling awal adalah data yang keluar paling awal juga. Hal ini dapat di analogikan (dalam kehidupan sehari-hari), misalnya saat sekelompok orang yang datang (ENQUEUE) mengantri hendak membeli tiket di loket. Jika Linked List dibuat dengan metode FIFO, terjadi penambahan / Insert simpul di depan.

Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, anda dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked List berpointer Ganda atau Double Linked List.


Circular Double Linked List
Ini adalah double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

Operasi-Operasi yang ada pada Linked List
Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.

Find First
Fungsi ini mencari elemen pertama dari linked list.

Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now.

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

Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.

Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

Clear
Fungsi ini 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 Program :

1. Single Linked List

#include <iostream.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>

#define Nil NULL
#define info (P) P->info
#define next (P) P->next
#define First (L) (L)

typedef int InfoType;
typedef struct telmtlist *address;
typedef struct telmtlist
{
InfoType info;
address next;
}elmtlist;

typedef address list;

void CiptaSenarai (list *L)
{
First (*L) = Nil;
}

list NodBaru(int m)
{
list n;
n = (list) malloc(sizeof(elmtlist));
if (n != NULL)
{
info(n) = m;
next(n) = Nil;
}

return n;
}

void SisipSenarai (list *L, list t, list p)
{
if (p == Nil)
{
t->next = *L;
*L = t;
}
else
{
t->next = p->next;
p->next = t;
}
}

void CetakSenarai (list L)
{
list ps;
for (ps=L; ps!=Nil; ps=ps->next)
{
cout<<” “<<<” --> “;
}
cout<<” NULL”<<<”Masukkan Banyak Data = “; cin>>k;
for (i=1; i<=k; i++) { cout<<”Masukkan Data Senarai ke-“<<<” = “; cin>>nilai;
n = NodBaru(nilai);
SisipSenarai (&pel, n, NULL);
}

CetakSenarai(pel);
return 0;
}

2. Double Linked List

#include <iostream.h>

class node
{
public:
int value; //value stored in the node
node *next; //pointer to next node
node *prev; //pointer to previous node
};

class dlist
{
public:
node *front; //pointer to front of list
node *back; //pointer to back of list

dlist()
{
front=NULL;
back=NULL;
}

void insertFront(int value);
void insertBack(int value);
void removeFront();
void removeBack();
void insertBefore(int value,node *nodeB);
void insertAfter(int value,node *nodeA);
void removeBefore(node *nodeB);
void removeAfter(node *nodeA);
void removeNode(node *newNode);
void printDListFront();
void printDListBack();
};

//insert a node before nodeB
void dlist::insertBefore(int value,node *nodeB)
{
node *newNode;
newNode=new node();
newNode->prev=nodeB->prev;
newNode->next =nodeB;
newNode->value =value;
if(nodeB->prev==NULL)
{
this->front=newNode;
}
nodeB->prev=newNode;
removeNode(newNode);

}

//insert a node before the front node
void dlist::insertFront (int value)
{
node *newNode;
if(this->front==NULL)
{
newNode=new node();
this->front=newNode;
this->back =newNode;
newNode->prev=NULL;
newNode->next=NULL;
newNode->value=value;

}
else
{
insertBefore(value,this->front );
}
}

//insert a node after nodeB
void dlist::insertAfter(int value,node *nodeB)
{
node *newNode;
newNode=new node();
newNode->next= nodeB->next ;
newNode->prev =nodeB;
newNode->value =value;

if(nodeB->next==NULL)
{
cout<<"\n "<<>back =newNode;
}
nodeB->next=newNode;
cout<<"2"<back==NULL)
{
cout<<"insert at back"; insertFront(value); } else { cout<<"insert at back"; insertAfter(value,this->back );
}
}

//remove the front node
void dlist::removeFront ()
{
removeNode(this->front);
}

//remove a back node
void dlist::removeBack ()
{
removeNode(this->back);

}

//remove before a node
void dlist::removeBefore(node *nodeB)
{

if(nodeB->prev==this->front)
{
this->front=nodeB;
this->front->prev=NULL;
}
else
{
removeNode(nodeB->prev);
}
}

//remove after a node
void dlist::removeAfter(node *nodeA)
{
if(nodeA->next==this->back)
{
this->back=nodeA;
this->back->next=NULL;
}
else
{
removeNode(nodeA->next);
}
}

//remove a perticular node
void dlist::removeNode(node *nodeToRemove)
{
if(nodeToRemove==this->front)
{
this->front=this->front->next;
this->front->prev=NULL;
}
else if (nodeToRemove==this->back)
{
this->back=this->back->prev;
this->back->next=NULL ;
}
else
{
nodeToRemove->prev->next=nodeToRemove->next;
nodeToRemove->next->prev=nodeToRemove->prev;
}
}

//Print the list from front
void dlist::printDListFront()
{
node* curr2;
curr2= this->front;
cout<<"\n-----\n"; cout<<"Queue\n"; cout<<"-----\n"; //cout<<"size:"<<<<" |"<value<<"|"; curr2=curr2->next;
}
cout<back;
cout<<"\n-----\n"; cout<<"Queue\n"; cout<<"-----\n"; //cout<<"size:"<<<<" |"<value<<"|"; curr2=curr2->prev;
}
cout<insertBack(8);
st->printDListFront ();
st->insertBack(5);
st->printDListFront ();
st->insertBack(6);
st->printDListFront ();
st->insertFront(1) ;
st->printDListFront ();
st->insertFront(3) ;
st->printDListFront ();
st->insertBack(7);
st->printDListFront ();
st->removeFront();
st->printDListFront ();
st->removeBack();
st->printDListFront ();
}