C++模拟实现JDK中的ArrayList和LinkedList

介绍

在Java语言中，ArrayList和LinkedList是两种常见的List集合实现方式。ArrayList底层基于动态数组实现，适用于随机访问元素，但插入和删除操作效率较低。LinkedList底层基于双向链表实现，适用于频繁插入和删除操作，但访问元素效率较低。

本篇文章将介绍如何使用C++语言模拟实现ArrayList和LinkedList，实现它们基本的操作。

C++实现ArrayList

数据结构

在C++中，可以使用std::vector代替Java中的ArrayList，std::vector基于动态数组实现，使用前需要包含< vector >头文件。

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> arrlist;
    arrlist.push_back(1);
    arrlist.push_back(2);
    arrlist.push_back(3);
    for(int i=0; i<arrlist.size(); i++) {
        cout << arrlist[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果为：1 2 3

基本操作

在C++中，可以使用std::vector实现ArrayList的基本操作，包括插入、删除、获取元素、获取大小等。

vector<int> arrlist;
arrlist.push_back(1); // 插入元素1
arrlist.push_back(2); // 插入元素2
arrlist.push_back(3); // 插入元素3

arrlist.erase(arrlist.begin() + 1); // 删除第二个元素2
cout << arrlist[1] << endl; // 输出第二个元素3

string s = "size: " + to_string(arrlist.size()); // 获取元素个数
cout << s << endl; // 输出size: 2

C++实现LinkedList

数据结构

在C++中，可以使用自定义结构体实现链表，包括链表节点和链表类。

#include <iostream>

/* 链表节点 */
struct Node {
    int val; // 节点值
    Node* prev; // 前驱指针
    Node* next; // 后继指针
    Node(int val) : val(val), prev(nullptr), next(nullptr) {} // 构造函数
};

/* 链表类 */
class LinkedList {
public:
    LinkedList() : head(nullptr), tail(nullptr) {} // 构造函数

    void addFirst(int val); // 在头部添加节点
    void addLast(int val); // 在尾部添加节点
    void insert(int val, int index); // 在指定位置插入节点
    void removeFirst(); // 删除头部节点
    void removeLast(); // 删除尾部节点
    void remove(int index); // 删除指定位置的节点
    int get(int index); // 获取指定位置的节点值
    int size(); // 获取节点总数

private:
    Node* head; // 头节点指针
    Node* tail; // 尾节点指针
};

int main() {
    LinkedList linkedlist;
    linkedlist.addFirst(1);
    linkedlist.addLast(3);
    linkedlist.insert(2, 1);
    linkedlist.remove(1);
    std::cout << linkedlist.get(1) << std::endl;
    std::cout << linkedlist.size() << std::endl;
    return 0;
}

基本操作

在C++中，根据链表节点的前驱指针和后继指针，可以实现链表的基本操作，包括在头部、尾部和指定位置插入节点，删除头部、尾部和指定位置的节点，获取指定位置的节点值和获取总节点数。

void LinkedList::addFirst(int val) {
    Node* node = new Node(val);
    if(head == nullptr) {
        head = node;
        tail = node;
    } else {
        node->next = head;
        head->prev = node;
        head = node;
    }
}

void LinkedList::addLast(int val) {
    Node* node = new Node(val);
    if(tail == nullptr) {
        head = node;
        tail = node;
    } else {
        node->prev = tail;
        tail->next = node;
        tail = node;
    }
}

void LinkedList::insert(int val, int index) {
    Node* node = new Node(val);
    Node* p = head;
    for(int i=0; i<index-1 && p!=nullptr; i++) {
        p = p->next;
    }
    if(p == nullptr) { // 插入位置越界
        std::cout << "Out of range!" << std::endl;
        return;
    }
    if(p == head) {
        addFirst(val);
        return;
    }
    node->prev = p->prev;
    node->next = p;
    p->prev->next = node;
    p->prev = node;
}

void LinkedList::removeFirst() {
    if(head == nullptr) {
        return;
    }
    Node* p = head;
    head = head->next;
    if(head != nullptr) {
        head->prev = nullptr;
    } else {
        tail = nullptr;
    }
    delete p;
}

void LinkedList::removeLast() {
    if(tail == nullptr) {
        return;
    }
    Node* p = tail;
    tail = tail->prev;
    if(tail != nullptr) {
        tail->next = nullptr;
    } else {
        head = nullptr;
    }
    delete p;
}

void LinkedList::remove(int index) {
    Node* p = head;
    for(int i=0; i<index && p!=nullptr; i++) {
        p = p->next;
    }
    if(p == nullptr) { // 删除位置越界
        std::cout << "Out of range!" << std::endl;
        return;
    }
    if(p == head) {
        removeFirst();
        return;
    }
    if(p == tail) {
        removeLast();
        return;
    }
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
}

int LinkedList::get(int index) {
    Node* p = head;
    for(int i=0; i<index && p!=nullptr; i++) {
        p = p->next;
    }
    if(p == nullptr) { // 获取位置越界
        std::cout << "Out of range!" << std::endl;
        return -1;
    }
    return p->val;
}

int LinkedList::size() {
    Node* p = head;
    int count = 0;
    while(p != nullptr) {
        count++;
        p = p->next;
    }
    return count;
}

总结

本篇文章介绍了如何使用C++语言模拟实现ArrayList和LinkedList，基于std::vector实现了ArrayList的基本操作，基于自定义结构体实现了LinkedList的基本操作，包括插入、删除、获取元素和获取大小。