double linked list双向链表

90 阅读 0 评论 60 点赞

我是靠谱客的博主开心鼠标，这篇文章主要介绍double linked list双向链表，现在分享给大家，希望可以做个参考。

[tags] C++

- - 双向链表的实现与单向链表相近
    - 节点结构体
    - 类声明
  - 总结

双向链表的实现（与单向链表相近）

1. 节点结构体

复制代码

1
2
3
4
5
6
7
8
9
struct DouListNode {
int elem;
DouListNode *prev, *next;
DouListNode(int e = 0, DouListNode *p = 0, DouListNode *n = 0) {
elem = e;
prev = p;
next = n;
}
};

2. 类声明

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class DouList {
private:
DouListNode *m_head, *m_tail;
public:
DouList();
DouList(const DouList &src);
~DouList();
void clear();
bool empty() const;
string to_str() const;
int front() const;
int back() const;
void push_front(const int &e);
void push_back(const int &e);
void pop_front();
void pop_back();
void operator=(const DouList &other);
friend ostream& operator<<(ostream &out,
const DouList &list);
// non-meaning static value
static int _error_sign;
// for illegal front()/back()
};

（1）构造函数

复制代码

1
2
3
4
5
6
7
8
9
DouList::DouList() {
m_head = NULL;
m_tail = NULL;
}
DouList::DouList(const DouList& src) {
m_head = NULL;
m_tail = NULL;
*this = src;
}

**注意拷贝构造函数中要写m_head = NULL; m_tail = NULL;
每次定义一个成员函数都要考虑特殊值和边界情况
此处调用了重载运算符=

拷贝构造函数是关键，每次出现内存问题都应当重点检查拷贝构造函数
（2）重载运算符=

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DouList::operator=(const DouList& other) {
this->clear();
//
先进行清空
if (other.empty()) return;
//
把不满足的情况先挡在外边，排除掉
m_head = new DouListNode(other.front());
// 里面的other.front()虽说可以直接用m_head并且也不麻烦，但是这样更加符合代码的可读性，尽量用上类中的成员函数，可以使代码更加的简洁
DouListNode* p = other.m_head->next;
DouListNode* q = m_head;
while (p != NULL) {
q->next = new DouListNode(p->elem, q, NULL);
p = p->next;
q = q->next;
}
m_tail = q;
}

（3）清空，析构中直接调用clear()即可

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void DouList::clear() {
if (!empty()) {
DouListNode* p = m_head;
while (p != NULL) {
DouListNode* t = p;
p = p->next;
delete t;
}
}
m_head = m_tail = NULL;
}
DouList::~DouList() {
clear();
}

（4）空链表的判断，当头节点和尾节点为同一节点时为空

复制代码

1
2
3
bool DouList::empty() const {
return (m_head == NULL && m_tail == NULL);
}

（5）打印的形式

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string DouList::to_str() const {
string result = "[";
if (m_head == NULL&&m_tail == NULL) {
result += "]";
} else {
stringstream ss1;
ss1 << m_head->elem;
result +=
ss1.str();
DouListNode* p = m_head->next;
while(p != NULL) {
stringstream ss;
ss << p->elem;
result += ", " + ss.str();
p = p->next;
}
result += "]";
}
return result;
}

（6）获得元素(m_head->elem 和m_tail->elem)

复制代码

1
2
3
4
5
6
int DouList::front() const {
if (m_head != NULL) return m_head->elem;
}
int DouList::back() const {
if (m_tail != NULL) return m_tail->elem;
}

（7）从链表的头插入元素（重要）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
void DouList::push_front(const int& e) {
//
首先考虑特殊情况，要养成首先考虑特殊情况的好习惯，或者是写完一个函数后重新考虑是否漏掉了特殊情况，这样就不会出现一大堆的内存问题
if (m_head == NULL && m_tail == NULL) {
DouListNode* t = new DouListNode(e);
m_head = m_tail = t;
return;
}
DouListNode* t = new DouListNode(e, NULL, m_head);
m_head->prev = t;
m_head = t;
}

（8）从链表的尾插入元素（重要）

复制代码

1
2
3
4
5
6
7
8
9
10
11
void DouList::push_back(const int& e) {
// 考虑特殊情况，与从头插入相同
if (m_head == NULL && m_head == NULL) {
DouListNode* t = new DouListNode(e);
m_head = m_tail = t;
return;
}
DouListNode* t = new DouListNode(e, m_tail, NULL);
m_tail->next = t;
m_tail = t;
}

（9）从头pop（重要）

复制代码

1
2
3
4
5
6
7
void DouList::pop_front() {
if (m_head == NULL && m_tail == NULL) return;
DouListNode* t = m_head;
m_head = m_head->next;
m_head->prev = NULL;
delete t;
}

（10）从尾pop（重要）

复制代码

1
2
3
4
5
6
7
void DouList::pop_back() {
if (m_head == NULL&&m_tail == NULL) return;
DouListNode* t = m_tail;
m_tail = m_tail->prev;
m_tail->next = NULL;
delete t;
}

（11）友元函数

复制代码

1
2
3
4
std::ostream& operator<<(std::ostream& out, const DouList& list) {
out << list.to_str();
return out;
}

记得不能写成：ostream& DouList::operator<<(std::ostream& out, const DouList& list)
会报错：
‘std::ostream& DouList::operator<<(std::ostream&, const DouList&)’ must take exactly one argument
因为友元函数不属于该类