首页 > 代码库 > 双向链表(插入,删除,追加,正反向遍历,查找。。。)
双向链表(插入,删除,追加,正反向遍历,查找。。。)
#include <iostream> #include <stdexcept> using namespace std; class List { public: List(void) : m_head(NULL), m_tail(NULL), m_size(0){} ~List(void) { for(Node* node = m_head; m_head; m_head = node) { node = m_head->m_next; delete m_head; } } //在Index处插入元素 void insert(int data, size_t index) { //如果下标超过元素个数,则追加在链表最后 if(index >= m_size) { append(data); return; } Node* temp = new Node(data); //如果下标为0,则插入在头节点 if(0 == index) { temp->m_next = m_head; m_head->m_prev = temp; m_head = temp; ++m_size; return; } size_t count = 1; //其它情况 for(Node* node = m_head->m_next; node; node = node->m_next) { if(index == count) { temp->m_next = node; temp->m_prev = node->m_prev; node->m_prev->m_next = temp; node->m_prev = temp; ++m_size; return; } ++count; } } //在链表尾部追加元素 void append(int data) { Node* node = new Node(data); if(!m_head) m_head = node; else { node->m_prev = m_tail; m_tail->m_next = node; } m_tail = node; ++m_size; } //删除元素 void erase(size_t index) { if(!m_head) throw UnderFlow(); //首先查找要删除的元素 Node*& node = find(index, m_head); node->m_prev->m_next = node->m_next; node->m_next->m_prev = node->m_prev; delete node; node = NULL; } //查找元素 int& find(size_t index) { Node*& node = find(index, m_head); return node->m_data; } //正向遍历 void forward ()const { if(!m_head) throw UnderFlow(); for(Node* node = m_head; node; node = node->m_next) { cout << node->m_data << ' '; } cout << endl; } //反向遍历 void backward()const { if(!m_tail) throw UnderFlow(); for(Node* node = m_tail; node; node = node->m_prev) { cout << node->m_data << ' '; } cout << endl; } //链表元素个数 size_t size() { return m_size; } //重载下标操作符,作为左值 int& operator[] (size_t index) { if(index >= m_size) throw OverFlow(); Node*& node = find(index, m_head); return node->m_data; } //重载下标操作符,作为右值 const int& operator[] (size_t index)const { //去常属性后,调用上面下标重载 return const_cast<List&>(*this) [index]; } private: //链表每个节点 class Node { public: Node(int data=http://www.mamicode.com/0, Node* prev=NULL, Node* next=NULL):>双向链表(插入,删除,追加,正反向遍历,查找。。。)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。