#include <iostream>
#include <cassert>
using namespace std;
#define TYPE int
#define NULL 0
class Node{
public:
Node* next;
Node* prev;
TYPE data;
Node() : data(0), next(NULL), prev(NULL) {}
Node(TYPE _data) : data(_data), next(NULL), prev(NULL) {}
};
class CustomLinkedList {
public:
Node* head;
Node* tail;
int sz;
CustomLinkedList() : head(NULL), tail(NULL), sz(0) {}
void push_back(TYPE data) {
Node* newNode = new Node(data);
if (sz == 0) {
head = newNode;
}
else {
tail->next = newNode;
newNode->prev = tail;
}
tail = newNode;
sz++;
}
void push_front(TYPE data) {
Node* newNode = new Node(data);
if (sz == 0) {
tail = newNode;
}
else {
head->prev = newNode;
newNode->next = head;
}
head = newNode;
sz++;
}
void pop_back() {
Node* delNode = tail;
if (sz == 0) {
return;
}
else if (sz == 1) {
head = tail = NULL;
}
else {
tail->prev->next = NULL;
tail = tail->prev;
}
delete delNode;
sz--;
}
void pop_front() {
Node* delNode = head;
if (sz == 0) {
return;
}
else if (sz == 1) {
head = tail = NULL;
}
else {
head->next->prev = NULL;
head = head->next;
}
delete delNode;
sz--;
}
void insertAt(TYPE data, int idx) {
if (idx < 0 || idx >= sz) {
return;
}
if (idx == 0) {
push_front(data);
}
else if (idx == sz - 1) {
push_back(data);
}
else {
Node* newNode = new Node(data);
Node* nextNode = getAt(idx);
Node* prevNode = nextNode->prev;
prevNode->next = newNode;
newNode->prev = prevNode;
nextNode->prev = newNode;
newNode->next = nextNode;
}
sz++;
}
void deleteAt(int idx) {
if (idx < 0 || idx >= sz) {
return;
}
if (idx == 0) {
pop_front();
}
else if (idx == sz - 1) {
pop_back();
}
else {
Node* deleteNode = getAt(idx);
Node* nextNode = deleteNode->next;
Node* prevNode = deleteNode->prev;
prevNode->next = nextNode;
nextNode->prev = prevNode;
delete deleteNode;
}
sz--;
}
Node* getAt(int idx) {
if (idx < 0 || idx >= sz) {
return NULL;
}
int middle = sz / 2;
int searchLen = idx;
bool firstSearch = true;
Node* iterationNode = head;
if (middle < idx) {
firstSearch = false;
iterationNode = tail;
searchLen = sz - idx - 1;
}
for (int i = 0; i < searchLen; i++) {
iterationNode = firstSearch ? iterationNode->next : iterationNode->prev;
}
return iterationNode;
}
bool isEmpty() { return sz == 0; }
TYPE front() {
if (isEmpty()) {
assert(0);
}
return head->data;
}
TYPE back() {
if (isEmpty()) {
assert(0);
}
return tail->data;
}
void DEBUG_PRINT() {
Node* printNode = head;
cout << "PRINT NODE : ";
for (int i = 0; i < sz; i++) {
cout << printNode->data << " ";
printNode = printNode->next;
}
cout << endl;
}
int size() { return sz; }
};
int main() {
CustomLinkedList lst;
for (int i = 0; i < 10; i++) {
lst.push_back(i);
}
cout << "PUSH 0 to 9" << endl;
lst.DEBUG_PRINT();
cout << "DELETE INDEX 3" << endl;
lst.deleteAt(3);
lst.DEBUG_PRINT();
cout << "INSERT INDEX 7 VALUE 100" << endl;
lst.insertAt(100, 7);
lst.DEBUG_PRINT();
cout << "DELETE INDEX 10 INT MAX INDEX 9(NOT WORKING)" << endl;
lst.deleteAt(10);
lst.DEBUG_PRINT();
cout << "PUSH BACK (99)" << endl;
lst.push_back(99);
lst.DEBUG_PRINT();
cout << "PUSH FRONT (12)" << endl;
lst.push_front(12);
lst.DEBUG_PRINT();
cout << "SIZE " << lst.size() << endl;
cout << "POP FRONT()" << endl;
lst.pop_front();
lst.DEBUG_PRINT();
cout << "POP BACK()" << endl;
lst.pop_back();
lst.DEBUG_PRINT();
cout << "FRONT VALUE " << lst.front() << endl;
cout << "BACK VALUE " << lst.back() << endl;
return 0;
}
