Skip to content

Instantly share code, notes, and snippets.

@ebresafegaga
Last active February 11, 2022 12:20
Show Gist options
  • Save ebresafegaga/1e5f79c219f0cad5b2c7ea1d9a02e0f7 to your computer and use it in GitHub Desktop.
Save ebresafegaga/1e5f79c219f0cad5b2c7ea1d9a02e0f7 to your computer and use it in GitHub Desktop.
Just a functional programmer playing with pointers.
#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