基于c++创建列表，从尾部添加数据

在 C 语言中，可以使用链表来创建列表，并从尾部添加数据。

链表是一种动态数据结构，允许您在运行时动态地添加或删除元素。它由节点组成，每个节点都包含数据和指向下一个节点的指针。

要创建链表，需要定义一个结构体来表示每个节点，包括数据域和指针域。例如：

struct node {
  int data;
  struct node *next;
};

然后，可以使用 malloc 函数为新节点分配内存，并使用指针操作来更新指针。例如，以下代码演示了如何在链表的尾部添加一个新节点：

struct node *head = NULL;  // 初始化头指针

// 创建新节点
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = 5;
new_node->next = NULL;

// 如果链表为空，则将新节点设为头节点
if (head == NULL) {
  head = new_node;
} else {
  // 否则，遍历链表，找到最后一个节点
  struct node *current = head;
  while (current->next != NULL) {
    current = current->next;
  }
  // 将新节点添加到最后一个节点的后面
  current->next = new_node;
}

注意：在使用链表时，需要注意内存管理

相关问题

LRU 缓存 基于哈希表 C++

LRU 缓存基于哈希表的实现可以使用 STL 中的 `std::unordered_map`，这个容器提供了 O(1) 的查找和插入操作，非常适合用于实现缓存。下面是一个基于哈希表实现的 LRU 缓存的 C++ 代码：

#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto iter = cache_.find(key);
        if (iter == cache_.end()) {
            return -1;
        } else {
            auto value = iter->second->second;
            cache_list_.splice(cache_list_.begin(), cache_list_, iter->second);
            iter->second = cache_list_.begin();
            return value;
        }
    }

    void put(int key, int value) {
        auto iter = cache_.find(key);
        if (iter == cache_.end()) {
            if (cache_.size() == capacity_) {
                int key_to_remove = cache_list_.back().first;
                cache_.erase(key_to_remove);
                cache_list_.pop_back();
            }
            cache_list_.push_front({key, value});
            cache_[key] = cache_list_.begin();
        } else {
            iter->second->second = value;
            cache_list_.splice(cache_list_.begin(), cache_list_, iter->second);
            iter->second = cache_list_.begin();
        }
    }

private:
    int capacity_;
    std::list<std::pair<int, int>> cache_list_;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache_;
};

在这个实现中，我们使用了一个双向链表 `cache_list_` 来保存缓存中的数据，并使用一个哈希表 `cache_` 来提高查找效率。在 `get` 操作中，我们先在哈希表中查找目标数据，如果不存在则返回 -1，否则将目标数据移到链表头部并返回其值。在 `put` 操作中，如果缓存中不存在目标数据则创建一个新的节点并将其添加到链表头部，如果缓存已满则删除链表尾部的节点。如果缓存中已存在目标数据则将其值更新并将其移动到链表头部。

需要注意的是，在 `get` 操作中，我们需要使用 `splice` 操作将目标节点移到链表头部，并更新哈希表中对应节点的指针。在 `put` 操作中，我们需要先判断缓存是否已满，如果已满则删除链表尾部的节点，并在哈希表中删除对应的键值对。然后我们将新节点添加到链表头部，并在哈希表中创建对应的键值对。

另外，由于我们使用了 STL 中的 `std::list`，所以我们可以直接使用 `push_front` 和 `pop_back` 操作来添加和删除链表节点，非常方便。

用C++实现一个基于模板的双向循环链表并加上详细的注释

好的，以下是基于模板的双向循环链表的实现代码，注释详细：

#include <iostream>
using namespace std;

// 定义节点结构体
template<typename T>
struct Node {
    T data; // 节点中存储的数据
    Node<T>* next; // 指向下一个节点的指针
    Node<T>* prev; // 指向前一个节点的指针
};

