SIngle Linked List dan Contoh Penerapan dalam Bahasa C

Assala'mualaikum Wr. Wb. Selamat dan semangat pagi, siang, sore, malam untuk teman-teman semua. Setelah sekian purnama saya tidak memposting artikel dikarenakan beberapa masalah teknis. Baik, pada artikel ini, sesuai dengan judul di atas, saya akan membahas materi kuliah Struktur Data dan Algoritma, yaitu Linked List. Linked List (yang juga sering disebut dengan senarai berantai) merupakan struktur data yang terdiri dari urutan record data dimana setiap record data punya field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data pada Linked List ini disebut dengan Node. Istilah yang sering dipakai di dalam linked list antara lain head dan tail. Apa itu Head? Apa itu Tail? Seperti dengan namanya, arti atau definisi Head pada linked list ini adalah elemen pertama pada linked list. Sedangkan Tail merupakan elemen terakhir pada linked list. Untuk lebih jelasnya bisa dilihat seperti pada gambar berikut.

Nah, bisa disimpulkan bahwa Linked List ini merupakan kumpulan dari beberapa Nodes dan menggambarkan suatu urutan data. Ada beberapa jenis linked list, yaitu:

1. Single Linked List
2. Double Linked List
3. Circular Linked List, dan
4. Multiple Linked List

Nah pada artikel ini akan dibahas Single Linked List dulu, untuk yang lain akan ditulis di artikel terpisah. Single Linked List merupakan linked list yang hanya punya satu variabel pointer saja, dan variabel ini menunjuk pada node selanjutnya. Adapun pada single linked list ada satu variabel pointer yang dijadikan sebagai acuan, atau referensi, yaitu pointer Head, yang menunjuk pada node pertama pada suatu linked list. Secara umum ada 2 (dua) operasi pada single linked list, yaitu push dan pop. Apa lagi itu push dan pop? Push merupakan operasi untuk menambahkan suatu record data pada suatu linked list. Ada dua operasi push, ada dua buah aksi, yaitu pushHead dan pushTail. Nah ada istilah lagi nih teman-teman, tapi tidak perlu bingung, nanti akan saya berikan contohnya agar makin mudah dalam memahaminya.

Baik, pushHead adalah suatu aksi menambahkan elemen baru pada single linked list dimana elemen tersebut diletakkan pada posisi terdepan atau paling awal. Sebaliknya, pushTail adalah aksi menambahkan elemen baru dalam suatu single linked list dengan posisi paling akhir. Selain ada operasi push, ada juga operasi pop. Pop merupakan kebalikan dari operasi push, yaitu menghapus elemen pada suatu single linked list. Ada dua aksi juga, yaitu popHead dan popTail. Sama seperti pushHead dan pushTail, popHead ini aksi untuk menghapus elemen linked list yang berada diurutan pertama, sedangkan popTail akan menghapus elemen yang berada paling akhir. Berikut analogi yang menggambarkan operasi push dan pop.

Diberikan data awal linked list seperti berikut:

Kemudian akan saya berikan pushHead dengan data 2, sehingga data 2 akan menjadi Head yang baru, maka akan menjadi:

Kemudian saya berikan aksi popTail, sehingga data dengan nilai 6 akan menghilang, dan data dengan nilai 3 akan menjadi Tail yang baru:

Nah, sekarang untuk aksi pushTail dan popHead, teman-teman bisa membayangkannya kan? 

Lalu bagaimana implementasinya di kode program? Baik, akan saya berikan contoh sederhananya, pastikan teman-teman sudah mempelajari konsep ADT (Abstract Type Data) ya agar lebih mudah dalam memahami kode programnya. Langsung saja kita lihat potongan kode program berikut ini.

Kita buat dulu struct mahasiswa seperti berikut. Untuk keterangan masing-masing kode teman-teman bisa membaca di comment yang ada di samping kodenya ya..

struct mahasiswa{
	int nim; //menampung integer nim mahasiswa
	char nama[30]; //menampung karakter nama mahasiswa
	struct mahasiswa *next; //menampung alamat data selanjutnya
}*head, *tail, *current;
//head => pointer yang menyimpan alamat data pertama
//tail => pointer yang menyimpan alamat data terakhir
//current => pointer yang digunakan sebagai temporary variabel

