我编写了单链接列表的以下实现。我面临的一个问题是我要pop_back()
删除最后一个节点,然后将tail
设置为O(1)中的倒数第二个节点。现在,问题在于它不是一个双向链接的列表,因此如果不运行循环,我将无法访问倒数第二个节点。我已经完成了O(1)中的push_back()
。如何在此代码的O(1)中生成pop_back()
?
#include <iostream>
using namespace std;
template <class T>
class LinkedList {
private:
T data;
LinkedList *next, *head, *tail;
public:
LinkedList() : next(nullptr), head(nullptr), tail(nullptr){}
LinkedList* get_node(T);
void push_back(T);
void insert(int, T);
void pop_back();
void erase(int);
void print();
};
template <typename T>
LinkedList<T>* LinkedList<T>:: get_node(T element) {
auto* new_node = new LinkedList;
new_node -> data = element;
new_node ->next = nullptr;
return new_node;
}
template <typename T>
void LinkedList<T>:: push_back(T element) {
if(head == nullptr) {
head = get_node(element);
tail = head;
} else {
LinkedList *node = get_node(element);
tail->next = node;
tail = node;
}
}
template <typename T>
void LinkedList<T>:: insert(int position, T element) {
LinkedList *node = get_node(element);
if(position == 1){
node->next = head;
head = node;
} else {
LinkedList *start = head;
int it = 1;
while (it < position - 1) {
start = start->next;
++it;
}
node->next = start->next;
start->next = node;
}
}
template <typename T>
void LinkedList<T>:: pop_back() {
}
template <typename T>
void LinkedList<T>:: erase(int position) {
}
template <typename T>
void LinkedList<T>:: print() {
LinkedList *start = head;
while(start != nullptr) {
cout << start->data << " ";
start = start->next;
}
}
int main() {
LinkedList<int> lt;
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.insert(1, 34);
lt.print();
}
可悲的是,您无法在O(1)时间内执行此操作,因为无法执行此操作,因此必须补偿内存的性能并使用双链表。如果您可以选择使用其他数据结构,建议您使用Deque