配列とリスト
これまで配列について説明してきました。
配列で再帰を組む方法を前回説明しました。
配列は
- 非順序配列は探索が遅い
- 順序配列は挿入が遅い
- いずれにしても削除は遅い
こうした問題の一部を解決する方法に「連結リスト」というデータ構造があります。
配列もよいけど、連結リストのほうがもっとよい、というシーンが多々あります。
配列が得意なのは、
- データ構造内の個々の項目に簡単にアクセスできること
ですよね。ではまずは連結リストを紹介します。
連結リスト
連結リストは、複数のデータを格納できます。
各データは、１つ前、あるいは後ろのデータへの参照情報（リンクやポインタ）を持っています。
リンクされたリストは、すべてのノートが次のノードを指すノードのチェーンとして視覚化することができます。
- リンクされたリストは、アイテムを含む一連クリンクです。
- 各リンクには、別のリンクへの接続が含まれています。
- 連結リスト(リンクリスト）は、配列についで２番目によく使われるデータ構造です。
- 上の「HEAD」がリンクリストの先頭で、その後ろに３つのノードがあることがわかります。
- ノードには、「Data Items」として値を格納することができます。
- 「Next」は、次のノードを参照するノード名が格納されます。
重要な点は以下のとおりです。
- 連結リストには「first」というリンク要素が含まれています。
- 各リンクノードには、「Data Items」と「next」というフィールドがあります。
- 各リンクノードは、「next」を使って次のリンクノードとリンクします。
- 最後のリンクノードの「next」は、nullまたはnoneで終端とします。
連結リストでできること
一般的な機能
- 表示-リスト全体を表示します。
- 挿入-リストの先頭に要素を追加します。
- 削除-リストの先頭にある要素を削除します。
キーを指定して検索や削除を行う機能
- 検索-指定されたキーを使用して要素を検索します。
- 削除-指定されたキーを使用して要素を削除します。
プログラムソース
この章で使っているプログラムソースは以下にあります。
04_6LinkedList.sh 連結リスト
挿入
まずは、連結リストに挿入してみます。
イメージが重要なので以下の図を見てください。
A (LeftNode) とC (RightNode)の間にNewNode を挿入したいと思います。
まずは、NewNodeをA（LeftNode）とC（RightNode）の間に配置します。
次に、NewNode のNextをC（RightNode）へ参照します。
これにより、NewNodeの次のノードがC（RightNode）となりました。
次に、A（LeftNode）のNextの参照を、C(RightNode）からNewNodeへ切り替えます。
これで、A(LeftNode）の次のノードがNewNodeとなりました。
これにより、ノードNewNodeがA（LeftNoe）とC(RightNode）２つの中間に配置されます。
新しいリストは以下の図のようになります。
NewNodeをリストの先頭に挿入したい場合は、上記同様の手順を Headと A（LeftNode）との間で実行すればよいわけです。
NewNodeをリストの最後に挿入したい場合は、リストの最後のノードC(RightNode）が新しいノードNewNodeを参照し、新しいノード（NewNode）のNextは nullまたはnone を指定します。
これにより、新しいNewNodeがリストの終端となります。
削除
削除は検索をすることから始まります。
削除したいノードを検索できたとします。
ここでは削除したいノードを TargetNode として真ん中のノードを削除対象としました。
挿入のときと同じように、TargetNode の左（前の）ノードの next は、TargetNodeの次（右）のノードを参照します。
これにより、TargetNode を参照していたリンクが削除されます。
これによりメモリに割り当てられていたTargetNodeが開放され、TargetNodeを完全に消去することができます。
- ヒント
- 削除された
TargetNodeのNextの参照をわざわざ消去する必要すらありません。 A（LeftNode）のNextがC（LeftNode）を参照していれば、TargetNode`は孤立し、リンクをたどることができなくなります。
連結リストと配列の違い
連結リストと配列の最も大きな違い
配列
各項目が特定の場所にあり、プログラマは配列の要素を使ってその場所に直接アクセスして探索し、挿入や削除を行います。
連結リスト
鎖のように連なった項目の並びをたどり歩く（走査する）子によって特定の項目を見つけます。
Eはどこにいる？と、Aにたずねます。AはBにたずね、BはCにたずねます。連結リストでは、Eに直接聞けないのでこの鎖をたどっていくのです。この処理を再帰で実装するとプログラムをよりシンプルに書くことができます。
連結リストの効率
連結リストの先頭への「挿入」や「削除」は非常に高速です。
それは、つねに１つまたは２つの参照を変えるだけだからです。
所要時間はO(1)です。
特定の項目を見つける操作（探索、削除、途中挿入などのため）は、平均してリストの項目の半数を探索しなければなりません。
これは、O(N)の比較を必要とします。
配列でも、これらの操作はO(N)でしたが、連結リストでは、挿入後や削除後の項目移動を必要としないため、その分はるかに高速です。
メモリ上の移動に要する時間が、比較に要する時間よりも大きいときは、連結リストが配列に比べてかなり高速と言えます。
連結リストが配列に比べて有利なのは、必要なだけのメモリしか使わない、また必要に応じて伸縮できることです。
配列のサイズは固定ですが、それは実際のデータ量に対してメモリの無駄遣い、またはメモリ不足になりがちです。
拡張性のある配列は、この問題をある程度解決してくれますが、拡張の幅が固定サイズの場合、メモリの使い方は連結リストほど効率的とは言えません。
配列と連結リストのデータアクセスの違い
データアクセスの場合、配列のほうが優れています。
配列は、添え字で要素を指定できるのでワンステップで要素を指定することができます。
連結リストは、先頭からリストをたどっていくことでしか要素を探せません。最大でNステップかかります。
配列と連結リストのデータの追加と削除の違い
データの追加、削除はリストが優れています。
配列は、データを追加、または削除するため、後ろにあるデータをずらす必要があります。そのため、ずらすデータの数だけ余計に処理時間がかかります。
リストでは、となりのノードを指し示す参照(Next)を書き換えるだけでデータの追加、削除を行うことができます。そのため、後ろのデータに関係なく数ステップで処理ができます。
※削除項目を参照
配列と連結リストのメモリ領域の違い
格納領域は、リストの方が優れています。
配列の場合、最初に int data[100]; のように格納領域を指定するため、使わない無駄な領域が発生してしまいます。
一方リストは参照（Next)だけで前後関係を表しており、使用領域は動的に変更することができるため、無駄がありません。
まとめ
- 頻繁にデータにアクセスするようであれば「配列」
- 頻繁にデータを書き換える場合であれば「連結リスト」
- メモリ領域を気にするなら「連結リスト」
| 操作内容 | 配列 | リスト |
|---|---|---|
| データアクセス | O(1) | O(N) |
| データ挿入／削除 | O(N) | O(1) |
配列と連結リストのハイブリッド
配列と連結リストのハイブリッドが使われます。
具体的な事例として、名前の１文字ないし、２文字目のA〜Zまでは配列で管理し、高速アクセスを活かします。
そこから後の名前の部分は連結リストを使って追加・削除を柔軟に行えるようにします。
プログラムソース
今回のプログラムソースは、今後の実用性も考えて、以下の機能にに加えて、
一般的な機能
- 表示-リスト全体を表示します。
- 挿入-リストの先頭に要素を追加します。
- 削除-リストの先頭にある要素を削除します。
以下の機能も追加しています。
キーを指定して検索や削除を行う機能
- 検索-指定されたキーを使用して要素を検索します。
- 削除-指定されたキーを使用して要素を削除します。
ソースはやや長くなりましたが、じっくりと動かしてみてください。
#!/bin/bash
########################################
# 連結リスト Linked List
# Bash シェルスクリプト版
########################################
##
# final()
# 実行後に行うファイナル処理
# 実行に必要なノードファイルを削除します。
function final(){
rm -fr $dirName;
}
##
# makeNodeFile()
# ノードファイルを作成
#
dirName="demo";
list1="list1";
node1="node1";
node2="node2";
node3="node3";
#
function makeNodeFile(){
rm -fr "$dirName";
mkdir -p $dirName;
cd demo;
:>$list1;
echo "node1" | tee "$list1";
echo "3" | tee -a "$list1";
:>$node1;
echo "node2" | tee "$node1";
echo "foo" | tee -a "$node1";
:>$node2;
echo "node3" | tee "$node2";
echo "bar" | tee -a "$node2";
:>$node3;
echo "none" | tee "$node3";
echo "!" | tee -a "$node3";
cd ../
}
##
##
# addAtIdx()
# 指定したインデックスに要素を追加
function addAtIdx {
local first=$1;
local N=$2;
local dataItems=$3;
if [ "$N" -eq "0" ]; then
add $first $dataItems;
else
let prevIdx=$N-1;
let size=$(tail -n1 $first)+1;
prev=$(getNode $first $prevIdx);
if [ "$N" -eq $(tail -n1 $first) ]; then
cur="none";
else
cur=$(getNode $first $N);
fi
printf "%s\n%s" $cur $dataItems > node$size;
printf "%s\n%s" node$size $(tail -n1 $prev) > $prev;
printf "%s\n%s" $(head -n1 $first) $size > $first;
fi
}
##
# remove()
# リストの先頭から要素を削除します。
# $1 - 追加するリストの先頭
function remove {
local first=$1;
local oldHead=$(head -n1 $first);
local oldVal=$(tail -n1 $oldHead);
let size=$(tail -n1 $first)-1;
local newHead=$(head -n1 $oldHead);
printf "%s\n%s" $newHead $size > $first;
rm $oldHead;
echo $oldVal;
}
##
# removeAtIdx()
# インデックスの要素を削除します
function removeAtIdx {
local first=$1;
local N=$2;
local prev;
local cure;
local Next;
local oldVal;
if [ "$N" -eq "0" ]; then
remove $first;
else
let prevIdx=$N-1
let size=$(tail -n1 $first)-1
prev=$(getNode $first $prevIdx)
cur=$(getNode $first $N)
Next=$(head -n1 $cur)
oldVal=$(tail -n1 $cur)
printf "%s\n%s" $Next $(tail -n1 $prev) > $prev
printf "%s\n%s" $(head -n1 $first) $size > $first
rm $cur;
echo $oldVal;
fi
}
##
# getNode()
# N番目の要素を含むノードの名前を返します。
function getNode {
local first=$1;
local N=$2;
rest=$(head -n1 $first)
let restlen=$N-1;
if [ "$N" -eq "0" ]; then
echo $rest;
else
getNode $rest $restlen;
fi
}
##
# get()
# リンクリストのN番目の要素を取得します。
function get {
local currentNode=$1;
local N=$2;
local current=$(tail -n1 $currentNode);
local rest=$(head -n1 $currentNode);
let restlen=$N-1;
if [ "$N" -eq "0" ]; then
echo "$current";
else
get $rest $restlen;
fi
}
##
# add()
# リストの先頭に要素を追加します
function add {
# リストの先頭を参照
local first=$1;
local N=$2;
local oldHead=$(head -n1 $first);
let size=$(tail -n1 $first)+1;
printf "%s\n%s" $oldHead $N > node$size;
printf "%s\n%s" node$size $size > $first;
}
##
# printList()
# 連結されたリスト全体を出力
function printList {
local current=$1;
local dataItems=$(tail -n1 $current);
local Next=$(head -n1 $current);
echo "データアイテム:" $dataItems "次の参照:" $Next;
if [ "$Next" != "none" ]; then
printList $Next;
fi
}
##
# execLinkedList()
# 連結リストの実行
function execLinkedList(){
# demoディレクトリへ移動
cd demo;
#
printList $(head -n1 $list1);
printf "\nリストの先頭に hello を追加\n"
add "$list1" "hello";
printList $(head -n1 $list1);
#
printf "\nリストの先頭に world を追加\n"
add "$list1" "world"
printList $(head -n1 $list1)
#
printf "\n０から数えて１番目の要素を取得\n"
get $(head -n1 $list1) 1
#
printf "\n０から数えて１番目のノード名を取得\n"
getNode "$list1" 1
#
printf "\n０から数えて２番目に要素 327 を挿入\n"
addAtIdx "$list1" 2 327
printList $(head -n1 $list1)
#
printf "\nリストの先頭に要素 94 を挿入\n"
addAtIdx "$list1" 0 94
printList $(head -n1 $list1)
#
printf "\n０から数えて７番目に要素 1138 を挿入\n"
addAtIdx "$list1" 7 1138
printList $(head -n1 $list1)
#
printf "\nリストの先頭の要素 %s を削除\n" $(remove "$list1")
printList $(head -n1 $list1)
#
printf "\nリストの１番目の要素 %s を削除\n" $(removeAtIdx "$list1" 1)
printList $(head -n1 $list1)
#
printf "\nリスト５番目の要素 %s を削除\n" $(removeAtIdx "$list1" 5)
printList $(head -n1 $list1)
#
printf "\nリストの先頭の要素 %s を削除\n" $(removeAtIdx "list1" 0)
printList $(head -n1 $list1)
#
printf "\n%s を削除し初期状態に戻りました\n" $(remove "$list1")
printList $(head -n1 $list1)
#
cd ../;
}
##
# メイン
makeNodeFile; # makeDir makeFileなどのノードファイルを作成します。
execLinkedList
final; # 作成したディレクトリを削除（当然中にあるノードファイルも消えます）
exit;
実行結果
実行結果は以下のとおりです。
bash-5.1$ bash 04_6LinkedList.sh
node1
3
node2
foo
node3
bar
none
!
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
リストの先頭に hello を追加
データアイテム: hello 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
リストの先頭に world を追加
データアイテム: world 次の参照: node4
データアイテム: hello 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
０から数えて１番目の要素を取得
hello
０から数えて１番目のノード名を取得
node4
０から数えて２番目に要素 327 を挿入
データアイテム: world 次の参照: node4
データアイテム: hello 次の参照: node6
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
リストの先頭に要素 94 を挿入
データアイテム: 94 次の参照: node5
データアイテム: world 次の参照: node4
データアイテム: hello 次の参照: node6
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
０から数えて７番目に要素 1138 を挿入
データアイテム: 94 次の参照: node5
データアイテム: world 次の参照: node4
データアイテム: hello 次の参照: node6
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: node8
データアイテム: 1138 次の参照: none
リストの先頭の要素 94 を削除
データアイテム: world 次の参照: node4
データアイテム: hello 次の参照: node6
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: node8
データアイテム: 1138 次の参照: none
リストの１番目の要素 hello を削除
データアイテム: world 次の参照: node6
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: node8
データアイテム: 1138 次の参照: none
リスト５番目の要素 1138 を削除
データアイテム: world 次の参照: node6
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
リストの先頭の要素 world を削除
データアイテム: 327 次の参照: node1
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
327 を削除し初期状態に戻りました
データアイテム: foo 次の参照: node2
データアイテム: bar 次の参照: node3
データアイテム: ! 次の参照: none
bash-5.1$
「ざっくり」シリーズのご紹介
【アルゴリズム リスト】ざっくりわかるシェルスクリプト１６
https://suzukiiichiro.github.io/posts/2022-10-18-01-list-suzuki/
【アルゴリズム 再帰】ざっくりわかるシェルスクリプト１５
https://suzukiiichiro.github.io/posts/2022-10-07-01-algorithm-recursion-suzuki/
【アルゴリズム キュー】ざっくりわかるシェルスクリプト１４
https://suzukiiichiro.github.io/posts/2022-10-06-01-algorithm-queue-suzuki/
【アルゴリズム スタック】ざっくりわかるシェルスクリプト１３
https://suzukiiichiro.github.io/posts/2022-10-06-01-algorithm-stack-suzuki/
【アルゴリズム 挿入ソート】ざっくりわかるシェルスクリプト１２
https://suzukiiichiro.github.io/posts/2022-10-05-01-algorithm-insertionsort-suzuki/
【アルゴリズム 選択ソート】ざっくりわかるシェルスクリプト１１
https://suzukiiichiro.github.io/posts/2022-10-05-01-algorithm-selectionsort-suzuki/
【アルゴリズム バブルソート】ざっくりわかるシェルスクリプト１０
https://suzukiiichiro.github.io/posts/2022-10-05-01-algorithm-bubblesort-suzuki/
【アルゴリズム ビッグオー】ざっくりわかるシェルスクリプト９
https://suzukiiichiro.github.io/posts/2022-10-04-01-algorithm-bigo-suzuki/
【アルゴリズム ２次元配列編】ざっくりわかるシェルスクリプト８
https://suzukiiichiro.github.io/posts/2022-10-03-01-algorithm-eval-array-suzuki/
【アルゴリズム 配列準備編】ざっくりわかるシェルスクリプト７
https://suzukiiichiro.github.io/posts/2022-10-03-01-algorithm-array-suzuki/
【アルゴリズム 配列編】ざっくりわかるシェルスクリプト６
https://suzukiiichiro.github.io/posts/2022-09-27-01-array-suzuki/
【grep/sed/awkも】ざっくりわかるシェルスクリプト５
https://suzukiiichiro.github.io/posts/2022-02-02-01-suzuki/
【grep特集】ざっくりわかるシェルスクリプト４
https://suzukiiichiro.github.io/posts/2022-01-24-01-suzuki/
【はじめから】ざっくりわかるシェルスクリプト３
https://suzukiiichiro.github.io/posts/2022-01-13-01-suzuki/
【はじめから】ざっくりわかるシェルスクリプト２
https://suzukiiichiro.github.io/posts/2022-01-12-01-suzuki/
【はじめから】ざっくりわかるシェルスクリプト１
https://suzukiiichiro.github.io/posts/2022-01-07-01-suzuki/
【TIPS】ざっくりわかるシェルスクリプト
https://suzukiiichiro.github.io/posts/2022-09-26-01-tips-suzuki/