// 定义双向循环链表类
template<typename T>
class DoublyLinkedList {
private:
    Node<T>* head; // 头节点指针
    Node<T>* tail; // 尾节点指针
    int size; // 链表大小
public:
    // 构造函数
    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }

    // 析构函数
    ~DoublyLinkedList() {
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* temp = current;
            current = current->next;
            delete temp;
        }
        size = 0;
    }

    // 获取链表大小
    int getSize() {
        return size;
    }

    // 判断链表是否为空
    bool isEmpty() {
        return size == 0;
    }

    // 在链表头部添加元素
    void addFirst(T data) {
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        if (head == nullptr) { // 如果链表为空
            head = newNode;
            tail = newNode;
            head->prev = tail;
            tail->next = head;
        } else { // 如果链表不为空
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
            head->prev = tail;
            tail->next = head;
        }
        size++;
    }

    // 在链表尾部添加元素
    void addLast(T data) {
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        if (tail == nullptr) { // 如果链表为空
            head = newNode;
            tail = newNode;
            head->prev = tail;
            tail->next = head;
        } else { // 如果链表不为空
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
            head->prev = tail;
            tail->next = head;
        }
        size++;
    }

    // 在指定位置插入元素
    void add(int index, T data) {
        if (index < 0 || index > size) {
            cout << "Index out of range." << endl;
            return;
        }
        if (index == 0) { // 在链表头部插入元素
            addFirst(data);
            return;
        }
        if (index == size) { // 在链表尾部插入元素
            addLast(data);
            return;
        }
        Node<T>* current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        newNode->next = current->next;
        current->next->prev = newNode;
        current->next = newNode;
        newNode->prev = current;
        size++;
    }

    // 删除链表头部元素
    void removeFirst() {
        if (head == nullptr) {
            cout << "LinkedList is empty." << endl;
            return;
        }
        if (head == tail) { // 链表中只有一个节点
            delete head;
            head = nullptr;
            tail = nullptr;
        } else { // 链表中有多个节点
            Node<T>* temp = head;
            head = head->next;
            head->prev = tail;
            tail->next = head;
            delete temp;
        }
        size--;
    }

    // 删除链表尾部元素
    void removeLast() {
        if (tail == nullptr) {
            cout << "LinkedList is empty." << endl;
            return;
        }
        if (head == tail) { // 链表中只有一个节点
            delete tail;
            head = nullptr;
            tail = nullptr;
        } else { // 链表中有多个节点
            Node<T>* temp = tail;
            tail = tail->prev;
            tail->next = head;
            head->prev = tail;
            delete temp;
        }
        size--;
    }

    // 删除指定位置的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            cout << "Index out of range." << endl;
            return;
        }
        if (index == 0) { // 删除链表头部元素
            removeFirst();
            return;
        }
        if (index == size - 1) { // 删除链表尾部元素
            removeLast();
            return;
        }
        Node<T>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }

    // 获取指定位置的元素
    T get(int index) {
        if (index < 0 || index >= size) {
            cout << "Index out of range." << endl;
            return NULL;
        }
        Node<T>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        return current->data;
    }

    // 修改指定位置的元素
    void set(int index, T data) {
        if (index < 0 || index >= size) {
            cout << "Index out of range." << endl;
            return;
        }
        Node<T>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        current->data = data;
    }

    // 打印链表
    void printList() {
        if (head == nullptr) {
            cout << "LinkedList is empty." << endl;
            return;
        }
        Node<T>* current = head;
        while (current != tail) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << current->data << endl;
    }
};

int main() {
    // 创建双向循环链表对象
    DoublyLinkedList<int> dll;

    // 在链表头部添加元素
    dll.addFirst(1);
    dll.addFirst(2);
    dll.addFirst(3);
    dll.printList(); // 输出： 3 2 1

    // 在链表尾部添加元素
    dll.addLast(4);
    dll.addLast(5);
    dll.addLast(6);
    dll.printList(); // 输出： 3 2 1 4 5 6

    // 在指定位置插入元素
    dll.add(2, 7);
    dll.printList(); // 输出： 3 2 7 1 4 5 6

    // 删除链表头部元素
    dll.removeFirst();
    dll.printList(); // 输出： 2 7 1 4 5 6

    // 删除链表尾部元素
    dll.removeLast();
    dll.printList(); // 输出： 2 7 1 4 5

    // 删除指定位置的元素
    dll.remove(2);
    dll.printList(); // 输出： 2 7 4 5

    // 获取指定位置的元素
    cout << dll.get(2) << endl; // 输出： 4

    // 修改指定位置的元素
    dll.set(2, 8);
    dll.printList(); // 输出： 2 7 8 5

    return 0;
}

这里实现了双向循环链表的基本操作，包括在链表头部、尾部和指定位置插入元素，删除链表头部、尾部和指定位置的元素，获取指定位置的元素和修改指定位置的元素等。在实现过程中，我们采用了模板化编程，使得该链表可以存储任意类型的数据。同时，为了更好地理解和使用该链表，我们在每个函数中都添加了详细的注释。