数组和链表

数组因为内存连续,随机访问性强,可通过下标进行快速定位,查找速度快;但在插入和删除效率低,都需要移动数据,对内存空间要求高,必须有足够的连续内存空间。

优点 缺点
内存连续,随机访问性强 必须有足够的连续的内存空间
查找速度快 插入和删除效率低

链表相比数组操作更加灵活,尤其在插入和删除上,不需要额外的数据移动,效率更高只需要改变指针的指向,不需要连续内存,利用率更高;但不能随机查找,必须从第一个元素开始遍历,查找效率低。

优点 缺点
不要求连续内存 查找效率低,不能随机查找
插入和删除的效率高 链接域需要占用额外内存

单链表和双链表

  • 单链表只有一个指向下一结点的指针next,只能单向读取。
  • 双链表除了next外,还有一个指向前一结点的指针prev,可以快速找到前一结点,因此查找和删除的效率更高;但链接域占用了更多的额外内存。

双链表为什么查找和删除的效率更高?

  1. 查找结点时,双链表可以借用二分法的思路,从head(首节点)向后查找,同时从last(尾节点)向前查找,因此效率更高。
  2. 删除结点时,双链表和单链表都需要定位前驱结点,但双链表查找结点效率高,因此删除的效率也高。

为什么市场上单链表的使用多于双链表呢?

  1. 从存储结构来看,每个双链表的节点要比单链表的节点多一个指针,总共需要额外 n*length的内存空间(指针length在32位系统中是4字节,在64位中是8字节)
  2. 如果不追求时间效率就会采用 以时间换空间 的做法,是一种工程总体上的衡量。

以上参考:浅谈单链表与双链表的区别

单链表的C++实现


first 指向的节点称为头结点,或哑节点(dummy Node),是人为创建的数据为空的节点,能够简化处理头节点为空的边界问题,统一空链表与非空链表的处理方式。

结点定义:

template <typename T>
struct Node
{
    T data;             // 数据域
    Node<T>* next;      // 链接域:指向下一个节点
};

链表声明:

template <typename T>
class LinkedList
{
public:
    LinkedList();							// 构造空链表
    void appand(T _data);					// 追加
    void insert(int _index, T _data);		// 插入
    void remove(int _index);  				// 移除
    T get(int _index);						// 取值
    int find(T _data);						// 查找
    bool empty();							// 判断是否为空
    int size();								// 长度

private:
    Node<T>* first;     // 指向哑结点
    int length;
};

链表实现: 遍历操作可以按照size循环,也可以按 p->next != nullptr 进行

template<typename T>
inline LinkedList<T>::LinkedList()
{
    // 创建空链表
    first = new Node<T>;
    first->next = nullptr;
    length = 0;
}

template<typename T>
inline void LinkedList<T>::appand(T _data)
{
    insert(length, _data);
}

template<typename T>
inline void LinkedList<T>::insert(int _index, T _data)
{
    // 边界检查
    assert(_index >= 0 && _index <= length);
    // 定位上一结点
    Node<T>* p = first;
    for (int i = 0; i < _index; ++i, p = p->next);
    // 重新链接
    Node<T>* node = new Node<T>;
    node->data = _data;
    node->next = p->next;
    p->next = node;
    length++;
}

template<typename T>
inline void LinkedList<T>::remove(int _index)
{
    // 边界检查
    assert(_index >= 0 && _index < length);
    // 定位上一结点
    Node<T>* p = first;
    for (int i = 0; i < _index; ++i, p = p->next);
    Node<T>* node = p->next;
    // 重新链接
    p->next = node->next;
    delete node;
    length--;
}

template<typename T>
inline T LinkedList<T>::get(int _index)
{
    // 边界检查
    assert(_index >= 0 && _index <= length);
    // 定位上一结点
    Node<T>* p = first;
    for (int i = 0; i < _index; ++i, p = p->next);
    // 取值
    return p->next->data;
}

template<typename T>
inline int LinkedList<T>::find(T _data)
{
    // 遍历结点
    Node<T>* p = first;
    int index = 0;
    for (index; index < length; ++index)
    {
        p = p->next;
        if(p->data == _data) break;
    }
    if (p->next == nullptr) return -1;
    return index;
}

template<typename T>
inline bool LinkedList<T>::empty()
{
    return first->next == nullptr;
}

template<typename T>
inline int LinkedList<T>::size()
{
    return length;
}

循环链表


循环链表的特点是无须增加存储量,仅对表的链接方式稍作改变,即可更加方便灵活地处理。

  1. 循环链表中没有NULL指针。遍历操作时,其终止条件就不再是单链表那样判别p或p->next是否为空,而是判别它们是否等于某一指定指针,如头指针或尾指针等。
  2. 在单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。
  3. 改用尾指针(rear)指示的循环单链表,不需要遍历整个链表,可以用 O ( 1 ) \mathcal{O}(1) O(1)的时间,直接获取首结点(rear->next->next)和尾结点(rear)。

注意循环判断条件,避免死循环。

std::list 双向循环链表

#include <iostream>
#include <list>

int main()
{
    // 创建含整数的 list
    std::list<int> l = { 0, 10, 20, 30 };

    // 添加整数到 list 开头
    l.push_front(-10);
    // 添加整数到 list 结尾
    l.push_back(99);

    // 以搜索插入 16 前的值
    auto iter = std::find(l.begin(), l.end(), 20);
    if (iter != l.end()) {
        l.insert(iter, 15);
    }

    // 打印首尾
    std::cout << "front: " << l.front() << ", back: " << l.back() << std::endl;

    // 迭代并打印 list 的值
    for (auto x : l) {
        std::cout << x << " <--> ";
    }
    std::cout << std::endl;
	
	// 迭代器打印
    for (auto iter=l.begin(); iter!=l.end();iter++ )
    {
        std::cout << *iter << " <--> ";
    }
    std::cout << std::endl;
    
    return 0;
}