我们都知道list的底层实现是双向链表，今天我们就讲一讲底层为单向链表的slist，其实现比较简单。
listnode.h
template<typename T>
struct ListNode {
T value;
ListNode<T>* next;
public:
ListNode(const T _value) :value(_value) {};
};
listiterator.h
#include"listnode.h"
template<typename T>
class ListIterator {
public:
typedef T Value_type;
typedef T* Pointer;
typedef T& Reference;
public:
ListIterator() :node(nullptr) {};
ListIterator(ListNode<T>* _node) :node(_node) {};
~ListIterator() { if (node) delete node; };
public:
bool operator==(const ListIterator<T>& listiterator)const;
bool operator!=(const ListIterator<T>& listiterator)const;
T& operator*()const;
T* operator->()const;
ListIterator<T>& operator++();
ListIterator<T> operator++(int);
private:
ListNode<T>* node;
};
listiterator.cpp
#include"listiterator.h"
template<typename T>
bool ListIterator<T>::operator==(const ListIterator<T>& listiterator)const {
return nodo == listiterator.node;
}
template<typename T>
bool ListIterator<T>::operator!=(const ListIterator<T>& listiterator)const {
return node != listiterator.node;
}
template<typename T>
T& ListIterator<T>::operator*()const {
return node->value;
}
template<typename T>
T* ListIterator<T>::operator->()const {
return &(node->value);
}
template<typename T>
ListIterator<T>& ListIterator<T>::operator++() {
node = node->next;
return *this;
}
template<typename T>
ListIterator<T> ListIterator<T>::operator++(int) {
ListIterator<T>* tmp = *this;
node = node->next;
return *tmp;
}
list.h
#pragma once
#include"listiterator.h"
template<typename T>
class List {
public:
typedef T Value_type;
typedef T* Pointer;
typedef T& Reference;
typedef size_t Size_type;
typedef size_t Difference_type;
public:
List() :head(new ListNode<T>()) { head->next = nullptr; }
List(const size_t n, const T* t) { construct(n, t); }
~List() { destory(); }
public:
ListIterator<T>* begin()const;
ListIterator<T>* end()const;
Size_type size()const;
bool empty()const;
void swap(ListIterator<T>* listiterator1, ListIterator<T>* listiterator2);
Reference front()const;
void push_front(const Value_type value);
void pop_front();
void push(ListIterator<T>* position, const Value_type);
void pop(ListIterator<T>* position);
void clear();
private:
ListNode<T>* head;
private:
void construct(const size_t n, const T* t)noexcept;
void destory()noexcept;
};
list.cpp
#include"list.h"
template<typename T>
ListIterator<T>* List<T>::begin()const {
ListNode<T>* _node = head->next;
static ListIterator<T> listiterator(_node);
return &listiterator;
}
template<typename T>
ListIterator<T>* List<T>::end()const {
static ListIterator<T> listiterator(nullptr);
return &listiterator;
}
template<typename T>
typename List<T>::Size_type List<T>::size()const {
ListNode<T>* p = head->next;
typename List<T>::Size_type count = 0;
while (p != nullptr) {
++count;
p = p->next;
}
return count;
}
template<typename T>
bool List<T>::empty()const {
if (head->next == nullptr)
return true;
else
return false;
}
template<typename T>
void List<T>::swap(ListIterator<T>* listiterator1, ListIterator<T>* listiterator2) {
ListNode<T>* tmp = listiterator1->node;
listiterator1->node = listiterator2->node;
listiterator2->node = tmp;
}
template<typename T>
typename List<T>::Reference List<T>::front()const {
ListNode<T>* node = head->next;
return node->value;
}
template<typename T>
void List<T>::push_front(const Value_type value) {
ListNode<T>* newnode = nwe ListNode<T>(value);
ListNode<T>* head_next = head->next;
newnode->next = head_next;
head->next = newnode;
}
template<typename T>
void List<T>::pop_front() {
ListNode<T>* head_next = head->next;
head->next = head_next->next;
delete head_next;
}
template<typename T>
void List<T>::push(ListIterator<T>* position, const Value_type value) {
ListNode<T>* p = head;
while (p!=nullptr) {
if (p->next == position->node)
break;
p = p->next;
}
ListNode<T>* newnode = new ListNode<T>(value);
newnode->next = p->next;
p->next = newnode;
}
template<typename T>
void List<T>::pop(ListIterator<T>* position) {
ListNode<T>* p = head;
while (p != nullptr) {
if (p->next == position->node)
break;
p = p->next;
}
ListNode<T>* pos_next = position->node->next;
p->next = pos_next;
delete position;
}
template<typename T>
void List<T>::construct(const size_t n, const T* t)noexcept {
ListNode<T>* p = head;
for (int i = 0; i < n; ++i) {
ListNode<T>* newnode = new ListNode<T>(t[i]);
p->next = newnode;
p = newnode;
}
p->next = nullptr;
}
template<typename T>
void List<T>::destory()noexcept {
typename List<T>::Size_type n = size();
for (int i = 0; i < n; ++i) {
pop_front();
}
delete head;
}
template<typename T>
void List<T>::clear() {
typename List<T>::Size_type n = size();
for (int i = 0; i < n; ++i) {
pop_front();
}
head->next = nullptr;
}
以上是我简单的实现slist，如果有什么错误请大家及时的通知我哦~~