我正在学习数据结构，我创建了一个带有附加方法的链表，如下:
#include<iostream>
class List{
public:
using value_type = double;
using reference = value_type&;
using const_reference = value_type const &;
List()
: head_(nullptr)
, tail_(nullptr)
{}
void append(const_reference data){
Node* node = new Node;
node->data = data;
node->next = nullptr;
if(head_ == nullptr){
head_ = node;
return;
}
if(tail_ == nullptr){
tail_ = node;
head_->next = tail_;
return;
}
tail_->next = node;
Node* temporary = tail_;
tail_ = node;
node = temporary;
}
void print(){
Node* temporary = head_;
while(temporary != nullptr){
std::cout << temporary->data << '-';
temporary = temporary->next;
}
}
struct Node{
value_type data;
Node* next;
};
Node* head_;
Node* tail_;
};
int main(){
List list;
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.print();
return 0;
}
但是当我阅读如何使用它时，我发现了这样的内容:
void Append (Node* head, int data) {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
Node* new_node = new Node(data);
current->next = new_node;
}
我不是专家，我不认为遍历所有节点，只是在最后添加一些东西是有效的，我错了吗?
你的代码工作了。虽然实现起来有点另类，但它还是很有效的。因为，它使用尾指针直接在末尾附加一个元素。
所以好。
您所展示的另一个代码片段适用于没有尾指针的单链表。是的，这对于这个用例来说，效率更低一些。但是，这样的列表也有它的用例，在这些用例中它们表现得非常好。在c++标准库中，这样的列表称为forward_list。通常使用std::list。这是一个双链表。您可以轻松地在两个方向上遍历这样的列表，这也是它的主要优点。它使用头部和尾部指针，但不是像您实现的那样。它使用一个哨兵，一个特殊的节点，它总是存在并包含头和尾指针。
因此，您使用的是混合型，它只允许向前遍历，您的优化使用尾部指针直接访问最后一个元素。但是如果你想在列表的中间做一些事情，那么你必须从开始向前遍历它。
因此，带有next和previous指针的节点可能更可取。但这取决于你的用例。
为了便于学习，我在下面展示了一个双链表。也许你可以从中得到一些想法。
#include <iterator>
#include <initializer_list>
#include <algorithm>
#include <iostream>
#include <type_traits>
#include <vector>
// ------------------------------------------------------------------------------------------------
// 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 {
T data{};
Node* next{};
Node* previous{};
Node() {}
Node(Node* const n, Node* const p) : next(n), previous(p) {}
Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
};
// Private list data and functions --------
Node* head{};
size_t numberOfElements{};
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) { init(); insert(begin(), count); }
explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
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(T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }
template <int N> List(const 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; }
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; }
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()); }
// 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 pop_front() { erase(begin()); };
void push_front(const T& d) { insert(begin(), d); }
void pop_back() { erase(--end()); };
void push_back(const T& d) { insert(end(), d); }
void resize(size_t count, const T& value);
void resize(size_t count);
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--() { iter = iter->previous; return *this; }
iterator operator++(int) { iterator tmp = *this; ++* this; return tmp; }
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() {
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';
}