Last active
February 11, 2022 12:20
-
-
Save ebresafegaga/1e5f79c219f0cad5b2c7ea1d9a02e0f7 to your computer and use it in GitHub Desktop.
Just a functional programmer playing with pointers.
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
#include <vector> | |
#include <string> | |
#include <iostream> | |
struct Node { | |
int element; | |
Node* next; | |
Node* prev; | |
}; | |
Node* create (std::vector<int> elements) { | |
Node* prev = new Node; | |
prev->element = elements.front (); | |
prev->prev = nullptr; | |
Node* tip = prev; | |
auto i = elements.begin (); | |
elements.erase (i); | |
for (auto e : elements) { | |
Node* curr = new Node; | |
curr->element = e; | |
curr->prev = prev; | |
curr->next = nullptr; | |
prev->next = curr; | |
prev = curr; | |
} | |
return tip; | |
} | |
void ppNode (Node* elem) { | |
int element = elem->element; | |
std::string prev = elem->prev == nullptr ? "NULL" : std::to_string(elem->prev->element); | |
std::string next = elem->next == nullptr ? "NULL" : std::to_string(elem->next->element); | |
std::cout << prev << " <- " << element << " -> " << next << std::endl; | |
} | |
void ppDLL (Node* list) { | |
while (list != nullptr) { | |
ppNode (list); | |
list = list->next; | |
} | |
} | |
void reverse (Node*& tip) { | |
// reverse two element list | |
// <- 1 -> <- 2 -> <- 3 -> | |
// <- 2 -> <- 1 -> <- 3 -> | |
auto curr = tip->next; | |
// last element of the list points to nothing | |
tip->next = nullptr; | |
while (curr != nullptr) { | |
// This is the rest of the list | |
// we store for safe keeping | |
auto rest = curr->next; | |
// prev should be current | |
tip->prev = curr; | |
// the next element should point to | |
// the head of the list | |
curr->next = tip; | |
curr->prev = nullptr; | |
// current is now at the tip | |
tip = curr; | |
// start processing the rest of the list | |
// on the next iteration | |
curr = rest; | |
} | |
} | |
int main () { | |
auto list = create ({1, 2, 3, 4, 5, 6, 7}); | |
reverse (list); | |
ppDLL (list); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment