双方向リスト (循環リスト)
●双方向リストの構造
連結リストのセルは、データを格納する data と、直後のセルへの参照を格納する next から構成されています。双方向リストは名前が示すように、直後のセルだけでなく、直前のセルへの参照を持たせたデータ構造です。双方向リストは「重連結リスト (doubly linked list)」と呼ばれることもあります。
図 : 双方向リスト
連結リストは後ろ方向にしかセルをたどることができませんが、双方向リストでは前後どちらの方向へもセルをたどることができます。セルを削除する場合も、前後のセルがわかるので簡単に削除することができるのです。双方向リストはメモリ管理などによく使われるデータ構造です。
●両端キュー (deque)
それでは簡単な例題として deque (double ended queue) というデータ構造を Rust で実装してみましょう。deque は「両端キュー」のことで、「デック」とか「ディーキュー」と呼ばれることもあります。キューの場合、データの追加は最後尾に、データの取り出しは先頭に対してのみ行えます。これに対し両端キューは、先頭および最後尾のどちらでもデータの追加と取り出しが行えるデータ構造です。
両端キューは双方向リストを使うと簡単に実現できます。次の図を見てください。
図 : 両端キュー (1)
双方向リストを使う場合、ヘッダセルを用意してリストを環状に構成する方法が一般的です。ヘッダセルにはデータを格納しません。ヘッダセルの next が参照するセルが先頭で、prev が参照するセルが最後尾になります。ヘッダセルが先頭と最後尾のセルを参照しているので、両端でのデータ操作が簡単にできるのです。
データがない空リストの場合は、次の図に示すようにセルを参照する変数 next と prev の値はヘッダセル自身になります。
データがない場合はヘッダセル自身を格納 図 : 両端キュー (2)
このようにすると、空リストへデータを挿入する場合や、データを削除して空リストになる場合で、プログラムが簡単になるという利点があります。これは、実際にプログラムを作ってみるとわかります。
●プログラムの作成
それでは、プログラムを作りましょう。最初に作成するメソッドを表に示します。
| メソッド名 | 機能 |
|---|---|
| fn new(n: usize) -> Deque<T> | 指定した大きさの両端キューを作る (コンストラクタ) |
| fn push_front(&mut self, x: T) -> bool | 先頭にデータを追加する |
| fn push_back(&mut self, x: T) -> bool | 末尾にデータを追加する |
| fn pop_front(&mut self) -> Option<T> | 先頭からデータを取り出す |
| fn pop_back(&mut self) -> Option<T> | 末尾からデータを取り出す |
| fn front(&self) -> Option<&T> | 先頭データへの参照を返す |
| fn back(&self) -> Option<&T> | 末尾データへの参照を返す |
| fn len(&self) -> usize | 両端キューの要素数を返す |
| fn is_empty(&self) -> bool | 両端キューが空ならば true を返す |
| fn is_full(&self) -> bool | 両端キューが満杯ならば true を返す |
| fn clear(&mut self) | 両端キューを空にする |
●データ構造の定義
次はデータ構造を定義します。
リスト : 双方向リスト () による両端キューの実装
use std::rc::Rc;
use std::cell::UnsafeCell;
// 双方向リスト
struct Node<T> {
data: T,
prev: Link<T>,
next: Link<T>
}
type Link<T> = Option<Rc<UnsafeCell<Node<T>>>>;
// 両端キュー
struct Deque<T: Default> {
head: Link<T>,
size: usize
}
// メソッドの定義
impl<T: Default> Deque<T> {
fn new() -> Deque<T> {
// ヘッダセル (ダミー)
let header = Rc::new(UnsafeCell::new(Node {
data: Default::default(), prev: None, next: None
}));
unsafe {
(*header.get()).prev = Some(header.clone());
(*header.get()).next = Some(header.clone());
};
Deque { head: Some(header), size: 0 }
}
// メソッドの定義 (省略)
}
セルを表す構造体を Node<T> とし、両端キューを表す構造体を Deque<T> としました。今回はヘッダセルを使用するので、そこに格納するためのダミーデータを用意する必要があります。そこで、型パラメータ T の境界にトレイト Default を指定して、型 T のデフォルト値を使用することにします。
Deque のメソッド new() では、Node { ... } でセルを生成して変数 header に格納します。T のデフォルト値は Default::default() で取得することができます。次に、header の next と prev を header に書き換えて循環リストにします。これで、空の双方向リストになります。最後に、Deque のフィールド変数 size を 0 に、head を header に初期化します。
●データの追加
それでは、両端キューの先頭にデータを追加するメソッド push_front() から作りましょう。次の図を見てください。
H Q
<--> [ | |Q] <--> [H| | ] <-->
H の next に P を挿入
H P Q
<--> [ | |P] <--> [H| |Q] <--> [P| | ] <-->
【注意】[prev | data | next] はセルを表す。
図：データの追加 (1)
この場合はヘッダ H の next と Q の prev を挿入するセル P に書き換え、P の prev と next には H と Q をセットします。これをプログラムすると、次のようになります。
リスト：データの追加 (1)
fn push_front(&mut self, x: T) {
let new_node = Rc::new(UnsafeCell::new(Node {
data: x, prev: None, next: None
}));
let p = new_node.get();
self.head.as_mut().map(|header| unsafe {
let q = header.get();
(*q).next.take().map(|top| {
(*top.get()).prev = Some(new_node.clone());
(*q).next = Some(new_node);
(*p).next = Some(top);
(*p).prev = Some(header.clone());
});
});
self.size += 1;
}
データ x を格納した新しいセル new_node を生成し、その生ポインタを変数 p にセットします。self.head.as_mut().map() でヘッダセル (header) を求め、その生ポインタを変数 q にセットします。次に (*q).next.take().map() で先頭セル (top) を取り出します。そして、top の prev と header の next を new_node に書き換えます。そして、new_node の next を top に、prev を header に書き換えれば、データを追加することができます。
また、このままの処理で空リストにデータを挿入することもできます。次の図を見てください。
H(header) P [H| |H] [?| |?] H P [P| |P] <--> [H| |H] 図 : 空リストへデータを挿入
上図に示すように、ヘッダセルの prev と next は自分自身を格納しているので、h.next は H 自身となります。したがって、P の prev と next には H がセットされ、H の prev と next には P がセットされるのです。これで、空リストにデータを挿入することができます。
末尾にデータを追加するメソッド push_back() も同様にプログラムすることができます。次のリストを見てください。
リスト：データの追加 (2)
fn push_back(&mut self, x: T) {
let new_node = Rc::new(UnsafeCell::new(Node {
data: x, prev: None, next: None
}));
let p = new_node.get();
self.head.as_mut().map(|header| unsafe {
let q = header.get();
(*q).prev.take().map(|tail| {
(*tail.get()).next = Some(new_node.clone());
(*q).prev = Some(new_node);
(*p).prev = Some(tail);
(*p).next = Some(header.clone());
});
});
self.size += 1;
}
今度は新しいセル new_node をヘッダセル (header) の prev に、末尾セル (tail) の next に挿入します。あとは new_node の prev を tail に、next を header に書き換えれば、両端キューの末尾にデータを追加することができます。
●データの取得
次は、先頭のデータを取り出すメソッド pop_front() を作りましょう。次の図を見てください。
セルの削除はとても簡単です。H の next と P の prev を書き換えればいいのです。プログラムは次のようになります。
リスト：データの取得 (1)
fn pop_front(&mut self) -> Option<T> {
if self.size == 0 { return None; }
self.size -= 1;
self.head.as_mut().map(|header| unsafe {
let p = header.get();
(*p).next.take().map(|node| {
let q = node.get();
(*q).next.take().map(|node1| {
(*node1.get()).prev = Some(header.clone());
(*p).next = Some(node1)
});
match Rc::try_unwrap(node) {
Ok(node) => node.into_inner().data,
Err(_) => panic!("pop_front error")
}
})
}).unwrap()
}
self.size が 0 の場合は None を返します。そうでなければ、ヘッダセル (header) と先頭セル (node) を求め、node の next から 2 番目のセル (node1) を取り出します。そして、node1 の prev を header に、ヘッダの next を node1 に書き換えます。これで node を循環リストから外して、その参照カウンタを 1 にすることができます。あとは try_unwrap() で Rc からセルを取り出し、そこに格納されている data を返すだけです。
ところで、最後のデータを削除する場合もこのままの処理で大丈夫です。次の図を見てください。
H(header) Q H
[Q| |Q] <--> [H| |H] ===> [H| |H]
図 : 最後のデータを削除
セル Q の next と prev はヘッダセル H を格納しています。Q の次のセルを P とすると、それはヘッダセル H になります。したがって、P の prev を H に書き換える処理は、ヘッダの prev をヘッダ自身に、H の next を P に書き換える処理はヘッダの next をヘッダ自身に書き換える処理になります。これで双方向リストは空リストになります。
末尾のデータを削除するメソッド pop_back() も簡単にプログラムすることができます。次のリストを見てください。
リスト：データの取得 (2)
fn pop_back(&mut self) -> Option<T> {
if self.size == 0 { return None; }
self.size -= 1;
self.head.as_mut().map(|header| unsafe {
let p = header.get();
(*p).prev.take().map(|node| {
let q = node.get();
(*q).prev.take().map(|node1| {
(*node1.get()).next = Some(header.clone());
(*p).prev = Some(node1)
});
match Rc::try_unwrap(node) {
Ok(node) => node.into_inner().data,
Err(_) => panic!("pop_back error")
}
})
}).unwrap()
}
今度はヘッダセル (header) の prev のセル (node) を削除します。node から一つ手前のセル (node1) を求め、node1 の next を header に、header の prev を node1 に書き換えます。これで node を循環リストから外して、参照カウンタを 1 にすることができます。あとの処理は pop_front() と同じです。
残りのメソッドは簡単なので説明は省略します。詳細は プログラムリスト をお読みください。
●実行例
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
fn main() {
let mut deq = Deque::new();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
for i in 0 .. 4 {
deq.push_back(i);
deq.push_front(i + 10);
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
println!("{:?}", deq.back());
println!("{:?}", deq.front());
for _ in 0 .. 3 {
println!("{:?}", deq.pop_back());
println!("{:?}", deq.pop_front());
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
deq.clear();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
}
実行結果を示します。
0 true false 8 false false Some(3) Some(13) Some(3) Some(13) Some(2) Some(12) Some(1) Some(11) 2 false false 0 true false
正常に動作しているようです。興味のある方はいろいろ試してみてください。
●プログラムリスト
//
// dlist.rc : 双方向リスト (循環リスト)
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
use std::rc::Rc;
use std::cell::UnsafeCell;
// 双方向リスト
struct Node<T> {
data: T,
prev: Link<T>,
next: Link<T>
}
type Link<T> = Option<Rc<UnsafeCell<Node<T>>>>;
// 両端キュー
struct Deque<T: Default> {
head: Link<T>,
size: usize
}
// メソッド
impl<T: Default> Deque<T> {
fn new() -> Deque<T> {
// ヘッダーセル (ダミー)
let header = Rc::new(UnsafeCell::new(Node {
data: Default::default(), prev: None, next: None
}));
unsafe {
(*header.get()).prev = Some(header.clone());
(*header.get()).next = Some(header.clone());
};
Deque { head: Some(header), size: 0 }
}
// 末尾にデータを追加する
fn push_back(&mut self, x: T) {
let new_node = Rc::new(UnsafeCell::new(Node {
data: x, prev: None, next: None
}));
let p = new_node.get();
self.head.as_mut().map(|header| unsafe {
let q = header.get();
(*q).prev.take().map(|tail| {
(*tail.get()).next = Some(new_node.clone());
(*q).prev = Some(new_node);
(*p).prev = Some(tail);
(*p).next = Some(header.clone());
});
});
self.size += 1;
}
// 先頭データを取り出す
fn pop_front(&mut self) -> Option<T> {
if self.size == 0 { return None; }
self.size -= 1;
self.head.as_mut().map(|header| unsafe {
let p = header.get();
(*p).next.take().map(|node| {
let q = node.get();
(*q).next.take().map(|node1| {
(*node1.get()).prev = Some(header.clone());
(*p).next = Some(node1)
});
match Rc::try_unwrap(node) {
Ok(node) => node.into_inner().data,
Err(_) => panic!("pop_front error")
}
})
}).unwrap()
}
// 先頭にデータを追加する
fn push_front(&mut self, x: T) {
let new_node = Rc::new(UnsafeCell::new(Node {
data: x, prev: None, next: None
}));
let p = new_node.get();
self.head.as_mut().map(|header| unsafe {
let q = header.get();
(*q).next.take().map(|top| {
(*top.get()).prev = Some(new_node.clone());
(*q).next = Some(new_node);
(*p).next = Some(top);
(*p).prev = Some(header.clone());
});
});
self.size += 1;
}
// 末尾データを取り出す
fn pop_back(&mut self) -> Option<T> {
if self.size == 0 { return None; }
self.size -= 1;
self.head.as_mut().map(|header| unsafe {
let p = header.get();
(*p).prev.take().map(|node| {
let q = node.get();
(*q).prev.take().map(|node1| {
(*node1.get()).next = Some(header.clone());
(*p).prev = Some(node1)
});
match Rc::try_unwrap(node) {
Ok(node) => node.into_inner().data,
Err(_) => panic!("pop_back error")
}
})
}).unwrap()
}
// 先頭データの参照を返す
fn front(&self) -> Option<&T> {
if self.size == 0 {
None
} else {
self.head.as_ref().map(|header| unsafe {
(*header.get()).next.as_ref().map(|top| {
&((*top.get()).data)
})
}).unwrap()
}
}
// 末尾データの参照を返す
fn back(&self) -> Option<&T> {
if self.size == 0 {
None
} else {
self.head.as_ref().map(|header| unsafe {
(*header.get()).prev.as_ref().map(|tail| {
&((*tail.get()).data)
})
}).unwrap()
}
}
// 要素数を返す
fn len(&self) -> usize { self.size }
// キューは空か？
fn is_empty(&self) -> bool { self.size == 0 }
// キューは満杯か？ (常に false を返す)
fn is_full(&self) -> bool { false }
// キューを空にする
fn clear(&mut self) {
while !self.is_empty() { self.pop_front(); }
}
}
// Deque が drop されたときは双方向リストも drop する
impl<T: Default> Drop for Deque<T> {
fn drop(&mut self) {
self.clear();
self.head.take().map(|node| unsafe {
let p = node.get();
(*p).prev = None;
(*p).next = None;
});
}
}
// 簡単なテスト
fn main() {
let mut deq = Deque::new();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
for i in 0 .. 4 {
deq.push_back(i);
deq.push_front(i + 10);
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
println!("{:?}", deq.back());
println!("{:?}", deq.front());
for _ in 0 .. 3 {
println!("{:?}", deq.pop_back());
println!("{:?}", deq.pop_front());
}
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
deq.clear();
println!("{}", deq.len());
println!("{}", deq.is_empty());
println!("{}", deq.is_full());
}
改訂 2022 年 8 月 6 日