In my data structures class I have received the oh so common question of reversing a linked list. I've seen and read enough online to have a good idea on how. However, the professor provided me with this code snippet to implement my function:
template<class T>
void Reverse(LinkedList<T> &array) {
//my code here
}
I would expect the provided skeleton code to be like
void reverse(struct node **head_ref) {
}
Why exactly is there an array reference being passed to the function? How should I implement? Is this a typo?
CodePudding user response：
I see many many questions about linked list, where people are mainly talking about nodes. But a linked list is not a node. It has or contains nodes, or better said a pointer to a head node.
So, if you learn about data structures, then you need this fundamental difference.
In C you can even embed a class "Node" in a class "LinkedList". And then define a pointer to type "Node" with the name head in the linked list.
Regarding your question with the function prototypes.
1st, you are confused by the word "array". The function is called with a variable of type LinkedList Reference and the formal parameter name is "array" (which is then reference to a "Linked"List".
This will be revered in the function, and the result is again available in the LinkedList given to the function.
Your expected prototype "void reverse(struct node **head_ref)" is wrong, becuase you want to reverse a complete linked list, but not a "node".
Because you did not show the Definition of the class "LinkedList", the implementation details cannot be shown here. I just can tell you the usual simple algorithm. You iterate through the linked list at the same time from begin and from the end, using the next/previos pointer from the nodes. And then simply "swap" the values in the node from the current pair from front and end.
You can see a potential implementation here
Below you can find an example for a linked list with a build in reverse function
#include <iostream>
#include <iterator>
#include <vector>
#include <type_traits>
#include <initializer_list>
#include <algorithm>
#include <list>
// ------------------------------------------------------------------------------------------------
// This would be in a header file -----------------------------------------------------------------
// Type trait helper to identify iterators --------------------------------------------------------
template<typename T, typename = void>
struct is_iterator { static constexpr bool value = false; };
template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
static constexpr bool value = true;
};
// The List class ---------------------------------------------------------------------------------
template <typename T>
class List {
// Sub class for a Node -----------
struct Node {
Node* next{};
Node* previous{};
T data{};
Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
Node(Node* const n, Node* const p) : next(n), previous(p) {}
Node() {}
};
// Private list data and functions --------
size_t numberOfElements{};
Node* head{};
void init() { head = new Node(); head->next = head; head->previous = head; numberOfElements = 0; }
public:
struct iterator; // Forward declaration
// Constructor --------------------
List() { init(); }
explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
explicit List(const size_t count) { init(); insert(begin(), count); }
template <typename Iter>
List(const Iter& first, const Iter& last) { init(); insert(begin(),first, last); }
List(const List& other) { init(), insert(begin(), other.begin(), other.end()); };
List(List&& other) : head(other.head), numberOfElements(other.numberOfElements) { other.init(); }
List(const std::initializer_list<T>& il) { init(); insert(begin(), il.begin(), il.end()); }
template <int N> List(const T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }
template <int N> List(T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }
// Assignment ---------------------
List& operator =(const List& other) { clear(); insert(begin(), other.begin(), other.end()); return *this; }
List& operator =(List&& other) { clear(); head = other.head; numberOfElements = other.numberOfElements; other.init(); return *this; }
List& operator =(const std::initializer_list<T>& il) { clear(); insert(begin(),il.begin(),il.end()); return *this; }
template <int N> List& operator =(const T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
template <int N> List& operator =(T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this;}
void assign(const size_t count, const T& value) { clear(); insert(begin(), count, value); }
void assign(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); }
template <typename Iter> void assign(const Iter& first, const Iter& last) { clear(); insert(begin(), first, last);}
template <int N> void assign(const T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
template <int N> void assign(T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
// Destructor ---------------------
~List() { clear(); }
// Element Access -----------------
T& front() { return *begin(); }
T& back() { return *(--end()); }
// Iterators ----------------------
iterator begin() const { return iterator(head->next, head); }
iterator end() const { return iterator(head, head); }
// Capacity -----------------------
size_t size() const { return numberOfElements; }
bool empty() { return size() == 0; }
// Modifiers ----------------------
void clear();
iterator insert(const iterator& insertBeforePosition, const T& value);
iterator insert(const iterator& insertBeforePosition);
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool> = true>
iterator insert(const iterator& insertBeforePosition, const Iter& first, const Iter& last);
iterator insert(const iterator& insertBeforePosition, const size_t& count, const T& value);
iterator insert(const iterator& insertBeforePosition, const std::initializer_list<T>& il);
iterator erase(const iterator& posToDelete);
iterator erase(const iterator& first, const iterator& last);
void push_back(const T& d) { insert(end(), d); }
void pop_back() { erase(--end()); };
void push_front(const T& d) { insert(begin(), d); }
void pop_front() { erase(begin()); };
void resize(size_t count);
void resize(size_t count, const T& value);
void swap(List& other) { std::swap(head, other.head); std::swap(numberOfElements, other.numberOfElements); }
// Operations --------------------
void reverse();
// Non standard inefficient functions --------------------------
T& operator[](const size_t index) const { return begin()[index]; }
// ------------------------------------------------------------------------
// Define iterator capability ---------------------------------------------
struct iterator {
// Definitions ----------------
using iterator_category = std::bidirectional_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
// Data -----------------------
Node* iter{};
Node* head{};
// Constructor ----------------
iterator(Node*const node, Node* const h) : iter(node), head(h) {};
iterator() {};
// Dereferencing --------------
reference operator*() const { return iter->data; }
reference operator->() const { return &**this; }
// Arithmetic operations ------
iterator operator () { iter = iter->next; return *this; }
iterator operator (int) { iterator tmp = *this; * this; return tmp; }
iterator operator--() { iter = iter->previous; return *this; }
iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }
iterator operator (const difference_type& n) const {
iterator temp{ *this }; difference_type k{ n }; if (k > 0) while (k--) temp; else while (k )--temp; return temp;
}
iterator operator =(const difference_type& n) {
difference_type k{ n }; if (k > 0) while (k--) * this; else while (k )--* this; return *this;
};
iterator operator -(const difference_type& n) const {
iterator temp{ *this }; difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k ) temp; return temp;
}
iterator operator -=(const difference_type& n) {
difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k ) * this; return *this;
};
// Comparison ----------------- (typical space ship implementation)
bool operator ==(const iterator& other) const { return iter == other.iter; };
bool operator !=(const iterator& other) const { return iter != other.iter; };
bool operator < (const iterator& other) const { return other.iter - iter < 0; };
bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
bool operator > (const iterator& other) const { return other.iter - iter > 0; };
bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };
// Special non standard functions -----------------
difference_type operator-(const iterator& other) const;
reference operator[] (const size_t index);
};
};
// ------------------------------------------------------------------------------------------------
// Implementation of list functions. This would normally go into a TCC file -----------------------
// List class functions ---------------
template <typename T>
void List<T>::clear() {
for (Node* nextNode{}, * currentNode(head->next); currentNode != head; currentNode = nextNode) {
nextNode = currentNode->next;
delete currentNode;
}
init();
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const T& value)
{
Node* nodeInsertBeforePosition = insertBeforePosition.iter;
Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous, value);
nodeInsertBeforePosition->previous = newNode;
(newNode->previous)->next = newNode;
numberOfElements;
return iterator(newNode, head);
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition)
{
Node* nodeInsertBeforePosition = insertBeforePosition.iter;
Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous);
nodeInsertBeforePosition->previous = newNode;
(newNode->previous)->next = newNode;
numberOfElements;
return iterator(newNode, head);
}
template <typename T>
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool>>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const Iter& first, const Iter& last) {
iterator result(insertBeforePosition.iter, head);
if (first != last) {
result = insert(insertBeforePosition, *first);
Iter i(first);
for ( i; i != last; i)
insert(insertBeforePosition, *i);
}
return result;
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const size_t& count, const T& value) {
iterator result(insertBeforePosition.iter, head);
if (count != 0u) {
result = insert(insertBeforePosition, value);
for (size_t i{ 1u }; i < count; i)
insert(insertBeforePosition, value);
}
return result;
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const std::initializer_list<T>& il) {
return insert(insertBeforePosition, il.begin(), il.end());
}
template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& posToDelete) {
iterator result = posToDelete;
result;
Node* nodeToDelete = posToDelete.iter;
if (nodeToDelete != head) {
nodeToDelete->previous->next = nodeToDelete->next;
nodeToDelete->next->previous = nodeToDelete->previous;
delete nodeToDelete;
--numberOfElements;
}
return result;
}
template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& first, const List<T>::iterator& last) {
iterator result{ end() };
if (first == begin() && last == end())
clear();
else {
while (first != last)
first = erase(first);
result = last;
}
return result;
}
template <typename T>
void List<T>::resize(size_t count) {
if (numberOfElements < count)
for (size_t i{ numberOfElements }; i < count; i)
insert(end());
else
while (count--)
pop_back();
}
template <typename T>
void List<T>::resize(size_t count, const T& value) {
if (numberOfElements < count)
for (size_t i{ numberOfElements }; i < count; i)
insert(end(),value);
else
while (count--)
pop_back();
}
template <typename T>
void List<T>::reverse() {
const Node* oldHead = head;
for (Node* nptr = head; ; nptr = nptr->previous) {
std::swap(nptr->next, nptr->previous);
if (nptr->previous == oldHead) // Previous was the original next
break;
}
}
// ------------------------------------
// Iterator functions -----------------
template <typename T>
typename List<T>::iterator::difference_type List<T>::iterator::operator-(const iterator& other) const {
difference_type result{};
Node* nptr = head;
int indexThis{ -1 }, indexOther{ -1 }, index{};
do {
nptr = nptr->next;
if (nptr == iter)
indexThis = index;
if (nptr == other.iter)
indexOther = index;
index;
} while (nptr != head);
if (indexThis >= 0 and indexOther >= 0)
result = indexThis - indexOther;
return result;
}
template <typename T>
typename List<T>::iterator::reference List<T>::iterator::operator[] (const size_t index) {
Node* nptr = head->next;
for (size_t i{}; i < index and nptr != head; i, nptr = nptr->next)
;
return nptr->data;
}
// ------------------------------------------------------------------------------------------------
// This would be in a cpp file --------------------------------------------------------------------
int main() {
// std::list works
std::list<int> list1{ 1, 2, 3, 4, 5 };
std::cout << std::distance(list1.end(), list1.begin()) << '\n';
List<int> list3{10,20};
List<int>::iterator l3 = list3.end();
for (int k = 0; k < 10; k) {
std::cout << *l3 << ' ';
--l3;
}
std::cout << '\n';
// Custom list
List<int> list2{ 1, 2, 3, 4, 5 };
for (int i : list2)
std::cout << i << ' '; std::cout << '\n';
// Delta works
std::cout << list2.begin() - list2.end() << '\n';
std::cout << list2.end() - list2.begin() << '\n';
// Hopp Count works
List<int>::iterator i = list2.end();
while (i-- != list2.begin())
std::cout << *i << ' '; std::cout << '\n';
i = list2.end();
int counter = 0;
while (i != list2.end()) {
counter;
i;
}
std::cout << counter << '\n';
// Distance will go into endless loop ****************************
std::cout << std::distance(list2.end(), list2.begin()) << '\n';
}