線形リストを作ってみる その２

線形リストを作ってみる その１ - white wheelsのメモの続き。
push_back(最後尾に要素を挿入する), pop_back(最後尾の要素を削除する)を加え、好きな位置のノードにアクセスできるようにしてみます。

線形リストver2

List.h

#ifndef __List_H
#define __List_H

#include "Node.h"
class List
{
public:
	List(void);
	~List(void);
	void push_back(int data);	//要素を最後尾に追加する
	void pop_back();		//最後の要素を削除する
	void clear();			//全てのノードを削除する
	int operator[](unsigned int i);	//i番目の要素を取り出す

	void print();			//要素を表示する
private:
	void insert_next(Node* node,int data);//指定したnodeの後に追加
	void insert_prev(Node* node,int data);//指定したnodeの前に追加
	void erase(Node* node);		//指定したノードを削除する
	Node* node(unsigned int i);		//i番目のノードを取得する
	Node* m_root;
	int m_size;
};
#endif

要素の追加と削除

前に作成したinsertを再利用します。

void List::push_back(int data){
	insert_prev(m_root,data);
}

void List::pop_back(){
	erase(m_root->prev());
}

全ノードの削除

eraseを再利用します。rootが自分自身につながっていることを確認します。

void List::clear(){
	for(Node* node=m_root->next();node!=m_root;node=m_root->next()){
		erase(node);
	}
	m_size=0;
}

指定位置のノード・値の取得

範囲外の場合は例外処理を行う必要があります。今回はrootを返すようにしてみました。

Node* List::node(unsigned int i){
	int count=0;
	for(Node* node=m_root->next();node!=m_root;node=node->next()){
		if(count==i){
			return node;
		}
		count++;
	}
	return m_root;//out of range
}
int List::operator[](unsigned int i){
	return node(i)->data();
}

List.cpp

#include "List.h"

List::List(void):
m_size(0)
{
	m_root = new Node();
	m_root->next() = m_root;	//rootノードの前後を自分自身にしておく
	m_root->prev() = m_root;
}

List::~List(void)
{
	clear();
	delete m_root;
}
int List::operator[](unsigned int i){
	return node(i)->data();
}
void List::push_back(int data){
	insert_prev(m_root,data);
}

void List::pop_back(){
	erase(m_root->prev());
}

void List::clear(){
	for(Node* node=m_root->next();node!=m_root;node=m_root->next()){
		erase(node);
	}
	m_size=0;
}

void List::insert_next(Node* node,int data){
	if(node==0){
		return;
	}
	Node* new_node=new Node();//新たに追加したnode

	new_node->prev()=node;
	new_node->next()=node->next();
	node->next()->prev()=new_node;
	node->next()=new_node;
	new_node->data()=data;	//追加したnodeの値を設定
	m_size++;
}
void List::insert_prev(Node* node,int data){
	if(node==0){
		return;
	}
	Node* new_node=new Node();//新たに追加したnode

	new_node->prev()=node->prev();
	new_node->next()=node;
	node->prev()->next()=new_node;
	node->prev()=new_node;
	new_node->data()=data;//追加したnodeの値を設定
	m_size++;
}

void List::erase(Node* node){
	if(node==0 || node==m_root){	//rootは削除しない
		return;
	}
	node->prev()->next()=node->next();
	node->next()->prev()=node->prev();
	delete node;
	m_size--;
}

Node* List::node(unsigned int i){
	int count=0;
	for(Node* node=m_root->next();node!=m_root;node=node->next()){
		if(count==i){
			return node;
		}
		count++;
	}
	return m_root;//out of range
}

#include <iostream>
using namespace std;
//要素を表示する
void List::print(){
	cout <<"(root) "<<"\t\t";
	m_root->print();
	int count=0;
	for(Node* node=m_root->next();node!=m_root;node=node->next()){
		cout <<"(node"<<count<<") "<<"\t";
		node->print();
		count++;
	}
}

線形リストクラスの利用

#include "List.h"
#include <iostream>
using namespace std;
int main(){
	List list;
	list.print();	cout << endl;
	list.push_back(1);
	list.print();	cout << endl;
	list.push_back(2);
	list.print();	cout << endl;
	list.push_back(3);
	list.print();	cout << endl;

	list.pop_back();
	list.print();		cout << endl;
	cout<<list[1]<<endl;;
	
	list.clear();
	list.print();	cout << endl;

	list.pop_back();
	list.print();	cout << endl;
	cout<<list[2]<<endl;;

	return 0;
}

(root) prev[00868FC8] [00868FC8,data=0] next[00868FC8]

(root) prev[00862328] [00868FC8,data=0] next[00862328]
(node0) prev[00868FC8] [00862328,data=1] next[00868FC8]

(root) prev[00862360] [00868FC8,data=0] next[00862328]
(node0) prev[00868FC8] [00862328,data=1] next[00862360]
(node1) prev[00862328] [00862360,data=2] next[00868FC8]

(root) prev[00862398] [00868FC8,data=0] next[00862328]
(node0) prev[00868FC8] [00862328,data=1] next[00862360]
(node1) prev[00862328] [00862360,data=2] next[00862398]
(node2) prev[00862360] [00862398,data=3] next[00868FC8]

(root) prev[00862360] [00868FC8,data=0] next[00862328]
(node0) prev[00868FC8] [00862328,data=1] next[00862360]
(node1) prev[00862328] [00862360,data=2] next[00868FC8]

2
(root) prev[00868FC8] [00868FC8,data=0] next[00868FC8]

(root) prev[00868FC8] [00868FC8,data=0] next[00868FC8]

0