1数组链表基础知识

前言

学习路线总纲
https://zhuanlan.zhihu.com/p/157355850

讲C++面向对象讲得很好
https://zhuanlan.zhihu.com/p/225175529

C++学习路线
https://tobebetterjavaer.com/xuexiluxian/ccc.html

数组和链表

• 数组特点：首地址已知，数组元素大小已知，存储连续
• 链表特点：存储不连续，根据next指针一个一个找
• 数组缺点：删除元素，后面的元素要挨个往前挪，总之要满足紧凑、连续的特性，有一定代价
• 链表缺点：多存储一个指针的空间

代码实现

• 数据结构的代码实现主要就是增删查改

• 数组：

  • 检查边界，注意增的边界可以<=
  • 末尾增：扩容2倍
  • 中间增：数据搬移，赋值
  • 末尾删：
    小于1/4时，缩容为一半
    最后一个元素置空，不能直接size-1
  • 中间删：数据搬移，删除最后一个元素

• 双向链表

  • 构造函数：哨兵节点，不用判断空节点

  • 插入元素：
    插入元素指针
    插入元素前一个的指针
    插入元素后一个的指针

  • 删除元素

  • 中间插入元素：

    遍历到第index个节点（优化，前向遍历和后向遍历）
    新节点指针
    前后两个元素的指针

//双链表节点结构体
struct LinkedNode {
    int val;
    LinkedNode* prev, * next;
    //struct构造函数
    LinkedNode(int _val) : val(_val), prev(nullptr), next(nullptr) {}
};

class MyLinkedList {
public:
    //构造函数
    MyLinkedList() {
        this->head = new LinkedNode(0);
        this->tail = new LinkedNode(0);
        head->next = tail;
        tail->prev = head;
        this->size = 0;
    }
private:
    int size;
    LinkedNode* head;
    LinkedNode* tail;

public:
//***** 增 *****
    void add(int index, int val) {
        //找到index对应的node，pred
        //pred <-> x <-> succ
        LinkedNode* pred, * succ;
        //前向遍历
        if (index < size - index) {
            pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred->next;
            }
            succ = pred->next;
        }
        //后向遍历
        else {
            succ = tail;
            for (int i = 0; i < size - index; i++) {
                succ = succ->prev;
            }
            pred = succ->prev;
        }
        //新插入node，x
        LinkedNode* x = new LinkedNode(val);

        pred->next = x;
        succ->prev = x;

        x->prev = pred;
        x->next = succ;
        
        size++;
    }
}