单向链表与单向循环链表

1
2
3
4

struct Node {
  element_type data;
  Node* next;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

class SinglyLinkedList {
    // 结点类型
    struct Node {
        Node(int data)
            : data_{data},
              next_{nullptr} {}
        int data_;
        Node* next_;
    };

public:
    // 无参构造
    SinglyLinkedList()
        : head_{new Node{}} {}
    // 析构函数，释放单向链表中的每一个结点
    ~SinglyLinkedList() {}
  
private:
    // 单向链表的数据成员
    Node* head_;  // 指向单向链表的头结点的指针
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 尾插法插入结点
void insertTail(int val) {
        // 1. 找到尾部结点
        Node* tail = head_;
        while (tail->next_ != nullptr) {
            tail = tail->next_;
        }

        // 2. 以val构建新的结点
        Node* new_node = new Node{val};

        // 将尾结点的next_指向新的结点
        tail->next_ = new_node;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// 头插法插入结点
void insertHead(int val) {
    // 0. 先构建新的结点
    Node* new_node = new Node{val};

    // 1. 若链表中除头结点之外无有效结点
    if (head_->next_ == nullptr) {
        // 1.1 将头结点的next指针域赋值为新的结点
        head_->next_ = new_node;
        // 1.2 新结点的next指针域赋值为nullptr
        new_node->next_ = nullptr;
        return;
    }

    // 2. 否则，该链表中除头结点外还有至少有一个有效结点
    // 2.1 将新结点的next指针域赋值为当前链表中第一个有效结点的地址
    new_node->next_ = head_->next_;

    // 2.2 将头结点的next指针域赋值为新结点的地址
    head_->next_ = new_node;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void insertHead() {        
    // 1. 创建新的结点
    Node* new_node = new Node{val};

    // 2. 执行第一步操作
    new_node->next_ = head_->next_;

    // 3. 执行第二步操作
    head_->next_ = new_node;
}

1
2
3
4
5
6
7
8
9

std::ostream& operator<<(std::ostream& os, const SinglyLinkedList& sll) {
    SinglyLinkedList::Node* p = sll.head_->next_;
    while (p != nullptr) {
        os << p->data_ << " ";
        p = p->next_;
    }

    return os;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 按值删除结点
void remove(int val) {
    // 若链表无有效结点
    if (head_->next_ == nullptr){
        return;
    }
    // q初始指向头结点
    Node* q = head_;
    // p初始指向第一个有效结点
    Node* p = head_->next_;

    // 循环遍历找到值为val的结点
    while (p != nullptr) {
        // 判断当前p指向的结点的数据域为val
        if (p->data_ == val) {
            // q指向的结点的next域修改为p指向结点的next域值
            q->next_ = p->next_;
            // 释放p指向的结点
            delete p;
            break;
        } else {  // 若当前p指向的结点的数据域不为val
            // q向前进一个结点，也就是p的值
            q = p;

            // p向前进一个结点，也就是p->next的值
            p = p->next_;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 3. 测试remove
void test_remove() {
    SinglyLinkedList sll;

    for (int i = 0; i < 10; ++i) {
        sll.insertHead(i * 23);
    }

    std::cout << sll << std::endl; /* 207 184 161 138 115 92 69 46 23 0 */

    // 删除161 207 0
    sll.remove(161);
    std::cout << sll << std::endl;

    sll.remove(207);
    std::cout << sll << std::endl;

    sll.remove(0);
    std::cout << sll << std::endl;
}

1
2
3
4

207 184 161 138 115 92 69 46 23 0
207 184 138 115 92 69 46 23 0
184 138 115 92 69 46 23 0
184 138 115 92 69 46 23

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 按值删除多个结点
void remove_all(int val) {
    // 若链表无有效结点
    if (head_->next == nullptr) {
        return;
    }
    Node* q = head_;
    Node* p = head_->next_;

    while (p != nullptr) {
        if (p->data_ == val) {
            q->next_ = p->next_;

            delete p;

            // 重置p的值，指向原来p的下一个结点(next)
            p = q->next_;
        } else {
            q = p;
            p = p->next_;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//测试remove_all
void test_remove_all() {
    SinglyLinkedList sll;

    for (int i = 11; i < 20;++i) {
        sll.insertTail(i * 3);
    }

    std::cout << sll << std::endl;/* 33 36 39 42 45 48 51 54 57 */

    // 头部插入42
    sll.insertHead(42);

    // 尾部插入42
    sll.insertTail(42);

    std::cout << sll << std::endl;

    // 删除42，所有等于42的结点全部删除
    sll.remove_all(42);

    std::cout << sll << std::endl;
}

1
2
3

33 36 39 42 45 48 51 54 57
42 33 36 39 42 45 48 51 54 57 42
33 36 39 45 48 51 54 57

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 析构函数，释放单向链表中的每一个结点
~SinglyLinkedList() {
    // 定义一个新的指针p指向head
    Node* p = head_;

    // 循环删除结点(包括头结点)
    while (head_ != nullptr) {
        // 保存下一个有效结点，使其成为头结点
        head_ = head_->next_;

        // 删除旧的头结点
        delete p;

        // 使其p指向新的头结点，以便删除
        p = head_;
    }

    head_ = nullptr;
}

1
2

clang++ -std=c++14 singly_linked_list.cc -fsanitize=address,undefined
ASAN_OPTIONS=detect_leaks=1 ./a.out

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

==7127==AddressSanitizer: libc interceptors initialized
|| `[0x107000020000, 0x7fffffffffff]` || HighMem    ||
|| `[0x027e00024000, 0x10700001ffff]` || HighShadow ||
|| `[0x007e00024000, 0x027e00023fff]` || ShadowGap  ||
|| `[0x007000020000, 0x007e00023fff]` || LowShadow  ||
|| `[0x000000000000, 0x00700001ffff]` || LowMem     ||
MemToShadow(shadow): 0x007e00024000 0x007fc00247ff 0x00bfc0024800 0x027e00023fff
redzone=16
max_redzone=2048
quarantine_size_mb=256M
thread_local_quarantine_size_kb=1024K
malloc_context_size=30
SHADOW_SCALE: 3
SHADOW_GRANULARITY: 8
SHADOW_OFFSET: 0x7000020000
==7127==Installed the sigaction for signal 11
==7127==Installed the sigaction for signal 10
==7127==Installed the sigaction for signal 8
==7127==T0: stack [0x00016e9c0000,0x00016f1bc000) size 0x7fc000; local=0x00016f1b9098
==7127==AddressSanitizer Init done
a.out(7127,0x1f3bc10c0) malloc: nano zone abandoned due to inability to reserve vm space.
33 36 39 42 45 48 51 54 57
42 33 36 39 42 45 48 51 54 57 42
33 36 39 45 48 51 54 57
==7127==LeakSanitizer: checking for leaksAddressSanitizer: reading suppressions file at /Users/bitofux/Exercises/lsan_suppressions.txt
-----------------------------------------------------
Suppressions used:
  count      bytes template
      3        120 *fetchInitializingClassList*
-----------------------------------------------------

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

 // 搜索
bool find(int val) const {
    // p指向第一个有效结点
    Node* p = head_->next_;

    // 遍历整个链表
    while (p != nullptr) {
        // 若数据域等于val
        if (p->data_ == val) {
            return true;
        } else {            // 若不等于
            p = p->next_;  // 移动p的指向
        }
    }

    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <ostream>
#include <random>

class SinglyCircleLinkedList {
    struct Node {
        Node(int data = 0)
            : data_{data},
              next_{nullptr} {}
        int data_;
        Node* next_;
    };

public:
    friend std::ostream& operator<<(std::ostream& os, const SinglyCircleLinkedList& scll);

private:
    Node* head_;  // 指向头结点
    Node* tail_;  // 指向尾结点
};

std::ostream& operator<<(std::ostream& os, const SinglyCircleLinkedList& scll) {
    SinglyCircleLinkedList::Node* p = scll.head_->next_;

    while (p != scll.head_) {
        os << p->data_ << " ";
        p = p->next_;
    }
    return os;
}

1
2
3
4
5
6
7

SinglyCircleLinkedList()
    : head_{new Node} {
    // 初始阶段，尾指针和头指针都指向头结点
    tail_ = head_;
    // 将头结点也看作是尾结点，其next指向head
    tail_->next_ = head_;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

~SinglyCircleLinkedList() {
    // 定义指针p指向第一个有效结点用于删除
    Node* p = head_->next_;

    while (p != head_) {
        // head_指向p指向的下一个结点
        head_->next_ = p->next_;
        // 释放p
        delete p;
        // 重置p的值，用于删除下一个有效结点
        p = head_->next_;
    }

    // 删除头结点
    delete head_;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 头插法
void insertHead(int val) {
    // 构建一个新的结点
    Node* new_node = new Node{val};

    // 插入新结点
    new_node->next_ = head_->next_;
    head_->next_ = new_node;

    // 判断new_node中next指针域的值，若是head，则表明插入这个结点
    // 之前，此链表是一个空链表，需要更新tail的值
    if (new_node->next_ == head_) tail_ = new_node;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 测试头插法
void test_insert_head() {
    SinglyCircleLinkedList scll;

    // 初始化随机设备
    std::random_device rd;

    // 使用19937算法
    std::mt19937 gen(rd());

    std::uniform_int_distribution<> distrib(1, 100);

    for (int i = 0; i < 5; ++i) {
        int val = distrib(gen);
        scll.insertHead(val);
        std::cout << scll << std::endl;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

51
first->51
tail ->51

76 51
first->76
tail ->51

80 76 51
first->80
tail ->51

36 80 76 51
first->36
tail ->51

25 36 80 76 51
first->25
tail ->51

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 // 尾插法
void insertTail(int val) {
    // 构建一个新的结点
    Node* new_node = new Node{val};

    // 插入新结点
    tail_->next_ = new_node;

    // 更新tail_的指向
    tail_ = new_node;
    tail_->next_ = head_;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 测试尾插法
void test_insert_tail() {
    SinglyCircleLinkedList scll;

    // 初始化随机设备
    std::random_device rd;

    // 随机算法
    std::mt19937 gen{rd()};

    // 定义随机数的生成区间
    std::uniform_int_distribution<> distrib(1, 100);

    // 尾插10个数据
    for (int i = 0; i < 5; ++i) {
        int val = distrib(gen);
        scll.insertTail(val);
        std::cout << scll << "\n";
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

77
first->77
tail ->77

77 40
first->77
tail ->40

77 40 6
first->77
tail ->6

77 40 6 45
first->77
tail ->45

77 40 6 45 28
first->77
tail ->28

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 删除值为val的结点
void remove(int val) {
    if (head_->next_ == head_) {
        return;
    }

    Node* p = head_->next_;
    Node* q = head_;

    while (p != head_) {
        if (p->data_ == val) {
            q->next_ = p->next_;
            delete p;

            // 若删除的p指向的是尾结点，需要更新tail的值
            if (q->next_ == head_) {
                tail_ = q;
            }
            break;
        } else {
            q = p;
            p = p->next_;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void test_remove() {
    SinglyCircleLinkedList scll;

    // 初始化随机设备
    std::random_device rd;

    // 使用19937算法
    std::mt19937 gen(rd());

    std::uniform_int_distribution<> distrib(1, 10);

    for (int i = 0; i < 20; ++i) {
        int val = distrib(gen);
        scll.insertHead(val);
    }
    std::cout << scll << std::endl;

    // 删除值为6的单个结点
    scll.remove(6);
    std::cout << scll << std::endl;

    // 插入一个尾结点，并删除，查看tail是否更新
    scll.insertTail(20);
    std::cout << scll << std::endl;
    scll.remove(20);
    std::cout << scll << std::endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

6 6 9 1 1 1 9 4 1 10 4 2 3 8 10 3 3 10 5 6
first->6
tail ->6

6 9 1 1 1 9 4 1 10 4 2 3 8 10 3 3 10 5 6
first->6
tail ->6

6 9 1 1 1 9 4 1 10 4 2 3 8 10 3 3 10 5 6 20
first->6
tail ->20

6 9 1 1 1 9 4 1 10 4 2 3 8 10 3 3 10 5 6
first->6
tail ->6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 // 删除值为val的全部结点
void remove_all(int val) {
    if (head_->next_ == head_) {
        return;
    }
    Node* p = head_->next_;
    Node* q = head_;

    while (p != head_) {
        if (p->data_ == val) {
            q->next_ = p->next_;
            delete p;

            // 若删除的p指向的是尾结点，需要更新tail的值
            if (q->next_ == head_) {
                tail_ = q;
                break;
            }
            // 若不是，则更新p的值，以供下一次删除
            p = q->next_;
        } else {
            q = p;
            p = p->next_;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void test_remove() {
    SinglyCircleLinkedList scll;

    // 初始化随机设备
    std::random_device rd;

    // 使用19937算法
    std::mt19937 gen(rd());

    std::uniform_int_distribution<> distrib(1, 10);

    for (int i = 0; i < 20; ++i) {
        int val = distrib(gen);
        scll.insertHead(val);
    }
    std::cout << scll << std::endl;

    // 删除值为6的单个结点
    scll.remove_all(6);
    std::cout << scll << std::endl;

    // 插入一个尾结点，并删除，查看tail是否更新
    scll.insertTail(30);
    std::cout << scll << std::endl;
    scll.remove_all(30);
    std::cout << scll << std::endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

10 2 10 5 6 7 2 1 2 3 2 4 4 4 4 2 6 7 1 10
first->10
tail ->10

10 2 10 5 7 2 1 2 3 2 4 4 4 4 2 7 1 10
first->10
tail ->10

10 2 10 5 7 2 1 2 3 2 4 4 4 4 2 7 1 10 30
first->10
tail ->30

10 2 10 5 7 2 1 2 3 2 4 4 4 4 2 7 1 10
first->10
tail ->10