linked list dengan bahasa c++

Senarai berantai (linked list) adalah sekumpulan elemen/nilai bertipesama yang mempunyai keterurutan keanggotaan. Berdasarkan keterurutan keanggotaan tersebut, jika diketahui sebuah anggota/elemen senarai maka dapat diketahui elemen berikutnya. Setiap elemen senarai terbagi menjadi 2 bagian, yaitu:
Info : menyimpan informasi, bisa berupa satu elemen data atau beberapa elemen data.
Berikut : menyimpan ‘alamat’ dari elemen berikutnya.

operator terhadap list adalah sebagai berikut:
Insert / tambah : menyisipkan sebuah elemen list
Delete / hapus : menghapus sebuah elemen list

Operator tambahan untuk list adalah :
Empty List : fungsi boolean yang mengirimkan nilai true jika list kosong.
Inisialisasi list : menginisialisasi (memberi nilai awal) list
Allocate : memesan alamat (address) yang belum digunakan
Deallocate : membebaskan alamat yang sudah tidak diperlukan lagi.

dan berikut saya sertakan source code linked list sederhana dengan bahasa c++ beserta sedikit penjelasan dalam wujud coment. lagi-lagi saya mohon kepada anda, kawan-kawan untuk tidak sekedar copy-paste code. melainkan mempelajari kemudian mengembangkannya. ini demi kebaikan anda juga.

source code:
list.h
———————————begin——————————

#ifndef list_H
#define list_H

#include
#include
#include
#include
#include

#define nil NULL
#define info(P) (P)->info
#define next(P) (P)->next
#define first(L) ((L).first)
#define last(L) ((L).last)

typedef int infotype;
typedef struct tElmtList *address;
typedef struct tElmtList
{
infotype info;
address next;
} ElmtList;
typedef struct
{
address first;
address last;
} List;

/* PROTOTYPE */

/* TEST LIST KOSONG */
bool ListEmpty(List L);
/* mengirimkan firs(L)==nil dan list(L)==nil */

/* PEMBUATAN LIST KOSONG */
void CreateList(List *L);
/* membuat list kosong first(*L)=nil dan list(*L)=nil */

/* INPUT /OUTPUT */
void BacaList(infotype *x);
/* menerima dan mengirimkan masukan list */
void TulisList(List L);
/* menampilkan elemen list */

/* MANAJEMEN MEMORY */
address Alokasi(infotype x);
/* mengirimkan address hasil alokasi sebuah elemen */
/* jika alokasi berhasil,address tidak nil */
/* jika alokasi gagal,mengirimkan nil */
void Dealokasi(address P);
/* menerima input P yang terdefinisi */
/* address P dikembalikan ke sistem */
/* melakukan dealokasi/pengembalian address P */

/* PENAMBAHAN ELEMEN */
void InsertFirst(List *L,infotype x);
/* melakukan alokasi untuk elemen x */
/* menambahkan elemen pada posisi pertama jika alokasi berhasil */
void InsertPos(List *L,infotype x,int Pos);
/* mnelakukan alokasi untuk elemen x */
/* mencari posisi untuk menempatkan elemen x */
/* menambahkan elemen x posisi yang sudah di tentukan */
void InsertLast(List *L,infotype x);
/* melakukan alokasi untuk elemen x */
/* jika list kosong,maka melakukan InsertFirst */
/* menambahkan elemen x pada posisi terakhir jika alokasi berhasil */

/* PENGHAPUSAN ELEMEN */
void DeleteFirst(List *L);
/* jika list kosong maka tidak melakukan apa-apa */
/* jika hanya satu elemen maka first(*L)=nil dan last(*L)=nil,dealokasi alamat P */
/* jika lebih dari satu elemen,dealokasi alamat P yang pertama */
void DeletePos(List *L,int Pos);
/* jika list kosong maka tidak melakukan apa-apa */
/* jika Posisi elemen yang ingin di hapus tidak ketemu maka tidak melakukan apa-apa */
/* jika Posisi ditemukan maka dealokasi alamat pada posisi tersebut */
void DeleteLast(List *L);
/* jika list kosong maka tidak melakukan apa-apa */
/* jika hanya satu elemen maka melakukan DeleteFirst */
/* jika lebih dari satu elemen,maka menghapus posisi terakhir dan dealokasi alamat terakhir */
void Max(List L);
void Min(List L);
void Search(List L);

