当前位置:网站首页>Template implementation of linked list
Template implementation of linked list
2022-07-22 07:05:00 【Little flying general】
BaseList.h
#pragma once
template <class T>
class BaseList {
public:
typedef size_t pos;
virtual void clear() = 0; // empty the list
virtual bool isEmpty() = 0; // Is empty list?
virtual void append(const T&) = 0; // add element in the end
virtual void insert(const pos, const T&) = 0; // insert element in the middle
virtual void del(const pos) = 0; // delete element from list
virtual T getValue(const pos) = 0; // return the value in the position
virtual void setValue(const pos, const T&) = 0; // modify the value at position
virtual pos getPosition(const T&) = 0; // get the position of value T
};
LinkList.h
#pragma once
#include <iostream>
#include "BaseList.h"
template <class T>
class Node {
public:
T val;
Node* next;
Node(const T& val, Node *p = nullptr)
: val(val), next(p) {
}
Node(Node *p = nullptr)
:next(p) {
}
};
template <class T>
class LinkList : public BaseList<T> {
private:
Node<T>* head;
Node<T>* getNodePosition(BaseList<T>::pos p) {
if (p == -1) {
return head;
}
Node<T>* tmpNode = head->next;
for (int i = 0; i < p; i++) {
tmpNode = tmpNode->next;
}
return tmpNode;
}
Node<T>* getTail() {
if (!head->next) {
return head;
}
Node<T>* itr = head->next;
while (itr->next) {
itr = itr->next;
}
return itr;
}
void checkLinkList() {
if (!head->next) {
throw std::exception("Empty list");
}
return;
}
public:
LinkList()
: head(new Node<T>()) {
};
~LinkList() {
Node<T>* itr = head->next;
while (itr) {
Node<T> *temp = itr;
itr = itr->next;
delete temp;
}
}
virtual void clear() override {
checkLinkList();
Node<T>* itr = head->next;
while (itr != nullptr) {
Node<T>* temp = itr;
delete temp;
itr = itr->next;
}
head = nullptr;
}
virtual bool isEmpty() override {
return head->next == nullptr;
}
virtual void append(const T& val) override {
Node<T>* newNode = new Node<T>(val);
if (!head->next) {
head->next = newNode;
return;
}
Node<T>* tail = getTail();
tail->next = newNode;
return;
}
virtual void insert(const BaseList<T>::pos p, const T& val) override {
if (!head->next) {
if (p == 0) {
append(val);
}
else {
throw std::exception("Empty list");
}
}
Node<T>* insertPos = getNodePosition(p);
Node<T>* newNode = new Node<T>(val);
newNode->next = insertPos->next;
insertPos->next = newNode;
return;
}
virtual void del(const BaseList<T>::pos p) override {
checkLinkList();
Node<T>* beforeDelPos = getNodePosition(p - 1);
if (beforeDelPos) {
if (beforeDelPos->next) {
Node<T>* deleteNode = beforeDelPos->next;
beforeDelPos->next = deleteNode->next;
delete deleteNode;
return;
}
throw std::exception("Delete node exceed list tail");
}
throw std::exception("Invalid position to delete");
}
virtual T getValue(const BaseList<T>::pos p) override {
checkLinkList();
Node<T>* readPos = getNodePosition(p);
return readPos->val;
}
virtual void setValue(const BaseList<T>::pos p, const T& val) override {
checkLinkList();
Node<T>* writePos = getNodePosition(p);
writePos->val = val;
return;
}
virtual BaseList<T>::pos getPosition(const T& val) override {
checkLinkList();
int count = 0;
Node<T>* itr = head->next;
while (itr->val != val) {
itr = itr->next;
++count;
}
return count;
}
void print() {
Node<T>* itr = head->next;
int count = 0;
while (itr) {
std::cout << "Node Index: " << count++ << '\t';
std::cout << "Node value: " << itr->val << std::endl;
itr = itr->next;
}
return;
}
};
main.cpp
// LinkList.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include "LinkList.h"
using namespace std;
int main()
{
LinkList<int> linklist;
cout << "Enter the count of nodes you want to append" << endl;
int count;
cin >> count;
while (count--) {
cout << "Enter the value of node" << endl;
int val;
cin >> val;
linklist.append(val);
}
linklist.print();
cout << "Enter the node index you want to delete" << endl;
int delIndex = 0;
cin >> delIndex;
linklist.del(delIndex);
linklist.print();
cout << "Enter the node index you want to insert" << endl;
int insertIndex;
cin >> insertIndex;
cout << "Enter the node value you want to insert" << endl;
int nodeVal;
cin >> nodeVal;
linklist.insert(insertIndex, nodeVal);
linklist.print();
return 0;
}
边栏推荐
猜你喜欢
Swagger interface importing postman
非参数检验
Observer mode and publish / subscribe mode
IDEA SSH 工具远程链接失败
EF linq杂记
敬伟PS教程:基础篇A
Matlab GUI programming skills (VII): matlablistbox operation - common operations of listbox and uilistbox
【MATLAB问题解决】解决Matlab编译后的.exe文件在另一台电脑上无法运行的问题
MCD12Q1数据在ENVI中显示多个分类
Matlab GUI编程技巧(九):详解 uitable 函数显示表格及相关操作(创建表用户界面)
随机推荐
在线股票开户很复杂吗?请问,手机开户股票开户安全吗?
ArcGIS创建矢量
Swagger interface importing postman
【MATLAB问题解决】解决Matlab编译后的.exe文件在另一台电脑上无法运行的问题
第三版新视野大学英语读写教程4结业考点(1,2,3,5,6单元)
Realize line by line output of text file content
贾跃亭的法拉第未来再获2.25亿美元融资,FF91即将量产!
Indexes
ArcPy入门相关
EventLoop事件循环机制
地理卫星数据下载
2022.7.19 simulation match
IDEA SSH 工具远程链接失败
c语言 - 如何使用结构体和结构体指针?
线性表的实现
flask - { “message“: “Failed to decode JSON object: Expecting value: line 1 column 1 (char 0)“ }
3D sensing市场加速爆发,TOF和结构光谁将更胜一筹?
vscode - 所选环境中没有可用的Pip安装程序
零碎知识——统计相关
B tree and b+ tree hash index