🕌
データ構造③ 連結リスト(Linked Lists)
連結リストとは
連結リストとは、各データをポインタでつなぐことによって、複数のデータを連結させて格納するデータ構造である。各データが自分のデータの後ろの要素のリンクを持っている連結リストを「単方向リスト」(Singly Linked List)、前後の要素へのリンクを持っている連結リストを「双方向リスト」(Doubly Linked List)という。
配列では、データが隣接したメモリに確保されているが、連結リストは各データがメモリ上で分散した状態で保存されている。
また、要素数の指定はないため、要素の追加や削除が自由に行うことができる。
実装
単方向リストの場合、以下のように実装できる。
// 要素
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedLists {
// 初期化
constructor(value) {
const newNode = new Node(value);
this.head = newNode;
this.tail = this.head;
this.length = 1;
}
// 末尾に要素追加
append(value) {
const newNode = new Node(value);
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
// 先頭に要素追加
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
// 特定の位置に要素追加
insert(index, value) {
if (index >= this.length) {
return this.append(value)
}
const leader = this.traverseToIndex(index - 1);
newNode.next = leader.next;
leader.next = newNode;
this.length++;
return this;
}
// 特定の位置の要素を取得
traverseToIndex(index) {
let counter = 0;
let currentNode = this.head;
while(counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
// 特定の位置の要素削除
remove(index) {
if (index >= this.length) {
return this;
}
const leader = this.traverseToIndex(index - 1);
leader.next = leader.next.next;
this.length--;
return this;
}
// すべての要素の値のみ表示
printList(value) {
const array = [];
let currentNode = this.head;
while(currentNode !== null){
array.push(currentNode.value)
currentNode = currentNode.next
}
return array;
}
}
双方向リストの場合は以下。
自身のデータの前のデータとのリンクが追加されるため、実装は少し複雑になる。
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor(value){
this.head = new Node(value);
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = new Node(value)
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
this.length++;
return this.printList();
}
prepend(value) {
const newNode = new Node(value)
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this.printList();
}
printList() {
const array = [];
let currentNode = this.head;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.next;
}
console.log(array);
return array;
}
insert (index, value) {
if (index >= this.length) {
this.append(value);
return this.printList();
}
if (index === 0) {
this.prepend(value);
return this.printList();
}
else {
const newNode = new Node(value);
const leader = this.traverseToIndex(index - 1);
const nextNode = leader.next;
newNode.next = nextNode;
newNode.prev = leader;
nextNode.prev = newNode;
leader.next = newNode;
}
return this.printList();
}
remove (index) {
const leader = this.traverseToIndex(index-1);
const unwantedNode = leader.next;
const follower = unwantedNode.next;
if (follower){
leader.next = follower;
follower.prev = leader;
}
else {
leader.next = follower;
}
this.length--;
return this.printList();
}
traverseToIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
それぞれの操作の計算量
それぞれの操作の計算量は以下。
挿入、削除に関して、配列でも連結リスとでもそれらの計算量はO(n)だが、連結リストにおいて挿入、削除に必要なのはポインタの更新のみであり、メモリの再割り当ても行う必要がないため、要素のシフトやメモリの再割り当ての可能性がある配列に比べて、挿入、削除を効率的に行うことが可能。
| 操作 | 計算量 |
|---|---|
| prepend | O(1) |
| append | O(1) |
| lookup | O(n) |
| insert | O(n) |
| delete | O(n) |
ただし、iterationの操作は、連結リストの場合、データがメモリ上で分散して確保されているため、隣接したメモリを確保している配列のデータでiterationするよりも少し遅くなる。
Singly vs Doubly
単方向リストと双方向リストはどのような違いがあるのか。
単方向リスト
- 利点
- 実装が双方向リストよりも少し簡単。
- 双方向リストと比較して、前のデータとのリンクがないため省メモリ。
- insertやdeleteの際に、this.prevの更新がないため、双方向リストよりも少し速い。
- 欠点
- headからtail側への探索しかできず、データを探索したいときなどは双方向リストに軍配があがる。
- 使う場面
- 使用するメモリを抑えたいときや動作を早くしたいとき。
- 探索がそれほど重要でないとき。
双方向リスト
- 利点
- headからtail、tailからheadの両方向からiterationができるため、探索が少し速い。
- 欠点
- 実装が単方向リストよりも少し難しくなる。
- 使用するメモリが多くなる。
- 使う場面
- メモリをあまり気にしなくていいとき。
- 探索を多く行うとき。
参考webサイト
このUdemyの講座を参考にしています。
Discussion