/* BODY */
void Max(List L)
{
address P;
P=first(L);
int x;
x=0;
while (P!=nil){
if(x<=info(P))
{
x=info(P);
}
P=next(P);
}
cout<=info(P))
{
x=info(P);
}
P=next(P);
}
cout<
}

void Search(List L)
{
address P;
P=first(L);
int s,k=2;
cout<<“\nNilai yang ingin dicari: “;
while(P!=nil){
if(s==info(P)){
cout<
break;
}
P=next(P);
k++;
}
}

/* TEST LIST KOSONG */
bool ListEmpty(List L)
{
return ((first(L)==nil)&&(last(L)==nil)); /* mengirimkan first(L)==nil dan list(L)==nil */
}

/* PEMBUATAN LIST KOSONG */
void CreateList(List *L)
{
first(*L)=nil;
last(*L)=nil;
}

/* INPUT /OUTPUT */
void BacaList(infotype *x)
{
printf(“\nMasukkan data : “); scanf(“%d”,&(*x));
printf(“”);
}

void TulisList(List L)
{
address P;
P=first(L);
printf(“Data List=”);
while (P!=nil)
{
printf(” %d”,info(P));
P=next(P);
}
}

/* MANAJEMEN MEMORY */
address Alokasi(infotype x)
{
address P;
P=(address)malloc(sizeof(ElmtList));
if (P!=nil)
{
info(P)=x;
next(P)=nil;
} /* end if (P!=nil) */
return P; /* mengirimkan alamat hasil alokasi */
}

void Dealokasi(address P)
{
free(P); /* melakukan dealokasi/pengembalian address P */
}

/* PENAMBAHAN ELEMEN */
void InsertFirst(List *L,infotype x)
{
address P;
P=Alokasi(x); /* alokasi memori unruk elemen x */
if (P!=nil)
{ /* jika alokasi P tidak nil */
if (ListEmpty(*L))
{ /* jika list kosong */
last(*L)=P;
} /* end if list kosong */
next(P)=first(*L);
first(*L)=P; /* elemen pertama di isi P */
} /* end if alokasi tidak nil */
}

