C++中双向链表

#include <iostream>

using namespace std;

class List {

public:

// 构造函数中初始化为空链表

List (void) : m_head (NULL), m_tail (NULL) {}

// 析构函数中销毁剩余的节点

~List (void) {

for (Node* next; m_head; m_head = next) {

next = m_head -> m_next;

delete m_head;

}

/**/

/*

Node * next;

while(m_head)

{

next=m_head->m_next;

delete m_head;

}

*/

}

// 追加

void append (int data) {

/*

Node* node = new Node;

node -> m_data = data;

node -> m_prev = m_tail;

node -> m_next = NULL;

m_tail = node;

*/

m_tail = new Node (data, m_tail);

if (m_tail -> m_prev)

m_tail -> m_prev -> m_next = m_tail;

else

m_head = m_tail;

}

// 插入

void insert (size_t index, int data) {

for (Node* find = m_head; find;

find = find -> m_next)

if (index-- == 0) 

{

Node* node = new Node (data,

find -> m_prev, find);

if (node -> m_prev)

node -> m_prev -> m_next = node;

else

m_head = node;

node -> m_next -> m_prev = node;

return;

}

throw OverBound ();

}

// 删除

void erase (size_t index) {

for (Node* find = m_head; find;

find = find -> m_next)

if (index-- == 0) {

if (find -> m_prev)

find -> m_prev -> m_next =

find -> m_next;

else

m_head = find -> m_next;

if (find -> m_next)

find -> m_next -> m_prev =

find -> m_prev;

else

m_tail = find -> m_prev;

delete find;

return;

}

throw OverBound ();

}

// 正遍历

void forward (void) const {

for (Node* node = m_head; node;

node = node -> m_next)

cout << node -> m_data << ' ';

cout << endl;

}

// 反遍历

void backward (void) const {

for (Node* node = m_tail; node;

node = node -> m_prev)

cout << node -> m_data << ' ';

cout << endl;

}

// 下标运算符

int& operator[] (size_t index) {

for (Node* find = m_head; find;

find = find -> m_next)

if (index-- == 0)

return find -> m_data;

throw OverBound ();

}

const int& operator[] (size_t index) const {

return const_cast<List&> (*this) [index];

}

// 测长

size_t length (void) const {

size_t len = 0;

for (Node* node = m_head; node;

node = node -> m_next)

len++;

return len;

}

private:

// 越界异常

class OverBound : public exception {

public:

const char* what (void) const throw () {

return "链表越界！";

}

};

// 节点

class Node {

public:

Node (int data = 0, Node* prev = NULL,

Node* next = NULL) :

m_data (data), m_prev (prev),

m_next (next) {}

int   m_data; // 数据

Node* m_prev; // 前指针

Node* m_next; // 后指针

};

Node* m_head; // 头指针

Node* m_tail; // 尾指针

};

int main (void) {

try {

List list;

list.append (10);

list.append (20);

list.append (50);

list.append (60);

list.append (80);

list.forward ();

list.insert (1, 15);

list.insert (3, 40);

list.insert (6, 70);

list.backward ();

list.erase (1);

list.erase (2);

list.erase (4);

list.forward ();

size_t len = list.length ();

for (size_t i = 0; i < len; i++)

list[i]++;

const List& cr = list;

for (size_t i = 0; i < len; i++)

cout << cr[i] << ' ';

cout << endl;

// cout << cr[10] << endl;

}

catch (exception& ex) {

cout << ex.what () << endl;

return -1;

}

return 0;

}