Kemudian kita buat fungsi pushHead sebagai berikut.

void pushHead(int nim, char nama[]){
    //alokasi memory untuk data baru
	current = (struct mahasiswa*)malloc(sizeof(struct mahasiswa));
	current->nim = nim; //assign data ke dalam struct
	strcpy(current->nama, nama); //copy nilai variabel parameter nama ke current->nama

	if(head == NULL){ //jika nilai head adalah null, maka set head = tail = current
		head = tail = current; //set nilai head = tail = current
	}
	else{ //jika nilai head tidak null, maka
		current->next = head; //set nilai current->next = head
		head = current; //kemudian set nilai head = current
	}
}

Kemudian kita buat fungsi pushTail.

void pushTail(int nim, char nama[]){
	current = (struct mahasiswa*)malloc(sizeof(struct mahasiswa)); //alokasi memory untuk data baru
	current->nim = nim;//assign data ke dalam struct
	strcpy(current->nama, nama); //copy nilai variabel parameter nama ke current->nama

	if(head == NULL){ //jika nilai head adalah null, maka set head = tail = current
		head = tail = current; //set nilai head = tail = current
	}
	else{ //jika nilai head tidak null, maka
		tail->next = current; //set nilai tail->next = current
		tail = current; //kemudian set nilai tail = current
	}
	tail->next = NULL; //kemudian set nilai tail menjadi null
}

Selanjutnya kita buat fungsi popHead.

void popHead(){
	current=head; //set nilai current sebagai head
	if(head==NULL){ //jika head bernilai null
		printf("No data"); //tampilkan info tidak ada data
	}else if(head==tail){ //jika nilai head = tail
		head=tail=NULL; //set nilai head = tail = null
		free(current); //hapus nilai current (head)
	}else{ //jika nilai head bukan null dan bukan tail
		head=head->next; //set nilai head menjadi data selanjutnya dari head
		free(current);// hapus nilai current (head)
	}
}

Lalu buat juga fungsi popTail.

void popTail(){
	if(head==NULL){ //jika nilai head = null
		printf("No data"); //tampilkan info tidak ada data
	}else if(head==tail){ //jika nilai head = tail
		head=tail=NULL; //set nilai head = tail = null
		free(current); //hapus nilai current
	}else{ //jika nilai head bukan null dan bukan tail
		struct mahasiswa *temp=head; //buat variabel penampung baru dan assign/beri nilai mulai dari head
		while(temp->next!=tail){ //looping untuk mencari posisi 1 data sebelum tail
			temp=temp->next; //set nilai temp menjadi 1 data setelahnya
		}
		current=tail; //set nilai current menjadi tail
		tail=temp; //set nilai tail menjadi 1 data sebelum tail (hasil looping)
		free(current); //hapus nilai current
		tail->next=NULL; //set nilai setelah next menjadi null/pointer next punya tail diset null
	}
}

Jangan lupa juga buat fungsi print untuk menampilkan hasil dari Single Linked Listnya.

void print(){
	current = head; //set current sebagai head
	while(current != NULL){ //looping selama current bukan null
		printf("%s -> %d\n",current->nama,current->nim); //tampilkan nilai nama dan nim
		current = current->next; //set current menjadi nilai setelahnya
	}
}

Nah, untuk potongan kode program lengkapnya bisa dilihat di bawah.

#include 
#include 
#include 

struct mahasiswa{
	int nim; //menampung integer nim mahasiswa
	char nama[30]; //menampung karakter nama mahasiswa
	struct mahasiswa *next; //menampung alamat data selanjutnya
}*head, *tail, *current;
//head => pointer yang menyimpan alamat data pertama
//tail => pointer yang menyimpan alamat data terakhir
//current => pointer yang digunakan sebagai temporary variabel

void pushHead(int nim, char nama[]){
    //alokasi memory untuk data baru
	current = (struct mahasiswa*)malloc(sizeof(struct mahasiswa));
	current->nim = nim; //assign data ke dalam struct
	strcpy(current->nama, nama); //copy nilai variabel parameter nama ke current->nama

	if(head == NULL){ //jika nilai head adalah null, maka set head = tail = current
		head = tail = current; //set nilai head = tail = current
	}
	else{ //jika nilai head tidak null, maka
		current->next = head; //set nilai current->next = head
		head = current; //kemudian set nilai head = current
	}
}