void InsertPos(List *L,infotype x,int Pos)
{
address P,Ppos;
int i=1;
Ppos=Alokasi(x);
P=first(*L);
if ((P==nil)&&(Pos==1))
{ /* jika list kosong dan posisi = 1*/
next(Ppos)=P;
first(*L)=Ppos;
last(*L)=Ppos;
}
else
{
if ((P!=nil)&&(Pos==1))
{
next(Ppos)=P;
first(*L)=Ppos;
}
else
{ /* jika listtidak kosong dan posisi != 1*/
while ((next(P)!=nil)&&((i+1)

{ /* masuk looping ketika ((next(P)!=nil)&&(i+1
i+=1; /* setiap looping i bertambah 1 */
P=next(P);
} /* end while ((next(P)!=nil)&&(i+1
if (((i+1)==Pos)&&(next(P)!=nil))
{ /* jika (i+1==Pos) */
next(Ppos)=next(P);
next(P)=Ppos;
}
else
{ /* jika (i+1!=Pos) */
next(P)=Ppos;
last(*L)=Ppos;
} /* endif (i+1==Pos) */
}
} /* end if ((P==nil)&&(Pos==1)) */
}

void InsertLast(List *L,infotype x)
{
address P;
P=Alokasi(x);
if (ListEmpty(*L))
{ /* jika list kosong */
first(*L)=P;
last(*L)=P;
}
else
{ /* jika list tidak kosong */
next(last(*L))=P;
last(*L)=P;
} /* end if (ListEmpty(*L)) */
}

/* PENGHAPUSAN ELEMEN */
void DeleteFirst(List *L)
{
address P;
P=first(*L);
if (!ListEmpty(*L))
{ /* jika list tidak kosong */
if (P==last(*L))
{ /* jika dalam list hanya ada 1 elemen*/
Dealokasi(P);
first(*L)=nil;
last(*L)=nil;
}
else
{ /* jika dalam list ada lebih dari satu elemen */
first(*L)=next(P);
Dealokasi(P);
} /* end if (P==last(*L)) */
} /* end if (P!=nil) */
}

void DeletePos(List *L,int Pos)
{
address P,temp;
int i=1;
P=first(*L);
if (!ListEmpty(*L))
{ /* jika list tidak kosong */
if ((P==last(*L))&&(Pos==1))
{ /* jika dalam elemen list hanya ada 1 elemen dan posisi yang akan di hapus adalah elemen 1 */
Dealokasi(P);
first(*L)=nil;
last(*L)=nil;
}
else
{
if ((next(P)!=nil)&&(Pos==1))
{
first(*L)=next(P);
Dealokasi(P);
}
else
{ /* jika dalam elemen list ada lebih dari satu elemen */
while ((next(P)!=nil)&&((i+1)
{ /* loopig ketika ((next(P)!=nil)&&((i+1)
i+=1;
P=next(P);
} /* end while ((next(P)!=nil)&&((i+1)
if (next(P)!=nil)
{ /* jika posisi yang akan dihapus bukan elemen terakhir */
temp=next(P);
next(P)=next(next(P));
Dealokasi(temp);
} /* endif (next(P)!=nil) */
}
} /* end if ((P==last(*L))&&(Pos==1)) */
} /* end if (!ListEmpty(*L)) */
}

void DeleteLast(List *L)
{
address P;
P=first(*L);
if (!ListEmpty(*L))
{ /* jika list tidak kosong */
if (P==last(*L))
{ /* jika dalam list hanya ada 1 elemen*/
Dealokasi(P);
first(*L)=nil;
last(*L)=nil;
}
else
{ /* jika dalam list ada lebih dari satu elemen */
while (next(P)!=last(*L))
{ /* looping ketika (next(P)!=last(*L)) */
P=next(P);
} /* end while (next(P)!=last(*L)) */
Dealokasi(last(*L));
next(P)=nil;
last(*L)=P;
} /* endif (P==last(*L)) */
} /* end if (!ListEmpty(*L)) */
}
#endif
——————————–end—————————————-

testlist.cpp
——————————–begin———————————-

#include
#include”list.h”
#include
#include
#include
#include

main(){
List L;
infotype x;
CreateList(&L);

BacaList( &x);
InsertFirst( &L, x);
cout<<“Angka ini dimasukkan sbg elemen pertama\n”;
TulisList(L);

BacaList( &x);
InsertFirst( &L, x);
cout<<“Angka ini dimasukkan sebagai elemen pertama\n”;
TulisList(L);

BacaList( &x);
InsertLast(&L, x);
cout<<“Angka ini dimasukkan sebagai elemen terakhir\n”;
TulisList(L);

BacaList( &x);
InsertLast(&L,x);
cout<<“Angka ini dimasukkan sebagai elemen terakhir\n”;
TulisList(L);

BacaList( &x);
InsertPos( &L, x, 2);
cout<<“Angka ini dimasukkan sbg elemen ke-2\n”;
TulisList(L);

cout<<“\nMenghapus elemen terakhir\n”;
DeleteLast(&L);
TulisList(L);

cout<<“\nMenghapus elemen pertama\n”;
DeleteFirst(&L);
TulisList(L);

cout<<“\nMenghapus elemen ke 3\n”;
DeletePos(&L,3);
TulisList(L);

cout<<“\nNilai maksimum: “;
Max(L);
cout<<“\nNilai minimum: “;
Min(L);

Search(L);
}
———————————–end—————————————–

karena saya baik hati, 🙂 maka untuk memudahkan anda, silahkan download source code tersebut di sini