Created
July 13, 2019 18:23
-
-
Save andraantariksa/096e515e5cb1464281a26124dbf8a3a2 to your computer and use it in GitHub Desktop.
Simple Linked List implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef linkedlist_header_ | |
#define linkedlist_header_ | |
#include <functional> | |
namespace LinkedList{ | |
template <class T> | |
class Node | |
{ | |
public: | |
T data; | |
Node<T> *next; | |
}; | |
template <class T> | |
class LinkedList | |
{ | |
private: | |
Node<T> *head; | |
public: | |
LinkedList(); | |
int length; | |
void push_front(T); | |
void push_back(T); | |
void insert(int, T); | |
void pop_front(); | |
void pop_back(); | |
void remove_at(T); | |
T first(); | |
T last(); | |
T at(int); | |
void map(std::function<void(T)>); | |
int find(std::function<bool(T)>); | |
}; | |
template <class T> | |
LinkedList<T>::LinkedList() | |
{ | |
this->length = 0; | |
this->head = NULL; | |
} | |
template <class T> | |
void LinkedList<T>::insert(int pos, T n) | |
{ | |
Node<T> *pre = new Node<T>(); | |
Node<T> *curr = new Node<T>(); | |
Node<T> *temp = new Node<T>(); | |
if(pos == 0) | |
{ | |
temp->data = n; | |
temp->next = this->head; | |
this->head = temp; | |
} | |
else | |
{ | |
curr = this->head; | |
for (int i = 0; i < pos; i++) | |
{ | |
pre = curr; | |
curr = curr->next; | |
} | |
temp->data = n; | |
temp->next = curr; | |
pre->next = temp; | |
} | |
this->length++; | |
} | |
template <class T> | |
void LinkedList<T>::push_front(T n) | |
{ | |
insert(0,n); | |
} | |
template <class T> | |
void LinkedList<T>::push_back(T n) | |
{ | |
insert(this->length, n); | |
} | |
template <class T> | |
void LinkedList<T>::remove_at(T pos) | |
{ | |
Node<T> *pre = new Node<T>(); | |
Node<T> *curr = new Node<T>(); | |
curr = this->head; | |
if(pos == 0) | |
{ | |
pre = this->head; | |
head = head->next; | |
} | |
else | |
{ | |
for (int i = 0; i < pos; i++) | |
{ | |
pre = curr; | |
curr = curr->next; | |
} | |
pre->next = curr->next; | |
} | |
this->length--; | |
} | |
template <class T> | |
void LinkedList<T>::pop_front() | |
{ | |
remove_at(0); | |
} | |
template <class T> | |
void LinkedList<T>::pop_back() | |
{ | |
remove_at(this->length - 1); | |
} | |
template <class T> | |
T LinkedList<T>::at(int n) | |
{ | |
Node<T> *new_node = this->head; | |
for (int i = 0; i < n; i++) | |
{ | |
new_node = new_node->next; | |
} | |
return new_node->data; | |
} | |
template <class T> | |
T LinkedList<T>::first() | |
{ | |
return at(0); | |
} | |
template <class T> | |
T LinkedList<T>::last() | |
{ | |
return at(this->length-1); | |
} | |
template <class T> | |
void LinkedList<T>::map(std::function<void(T)> funct) | |
{ | |
Node<T> *new_node = this->head; | |
while(new_node) | |
{ | |
funct(new_node->data); | |
new_node = new_node->next; | |
} | |
} | |
template <class T> | |
int LinkedList<T>::find(std::function<bool(T)> funct) | |
{ | |
// Pencarian linear dengan while loop | |
Node<T> *new_node = this->head; | |
int i = 0; | |
while(new_node) | |
{ | |
if(funct(new_node->data)) | |
{ | |
return i; | |
} | |
new_node = new_node->next; | |
i++; | |
} | |
return -1; | |
} | |
} | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment