![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
データ構造講座1回 のバックアップ(No.4)
第1回はリストと呼ばれるものです
リストというのは
ノードとよばれるものにデータを格納して
そのノード同士を直列にポインタでつないだものです
イメージ的には乾電池の直列つなぎです
リストの利点はデータの挿入や（先頭末尾以外の）削除などが高速です
なぜなら、つなぎなおしの際にポインタを繋ぎなおす箇所が
最大でも（双方向の場合）4箇所で済むからです
それに反してデータへのアクセスは
ノードをたどって調べていかなければならないので
配列などに比べて低速です
ノードを並列繋ぎをすると木（ツリー）構造になります
（実際には木はもっと複雑ですが）
もっとも簡単なノードの書き方は次のようになります
struct node
{
node* next;
int data;
};
nodeという構造体の中に自分自身のポインタ(node*)を持っています
int data;としていますが
一般的には格納するデータの構造体などをノードに持たせます
struct Data
{
char name[256];
int index;
float something;
};
struct node
{
node* next;
Data data;
// ノード生成時(newされたとき)初期化
node():next(NULL)
{
memset(data,0,sizeof(Data));
}
};
ノードを追加するときはnewします
node* head = NULL; // 全ノードの先頭ノード Data somedata; // 先頭ノードがなければ作成 if(head == NULL) head = new node; // 追加したい場合nextにnewする head->next = new node; // 追加したノードにデータを格納 head->next->data = somedata; // さらに追加したい場合、さらにたどってnewします head->next->next = new node;
リストの強みは途中に追加したい場合です
(あと削除をしたい場合)
node* newnode = newnode; node* tmpnode; // つなぎなおすところを一時保存 tmpnode = head->next->next; // 挿入 head->next = newnode; // つなぎなおし newnode->next = tmpnode;
終了処理はめんどくさいです
たどりつつ削除しなければなりません
node* tmpnode = head;
node* del = tmpnode;
while(tmpnode != NULL)
{
del = tmpnode;
tmpnode = tmpnode->next;
delete del;
}
これだけ見ると使いづらいだけに見えますが・・・
配列などの中間要素に挿入、削除などをする場合
最後方に追加してソートするという手間がかかります
（さらにいうと自由に配列の長さは変えることが基本的にはできません）
これに比べてリストは
ノードのポインタをつなぎなおすだけで済みます
配列と比べて新しいノードを追加するだけでいいので
固定長ではないところも強みです
つまり、データを頻繁に入れ替える場合に重宝する
データ構造なのです
以下に双方向リストをテンプレートクラス化したものを載せておきます
わかる人だけ専用ですが・・・（ぉぃ
//list.h
#pragma once
#include <iostream>
using namespace std;
template <class T>
class list
{
private:
int length;
list *head,*tail,*prev,*next;
T data;
public:
list(void);
virtual ~list(void);
void addlisthead(T setdata);
void addlist(int addnum,T setdata);
void addlisttail(T setdata);
void dellist(int delnum);
void dellisthead();
void dellisttail();
T get(int getnum);
void set(int setnum,T setdata);
int getlength();
};
//コンストラクタ
template <class T>
list<T>::list(void):length(0),head(NULL),tail(NULL),prev(NULL),next(NULL)
{
}
//デストラクタ(全てのリストを解放)
template <class T>
list<T>::~list(void)
{
list* tmplist = head;
list* del = NULL;
while(tmplist != NULL)
{
del = tmplist;
tmplist = tmplist->next;
delete del;
}
}
// 先頭追加（指定番号）
template <class T>
void list<T>::addlisthead(T setdata)
{
if(head == NULL)
{
head = new list<T>;
tail = head;
head->data = setdata;
return;
}
// リスト長を増やす
length++;
list* tmplist = head;
// リスト追加
tmplist->prev = new list<T>;
tmplist->prev->next = tmplist;
tmplist->prev->prev = NULL;
tmplist->prev->data = setdata;
// ヘッドを移行
head = tmplist->prev;
}
// 指定番号追加（指定番号）
template <class T>
void list<T>::addlist(int addnum,T setdata)
{
// 最小以下
if(addnum < 0)
addnum = 0;
// 最大以上
if(addnum > length)
addnum = length;
if(head == NULL)
{
head = new list<T>;
tail = head;
head->data = setdata;
return;
}
// リスト長を増やす
length++;
list* tmplist = head;
for(int i = 0;i < addnum;++i)
tmplist = tmplist->next;
// 末尾だったら
if(tmplist->next == NULL)
{
tmplist->next = new list<T>;
tmplist->next->next = NULL;
tmplist->next->prev = tmplist;
tmplist->next->data = setdata;
// テイルを移行
tail = tmplist->next;
}
// 先頭だったら
else if(tmplist->prev == NULL)
{
// リスト追加
tmplist->prev = new list<T>;
tmplist->prev->next = tmplist;
tmplist->prev->prev = NULL;
tmplist->prev->data = setdata;
// ヘッドを移行
head = tmplist->prev;
}
// 中間だったら
else
{
//つなぎなおし
tmplist->prev->next = new list<T>;
tmplist->prev->next->prev = tmplist->prev;
tmplist->prev->next->next = tmplist;
tmplist->prev = tmplist->prev->next;
tmplist->prev->data = setdata;
}
}
// 末尾追加（指定番号）
template <class T>
void list<T>::addlisttail(T setdata)
{
if(head == NULL)
{
head = new list<T>;
tail = head;
head->data = setdata;
return;
}
// リスト長を増やす
length++;
list* tmplist = head;
// リストを辿って末端のノードに接続
while(tmplist->next != NULL)
{
tmplist = tmplist->next;
}
// リストの生成
tmplist->next = new list<T>;
tmplist->next->next = NULL;
tmplist->next->prev = tmplist;
tmplist->next->data = setdata;
// テイルを移行
tail = tmplist->next;
}
// 先頭削除
template <class T>
void list<T>::dellisthead()
{
//削除不能
if(length < 0)
return;
list* del = head;
head = head->next;
head->prev = NULL;
delete del;
length--;
}
// 指定番号削除
template <class T>
void list<T>::dellist(int delnum)
{
//削除不能
if(length < 0)
return;
// 最小以下
if(delnum < 0)
delnum = 0;
// 最大以上
if(delnum > length)
delnum = length;
list* tmplist = head;
list* del;
for(int i = 0;i < delnum;++i)
tmplist = tmplist->next;
del = tmplist;
// 末尾
if(tmplist->next == NULL)
{
tail = tail->prev;
tail->next = NULL;
}
// 先頭
else if(tmplist->prev == NULL)
{
head = head->next;
head->prev = NULL;
}
// 中間
else
{
tmplist->prev->next = tmplist->next;
tmplist->next->prev = tmplist->prev;
}
delete del;
length--;
}
// 末尾削除
template <class T>
void list<T>::dellisttail()
{
//削除不能
if(length < 0)
return;
list* del = tail;
tail = tail->prev;
tail->next = NULL;
delete del;
length--;
}
// 指定番号のリストデータを取り出す
template <class T>
T list<T>::get(int getnum)
{
// 最小以下
if(getnum < 0)
getnum = 0;
// 最大以上
if(getnum > length)
getnum = length;
list* tmplist = head;
for(int i = 0;i < getnum;++i)
tmplist = tmplist->next;
return tmplist->data;
}
// 指定番号のリストデータにデータを追加する
template <class T>
void list<T>::set(int setnum,T setdata)
{
// 最小以下
if(setnum < 0)
setnum = 0;
// 最大以上
if(setnum > length)
setnum = length;
list* tmplist = head;
for(int i = 0;i < setnum;++i)
tmplist = tmplist->next;
tmplist->data = setdata;
}
// リスト長を返す
template <class T>
int list<T>::getlength()
{
return length + 1;
}