void pushTail(int nim, char nama[]){
	current = (struct mahasiswa*)malloc(sizeof(struct mahasiswa)); //alokasi memory untuk data baru
	current->nim = nim;//assign data ke dalam struct
	strcpy(current->nama, nama); //copy nilai variabel parameter nama ke current->nama

	if(head == NULL){ //jika nilai head adalah null, maka set head = tail = current
		head = tail = current; //set nilai head = tail = current
	}
	else{ //jika nilai head tidak null, maka
		tail->next = current; //set nilai tail->next = current
		tail = current; //kemudian set nilai tail = current
	}
	tail->next = NULL; //kemudian set nilai tail menjadi null
}

void popHead(){
	current=head; //set nilai current sebagai head
	if(head==NULL){ //jika head bernilai null
		printf("No data"); //tampilkan info tidak ada data
	}else if(head==tail){ //jika nilai head = tail
		head=tail=NULL; //set nilai head = tail = null
		free(current); //hapus nilai current (head)
	}else{ //jika nilai head bukan null dan bukan tail
		head=head->next; //set nilai head menjadi data selanjutnya dari head
		free(current);// hapus nilai current (head)
	}
}

void popTail(){
	if(head==NULL){ //jika nilai head = null
		printf("No data"); //tampilkan info tidak ada data
	}else if(head==tail){ //jika nilai head = tail
		head=tail=NULL; //set nilai head = tail = null
		free(current); //hapus nilai current
	}else{ //jika nilai head bukan null dan bukan tail
		struct mahasiswa *temp=head; //buat variabel penampung baru dan assign/beri nilai mulai dari head
		while(temp->next!=tail){ //looping untuk mencari posisi 1 data sebelum tail
			temp=temp->next; //set nilai temp menjadi 1 data setelahnya
		}
		current=tail; //set nilai current menjadi tail
		tail=temp; //set nilai tail menjadi 1 data sebelum tail (hasil looping)
		free(current); //hapus nilai current
		tail->next=NULL; //set nilai setelah next menjadi null/pointer next punya tail diset null
	}
}

void print(){
	current = head; //set current sebagai head
	while(current != NULL){ //looping selama current bukan null
		printf("%s -> %d\n",current->nama,current->nim); //tampilkan nilai nama dan nim
		current = current->next; //set current menjadi nilai setelahnya
	}
}

int main(){
    int jumlah, i, nim;
    char nama[15], hapustambah, pilihan, lagi;
    awal:
    system("clear");
    printf("Masukkan Jumlah Data: "); scanf("%d", &jumlah);
    for(i=1; i<=jumlah; i++){
        printf("Masukkan data ke %d: \n", i);
        printf("Nama: "); scanf("%s", nama);
        printf("NIM: "); scanf("%d", &nim);
        if(i == 1){
            pushHead(nim, nama);
        } else{
            printf("Masukkan data ke Depan atau Belakang? (d untuk depan, b untuk belakang): ");
            scanf("%s", &pilihan);
            if(pilihan == 'd'){
                pushHead(nim, nama);
            } else{
                pushTail(nim, nama);
            }
        }
    }
    print();
    printf("Mau Menghapus atau Menambah Data? (y untuk nambah, n untuk hapus) ");
    scanf("%s", &hapustambah);
    if(hapustambah == 'y'){
        printf("Nama: "); scanf("%s", nama);
        printf("NIM: "); scanf("%d", &nim);
        printf("Masukkan data ke Depan atau Belakang? (d untuk depan, b untuk belakang): ");
        scanf("%s", &pilihan);
        if(pilihan == 'd'){
            pushHead(nim, nama);
        } else{
            pushTail(nim, nama);
        }
    } else{
        printf("Hapus Depan atau Belakang? (d untuk depan, b untuk belakang) ");
        scanf("%s", &pilihan);
        if(pilihan == 'd'){
            popHead();
        } else{
            popTail();
        }
    }

    print();
    printf("Mau Menambah Data? (y untuk nambah, n untuk tidak) ");
    scanf("%s", &lagi);
    if(lagi == 'y'){
        goto awal;
    } else{
        goto akhir;
    }
    akhir:
	getchar();
	return 0;
}