pop_back () в односвязном списке в C ++ - PullRequest
Новая
       67

pop_back () в односвязном списке в C ++

2 голосов
/ 27 марта 2020

Я написал следующую реализацию Singlely Linked List. Одна проблема, с которой я сталкиваюсь, заключается в том, что я хочу pop_back() удалить последний узел, а затем установить tail для второго последнего узла в O (1). Теперь проблема не в двусвязном списке, и поэтому у меня нет доступа ко второму последнему узлу без запуска al oop. Я сделал push_back() в O (1). Как мне сделать pop_back() в O (1) в этом коде? 

#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) {
    LinkedList *temp;
    if(position == 1){
        temp = head;
        head = head ->next;
        delete temp;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        temp = start -> next;
        start ->next = start ->next->next;
        delete temp;
    }
}

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();
}

Ответы [ 3 ]

2 голосов
/ 27 марта 2020

Это невозможно.

Объяснение

Если вы действительно хотите сделать это в O (1) и хотите сохранить единый список, вы можете подумать о сохранении второго последнего узла в дополнение к последнему узлу.

Но, если не считать организационного ужаса, он все равно не сработает. Конечно, в pop_back вы могли бы просто delete tail; и установить хвост для второго последнего элемента. Но теперь вам все равно потребуется al oop для определения нового второго последнего элемента.

Это даже плохо?

Я так не думаю. Каждая структура данных имеет свои преимущества и недостатки. По моему мнению, структура данных, которая делает некоторые вещи действительно хорошо, но сосет на других, лучше, чем структура данных, которая делает все очень быстро. Лучше держать свой класс в тонком положении, оптимизировать его для конкретных c сценариев ios и принять его недостатки.

1 голос
/ 27 марта 2020

Вы не можете с одним связанным списком, давайте реализуем ваш 

template <typename T>
void LinkedList<T>:: pop_back() {
   tail = find(pos); 
   erase_next(tail); // erase tail's next.
}

. Вам нужна функция, чтобы найти позицию, которая подразумевает, что вы также должны знать, сколько в ней, и в этом случае pos это size-1 (-2, если вы используете нулевое смещение) или ищите узел, у которого pos является следующим узлом. Вы можете использовать большую часть кода в erase для его реализации.

Теперь эта новая находка будет иметь O (n), которое является проклятием выделенных связанных списков.

0 голосов
/ 27 марта 2020

К сожалению, вы не можете сделать это за O (1) раз, так как нет никакого способа сделать это, вы должны компенсировать память для производительности и использовать двойной связанный список. Если у вас есть возможность использовать другие структуры данных, я бы предложил вам использовать Deque

...