doubly-linked-list.cpp

/**
 * Author: miun173
 * Doubly linked list
 * @2019
 * */
#include <iostream>
using namespace std;

struct Pembalap {
  int nomor;
  char nama;
  int waktu;
  Pembalap* next;
  Pembalap* prev;
};

void createNode(Pembalap* &p,  int nomor, char nama);
// insert node into first position
void insertFirst(Pembalap* &head, Pembalap* node);
// searching in list and assign fount node to pToUpdate
void search(Pembalap* &firstNode, int nomorKey, Pembalap* &pFound);
// update Pembalap from user input
void update(Pembalap* firstNode, int nomorKey);
// print linked list
void traversal(Pembalap* head);
// sorting ascending
void sortingByNomor(Pembalap* &head);
void insertBefore(Pembalap* &head, int keyNomor, Pembalap* node);
void deleteByKey(Pembalap* &head, int keyNomor, Pembalap* &pHapus);

int main() {
  Pembalap* head = NULL;
  Pembalap* pBaru = NULL;
  Pembalap* pToUpdate = NULL;
  char nama = 'a';

  for (int i = 0; i < 4; i++) {
    createNode(pBaru, i+1, nama++);
    insertFirst(head, pBaru);
  }

  cout << "\n>>> List" << endl;
  traversal(head);

  int keyNomor = 2;

  cout << "\n>>> Insert Before nomor " << keyNomor << endl;
  createNode(pBaru, 99, 'z');
  insertBefore(head, keyNomor, pBaru);  
  traversal(head);

  cout << "\n>>> SortingByNomor" << endl;
  sortingByNomor(head);
  traversal(head);

  keyNomor = 3;
  cout << "\n>>> Delete nomor " << keyNomor << endl;
  Pembalap* pHapus = NULL;
  deleteByKey(head, keyNomor, pHapus);
  traversal(head);

  keyNomor = 4;
  cout << "\n>>> Update nomor " << keyNomor << endl;
  update(head, keyNomor);

  cout << "\n>>> Updated list\n";
  traversal(head);
}

void createNode(Pembalap* &p,  int nomor, char nama) {
  p = new Pembalap;
  p->nama = nama;
  p->nomor = nomor;
  p->waktu = 0;
  p->next = p->prev = NULL;
}

// insert node into first position
void insertFirst(Pembalap* &head, Pembalap* node) {
  if (head == NULL) {
    head = node;
    return;
  }

  node->next = head;
  head->prev = node;
  head = node;
}

void insertBefore(Pembalap* &head, int keyNomor, Pembalap* pBaru) {
  if (head == NULL) {
    cout << "List kosong. Pembalap dengan nomor " << keyNomor << " tidak ditemukan";
    return;
  }
  
  Pembalap* pCari = NULL;

  search(head, keyNomor, pCari);
  if (pCari == NULL) {
    cout << "Pembalap dengan nomor " << keyNomor << " tidak ditemukan\n";
    return;
  }

  pBaru->next = pCari;
  pBaru->prev = pCari->prev;
  pCari->prev->next = pBaru;
  pCari->prev = pBaru;
}

void deleteByKey(Pembalap* &head, int keyNomor, Pembalap* &pHapus) {
  if (head == NULL) {
    cout << "List kosong. Pembalap dengan nomor " << keyNomor << " tidak ditemukan";
    pHapus = NULL;
    return;
  }

  Pembalap* pCari = NULL;

  search(head, keyNomor, pCari);
  if (pCari == NULL) {
    cout << "Pembalap dengan nomor " << keyNomor << " tidak ditemukan\n";
    pHapus = NULL;
    return;
  }

  pHapus = pCari;
  // kalau pHapus adalah elemen terakhir
  if (pHapus->next == NULL) {
    pHapus->prev->next = NULL;
    pHapus->prev = NULL;
    return;
  }

  // kalau pHapus ada di tengah List
  pHapus->prev->next = pHapus->next;
  pHapus->next->prev = pHapus->prev;
  pHapus->next = pHapus->prev = NULL;
}

// searching in list and assign fount node to pToUpdate
void search(Pembalap* &firstNode, int nomorKey, Pembalap* &pFound) {
  bool isFound = false;
  Pembalap* pCari = firstNode;


  // search for the key till last node
  while(!isFound && pCari != NULL) {
    // kalo ketemu
    if (nomorKey == pCari->nomor) {
      isFound = true;
      pFound = pCari;
      break;
    }

    pCari = pCari->next;
  }
}

// update Pembalap from user input
void update(Pembalap* firstNode, int nomorKey) {
  Pembalap* pToUpdate = NULL;
  search(firstNode, nomorKey, pToUpdate);

  if (pToUpdate == NULL) {
    cout << "Tidak ada yg diupdate";
    return; // akhiri fungsi/void
  }

  // update here
  cout << "nama: "; cin >> pToUpdate->nama;
  cout << "nomor: "; cin >> pToUpdate->nomor;
  cout << "waktu: "; cin >> pToUpdate->waktu;
  cout << endl;
}

// print linked list
void traversal(Pembalap* head) {
  Pembalap* pCurr = head;

  while(pCurr != NULL) {
    cout << "nomor: " << pCurr->nomor << endl;
    cout << "nama: " << pCurr->nama << endl; 
    cout << "waktu: " << pCurr->waktu << endl << endl; 
    pCurr = pCurr->next;
  }
  
}

// sorting ascending
void sortingByNomor(Pembalap* &head) {
  Pembalap* travNode = head;

  while (travNode != NULL) {
    Pembalap* currNode = head;
    
    while (currNode != NULL) {
      if (currNode->nomor > travNode->nomor) {
        // swap them
        Pembalap temp = *currNode;
        currNode->nama = travNode->nama;
        currNode->waktu = travNode->waktu;
        currNode->nomor = travNode->nomor;

        travNode->nama = temp.nama;
        travNode->waktu = temp.waktu;
        travNode->nomor = temp.nomor;
      } else {
        currNode = currNode->next;
      }
    }

    travNode = travNode->next;
  }  
}