Skip to content

Instantly share code, notes, and snippets.

@Cartman0

Cartman0/リスト構造.ipynb

Last active December 20, 2020 01:46
Show Gist options
  • Save Cartman0/3ebb2e2669fa8da0daa0b92a6e1c577e to your computer and use it in GitHub Desktop.
Save Cartman0/3ebb2e2669fa8da0daa0b92a6e1c577e to your computer and use it in GitHub Desktop.
Download ZIP
DataStructure リスト構造
Display the source blob
Display the rendered blob
Raw
リスト構造.ipynb
{
"cells": [
{
"metadata": {
"toc": "true"
},
"cell_type": "markdown",
"source": "# Table of Contents\n <p><div class=\"lev1 toc-item\"><a href=\"#リスト構造\" data-toc-modified-id=\"リスト構造-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>リスト構造</a></div><div class=\"lev2 toc-item\"><a href=\"#単方向リスト\" data-toc-modified-id=\"単方向リスト-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>単方向リスト</a></div><div class=\"lev3 toc-item\"><a href=\"#実装メモ\" data-toc-modified-id=\"実装メモ-111\"><span class=\"toc-item-num\">1.1.1&nbsp;&nbsp;</span>実装メモ</a></div><div class=\"lev4 toc-item\"><a href=\"#データの追加（add操作）\" data-toc-modified-id=\"データの追加（add操作）-1111\"><span class=\"toc-item-num\">1.1.1.1&nbsp;&nbsp;</span>データの追加（add操作）</a></div><div class=\"lev4 toc-item\"><a href=\"#データの挿入（insert操作）\" data-toc-modified-id=\"データの挿入（insert操作）-1112\"><span class=\"toc-item-num\">1.1.1.2&nbsp;&nbsp;</span>データの挿入（insert操作）</a></div><div class=\"lev4 toc-item\"><a href=\"#データの削除の場合（delete操作）\" data-toc-modified-id=\"データの削除の場合（delete操作）-1113\"><span class=\"toc-item-num\">1.1.1.3&nbsp;&nbsp;</span>データの削除の場合（delete操作）</a></div><div class=\"lev4 toc-item\"><a href=\"#単方向リストのcode\" data-toc-modified-id=\"単方向リストのcode-1114\"><span class=\"toc-item-num\">1.1.1.4&nbsp;&nbsp;</span>単方向リストのcode</a></div><div class=\"lev2 toc-item\"><a href=\"#双方向リスト(Doubly-Linked-List)\" data-toc-modified-id=\"双方向リスト(Doubly-Linked-List)-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>双方向リスト(Doubly Linked List)</a></div><div class=\"lev3 toc-item\"><a href=\"#実装メモ\" data-toc-modified-id=\"実装メモ-121\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>実装メモ</a></div><div class=\"lev4 toc-item\"><a href=\"#データを末尾へ追加（addLast）\" data-toc-modified-id=\"データを末尾へ追加（addLast）-1211\"><span class=\"toc-item-num\">1.2.1.1&nbsp;&nbsp;</span>データを末尾へ追加（addLast）</a></div><div class=\"lev4 toc-item\"><a href=\"#データを先頭へ追加（addFirst）\" data-toc-modified-id=\"データを先頭へ追加（addFirst）-1212\"><span class=\"toc-item-num\">1.2.1.2&nbsp;&nbsp;</span>データを先頭へ追加（addFirst）</a></div><div class=\"lev4 toc-item\"><a href=\"#データの挿入-insert()\" data-toc-modified-id=\"データの挿入-insert()-1213\"><span class=\"toc-item-num\">1.2.1.3&nbsp;&nbsp;</span>データの挿入 insert()</a></div><div class=\"lev4 toc-item\"><a href=\"#先頭データの削除-deleteFirst\" data-toc-modified-id=\"先頭データの削除-deleteFirst-1214\"><span class=\"toc-item-num\">1.2.1.4&nbsp;&nbsp;</span>先頭データの削除 deleteFirst</a></div><div class=\"lev4 toc-item\"><a href=\"#末尾データの削除(deleteLast)\" data-toc-modified-id=\"末尾データの削除(deleteLast)-1215\"><span class=\"toc-item-num\">1.2.1.5&nbsp;&nbsp;</span>末尾データの削除(deleteLast)</a></div><div class=\"lev4 toc-item\"><a href=\"#データの削除-delete\" data-toc-modified-id=\"データの削除-delete-1216\"><span class=\"toc-item-num\">1.2.1.6&nbsp;&nbsp;</span>データの削除 delete</a></div><div class=\"lev4 toc-item\"><a href=\"#双方向リストのcode\" data-toc-modified-id=\"双方向リストのcode-1217\"><span class=\"toc-item-num\">1.2.1.7&nbsp;&nbsp;</span>双方向リストのcode</a></div><div class=\"lev2 toc-item\"><a href=\"#循環リスト\" data-toc-modified-id=\"循環リスト-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>循環リスト</a></div><div class=\"lev3 toc-item\"><a href=\"#実装メモ\" data-toc-modified-id=\"実装メモ-131\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>実装メモ</a></div><div class=\"lev4 toc-item\"><a href=\"#データを末尾へ追加（addLast）\" data-toc-modified-id=\"データを末尾へ追加（addLast）-1311\"><span class=\"toc-item-num\">1.3.1.1&nbsp;&nbsp;</span>データを末尾へ追加（addLast）</a></div><div class=\"lev4 toc-item\"><a href=\"#データを先頭へ追加（addFirst）\" data-toc-modified-id=\"データを先頭へ追加（addFirst）-1312\"><span class=\"toc-item-num\">1.3.1.2&nbsp;&nbsp;</span>データを先頭へ追加（addFirst）</a></div><div class=\"lev4 toc-item\"><a href=\"#データの先頭を削除-deleteFirst()\" data-toc-modified-id=\"データの先頭を削除-deleteFirst()-1313\"><span class=\"toc-item-num\">1.3.1.3&nbsp;&nbsp;</span>データの先頭を削除 deleteFirst()</a></div><div class=\"lev4 toc-item\"><a href=\"#データの末尾を削除(deleteLast())\" data-toc-modified-id=\"データの末尾を削除(deleteLast())-1314\"><span class=\"toc-item-num\">1.3.1.4&nbsp;&nbsp;</span>データの末尾を削除(deleteLast())</a></div><div class=\"lev4 toc-item\"><a href=\"#循環リストのcode\" data-toc-modified-id=\"循環リストのcode-1315\"><span class=\"toc-item-num\">1.3.1.5&nbsp;&nbsp;</span>循環リストのcode</a></div>"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "# リスト構造"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "- [Gist](https://gist.github.com/Cartman0/3ebb2e2669fa8da0daa0b92a6e1c577e)\n- [nbviewer](http://nbviewer.jupyter.org/gist/Cartman0/3ebb2e2669fa8da0daa0b92a6e1c577e)"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 単方向リスト"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ポインタには次のセルの場所が位置付けられていて，\n一方向にだけたどるリスト構造．\n\n特徴：\nデータの挿入，追加，削除がポインタ変更によって容易．\n\n最後のセルはデータのみ持ち，ポインタはどこも指さない．\n\n\n```\nデータアドレス 次のポインタ\n30 (先頭セル) 50\n ↓\n50 70\n ↓\n70 110\n ↓\n110 90\n ↓\n90 NULL\n```\n\nFig.単方向リストのイメージ図"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 実装メモ"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの追加（add操作）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "add操作：\nここでは，最後尾にデータを追加する．\n\n線形リストの最後のセルを求めて，最後のセルの次のポインタに新しいセルを追加する．\n\nデータが増えるたびに，最後尾まで求める必要があるので，\n処理量が増えていく．\n\n\n- リストが空の場合：先頭ポインタを新しいセルへ更新する．\n\n```\nHead -> newCell\n```\n\n- それ以外\n\n最後尾のセルを求めて，最後尾のセルの次のポインタを新しいセルにする．\n\n```\nHead -> Cell(1) -> Cell(2) -- -> Cell(n) -> newCell\n```\n\n参考\n- 平成26年 応用情報処理技術者 p.79"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの挿入（insert操作）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "insert操作：\n\n任意のindexを指定して，そこに新しいセルを挿入する．\n\n- 先頭へ挿入する場合\n\n「新しいセルの次ポインタ」に元々の先頭ポインタのセルを追加し，\n「先頭ポインタ」を新しいセルへ更新する．\n\n```\nold Head -> Cell(1) -> Cell(2) -- -> Cell(n)\nnew Head -> newCell -> Cell(1) -> Cell(2) -- -> Cell(n)\n```\n\n- indexへ挿入する場合： i-1番目のセルとi番目のセルを求めて，\n - 「i-1番目のセルの次ポインタ」に新しいセルを指定．\n - 「新しいセルの次ポインタ」にi番目のセルを指定\n\n```\nold Head -> Cell(1) --> Cell(i-1) -> Cell(i) -- -> Cell(n)\nnew Head -> Cell(1) --> Cell(i-1) -> newCell -> Cell(i) -- -> Cell(n)\n```\n\n参考\n- 平成26年 応用情報処理技術者 p.79"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの削除の場合（delete操作）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "- 先頭を削除：Headを「先頭セルの次ポインタ」にする．先頭セルを削除する．\n\n```\nold Head -> Cell(1) -> Cell(2) -> -- -> Cell(n)\nnew Head -> Cell(2) -> -- -> Cell(n)\ndel Cell(1)\n```\n\n- i番目を削除：\n「i-1番目のセルの次ポインタ」をi+1番目のセルにする．\ni番目のセルを削除する．\n\n```\nold Head -> Cell(1) -> Cell(2) -> --> Cell(i-1) -> Cell(i) -> Cell(i+1) -- -> Cell(n)\nnew Head -> Cell(1) -> Cell(2) -> --> Cell(i-1) -> Cell(i+1) -- -> Cell(n)\ndel Cell(i)\n```\n"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### 単方向リストのcode"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:10:58.740744",
"end_time": "2017-02-18T19:10:58.924871"
},
"trusted": true,
"collapsed": true
},
"cell_type": "code",
"source": "class Cell:\n \"\"\"\n cell of one-way list\n \"\"\" \n def __init__(self, data): # コンストラクタ\n self.data = data\n self.next_pointer = None\n \nclass OnewayList:\n '''\n '''\n def __init__(self): # コンストラクタ\n self.head = None\n \n def last(self):\n cell = self.head\n # 空の時\n if not cell:\n return None\n \n # 空でないとき\n while not cell.next_pointer == None:\n # 次のポインタが空になるまで\n cell = cell.next_pointer\n return cell\n \n def get_index_cell(self, index):\n '''\n if index=0, return head \n '''\n cell = self.head\n for i in range(index):\n cell = cell.next_pointer\n return cell\n \n def add(self, data):\n added_cell = Cell(data)\n last_cell = self.last()\n \n if not last_cell:\n self.head = added_cell\n else:\n last_cell.next_pointer = added_cell\n \n def insert(self, index, data):\n '''\n '''\n added_cell = Cell(data)\n \n # 先頭へ追加する場合\n if index == 0:\n added_cell.next_pointer = self.head\n self.head = added_cell\n return \n \n # indexへ追加する場合\n if index > 0:\n pre_cell = self.get_index_cell(index-1)\n next_cell = pre_cell.next_pointer\n \n pre_cell.next_pointer = added_cell\n added_cell.next_pointer = next_cell\n \n def del_head(self):\n head_cell = self.head\n self.head = head_cell.next_pointer\n del head_cell\n \n def delete(self, index):\n '''\n 削除対象がnullでない前提\n '''\n if index == 0:\n self.del_head()\n return \n \n if index > 0:\n pre_cell = self.get_index_cell(index-1)\n del_target_cell = pre_cell.next_pointer\n next_cell = del_target_cell.next_pointer\n pre_cell.next_pointer = next_cell\n \n del del_target_cell\n \n def to_list(self):\n cell = self.head\n arr = []\n # 空でないとき\n while not cell == None:\n arr.append(cell.data)\n # 次のポインタが空になるまで\n cell = cell.next_pointer\n return arr\n \n def print(self):\n cell = self.head\n # 空でないとき\n while not cell == None:\n print(cell.data)\n cell = cell.next_pointer\n",
"execution_count": 7,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:13:08.811885",
"end_time": "2017-02-18T19:13:08.820891"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l = OnewayList()\n\none_l.add(1)\none_l.add(2)\none_l.add(3)\none_l.print()",
"execution_count": 12,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "1\n2\n3\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:13:09.105992",
"end_time": "2017-02-18T19:13:09.114999"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l.insert(0, 4)\none_l.insert(2, 5)\none_l.insert(5, 6)\n\none_l.print()",
"execution_count": 13,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "4\n1\n5\n2\n3\n6\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:35:06.760469",
"end_time": "2017-02-18T19:35:06.774480"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l.del_head()\n\none_l.print()",
"execution_count": 14,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "1\n5\n2\n3\n6\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:35:51.177354",
"end_time": "2017-02-18T19:35:51.184360"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l.delete(0)\n\none_l.print()",
"execution_count": 15,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n2\n3\n6\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:36:34.862438",
"end_time": "2017-02-18T19:36:34.868442"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l.delete(1)\n\none_l.print()",
"execution_count": 16,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n3\n6\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:36:58.055349",
"end_time": "2017-02-18T19:36:58.060353"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l.delete(2)\none_l.print()",
"execution_count": 17,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n3\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T19:37:15.175369",
"end_time": "2017-02-18T19:37:15.258432"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "one_l.to_list()",
"execution_count": 18,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[5, 3]"
},
"metadata": {},
"execution_count": 18
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "参考：\n\nhttp://www.ced.is.utsunomiya-u.ac.jp/lecture/2011/prog/p2/kadai2/3_list_1.php"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 双方向リスト(Doubly Linked List)"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "平成22年基本情報技術者 p.133\n\n前のセルへのポインタと次のセルへのポインタといった2つのポインタを持たせ，前後に自由にリストを辿れる．\n\n最後のセルは前のポインタのみ持っている．\n\n\n```\nデータアドレス ポインタ\n30 (先頭セル) pre:Null next:50\n ↑ ↓\n50 pre:30 next:70\n ↑ ↓\n70 pre:50 next:110\n ↑ ↓\n110 pre:70 next:90\n ↓ ↓\n90 pre:110 next:NULL\n```\n\nFig. 双方向リストのイメージ図"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 実装メモ"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データを末尾へ追加（addLast）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "addLast\n\n- 空の場合：\nHeadとTailは，新しいセルを指すようにする．\n\n```\nHead -> newCell <- Tail\n```\n\n- 空でない場合：\n(1)「元のTailのセルの次ポインタ」を新しいセルにする．\n(2) Tailを新しいセルへ更新する．\n\n```\nold: Head -> Cell1 <- Tail\nnew: Head -> Cell1 -> (1)newCell <- (2)Tail\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データを先頭へ追加（addFirst）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "addFirst:先頭へ追加\n\n- 空の場合：`addLast`と同じ．\n\n```\nHead -> newCell <- Tail\n```\n\n- 空でない場合：\n\n(1)「元のHeadのセルの前ポインタ」を新しいセルにする．\n(2) Headを新しいセルへ更新する．\n\n```\nold: Head -> Cell1 <- Tail\n\n -> \nnew: Head(2) -> newCell Cell1 -> Tail\n (1) <-\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの挿入 insert()"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "index目に挿入\n\n- 先頭に挿入：addFirst\n\n- 末尾に挿入：addLast\n\n- index目に挿入：\n \n(1): index-1番目のセルと新しいセルを連結．\n(2): 新しいセルとindex番目のセルを連結．\n\n```\n --> -> \nold: Head -> Cell1 Cell(i-1) Cell(i) <- Tail\n <-- <-\n\n --> -> ->\nold: Head -> Cell1 Cell(i-1) (1) newCell (2) Cell(i) <- Tail\n <-- <- <-\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### 先頭データの削除 deleteFirst"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "deleteFirst:先頭データの削除\n\n(1)先頭セルから「2番目のセルの前ポインタ」をNULLへ\n(2)Headは2番目のセルを指すようにする．\n(3)先頭セルの削除\n\n```\n -> \nold: Head -> Cell1 Cell2 <- Tail\n <- \n \nnew: Head (2) -> Cell2 <- Tail\n (1)NULL <- \n(3) del Cell1\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### 末尾データの削除(deleteLast)"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "(1)末尾セルから「2番目のセルの次ポインタ」をNULLへ\n(2)Tailは2番目のセルを指すようにする．\n(3)末尾セルの削除\n\n```\n --> -> \nold: Head -> Cell1 Cell(n-1) Cell(n) <- Tail\n <-- <-\n --> \nnew: Head -> Cell1 Cell(n-1) <- (2) Tail\n <-- -> (1)NULL \n(3) del Cell(n)\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの削除 delete"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "データの削除 delete：任意のindexのデータを削除\n\n- 先頭の場合：deleteFirst\n- 末尾の場合：deleteLast\n- それ以外：\n\n(1)「i-1番目のセル」と「i+1番目のセル」を連結．\n(2) i番目のセルを削除する．\n\n```\n --> -> ->\nold Head -> Cell(1) Cell(i-1) Cell(i) Cell(i+1) -- -> Cell(n) <- Tail\n <-- <- <-\n\n --> ->\nnew Head -> Cell(1) Cell(i-1) (1) Cell(i+1) -- -> Cell(n)\n <-- <-\n(2)del Cell(i)\n```\n"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### 双方向リストのcode"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T21:56:37.041575",
"end_time": "2017-02-18T21:56:37.461297"
},
"trusted": true,
"collapsed": true
},
"cell_type": "code",
"source": "class DoubleCell:\n \"\"\"\n cell of doubly-lnked list\n \"\"\" \n def __init__(self, data): # コンストラクタ\n self.data = data\n self.pre_pointer = None\n self.next_pointer = None\n \nclass DoublyLinkedList:\n '''\n '''\n def __init__(self): # コンストラクタ\n self.head = None\n self.tail = None\n \n def get_index_cell(self, index):\n '''\n index=0:return head \n '''\n cell = self.head\n for i in range(index):\n cell = cell.next_pointer\n return cell\n \n def _update_doubly_linked_2cells(self, pre_cell, next_cell):\n pre_cell.next_pointer = next_cell\n next_cell.pre_pointer = pre_cell\n \n def _add_init(self, cell):\n self.tail = cell # update list.tail\n self.head = cell # update list.head\n \n def addLast(self, data):\n added_cell = DoubleCell(data)\n\n # 空の場合\n if (not self.head) and (not self.tail):\n self._add_init(added_cell)\n return\n \n # not empty\n self._update_doubly_linked_2cells(self.tail, added_cell)\n self.tail = added_cell # update list.tail \n \n def addFirst(self, data):\n added_cell = DoubleCell(data)\n \n # 空の場合\n if (not self.head) and (not self.tail):\n self._add_init(added_cell)\n return\n \n # not empty\n self._update_doubly_linked_2cells(added_cell, self.head)\n self.head = added_cell # update list.head \n \n def insert(self, index, data):\n '''\n \n '''\n added_cell = DoubleCell(data)\n \n # 先頭へ追加する場合\n if index == 0:\n self.addFirst(data)\n return \n \n # index目に挿入 \n if index > 0:\n pre_cell = self.get_index_cell(index-1)\n \n # 最後に追加する場合\n if pre_cell == self.tail:\n self.addLast(data)\n return\n \n # index目に挿入 \n next_cell = pre_cell.next_pointer\n self._update_doubly_linked_2cells(pre_cell, added_cell)\n self._update_doubly_linked_2cells(added_cell, next_cell)\n \n \n def deleteFirst(self):\n head_cell = self.head\n second_cell = head_cell.next_pointer\n \n if not second_cell == None:\n second_cell.pre_pointer = None\n \n self.head = second_cell\n del head_cell\n \n \n def deleteLast(self):\n last_cell = self.tail\n second_cell = last_cell.pre_pointer\n \n if not second_cell == None:\n second_cell.next_pointer = None\n \n self.tail = second_cell\n del last_cell\n \n def delete(self, index):\n '''\n 削除対象がnullでない前提\n '''\n # 先頭の削除\n if index == 0:\n self.deleteFirst()\n return\n \n # delete cell[index]\n if index > 0:\n pre_cell = self.get_index_cell(index-1)\n del_target_cell = pre_cell.next_pointer\n \n # 末尾の削除\n if del_target_cell == self.tail:\n self.deleteLast()\n return \n \n # delete cell[index]\n next_cell = del_target_cell.next_pointer\n self._update_doubly_linked_2cells(pre_cell, next_cell)\n del del_target_cell\n \n def to_list(self):\n cell = self.head\n arr = []\n # 空でないとき\n while not cell == None:\n arr.append(cell.data)\n # 次のポインタが空になるまで\n cell = cell.next_pointer\n return arr\n \n \n def print(self):\n cell = self.head\n # 空でないとき\n while not cell == None:\n print(cell.data)\n cell = cell.next_pointer\n\n def print_reverse(self):\n cell = self.tail\n # 空でないとき\n while not cell == None:\n print(cell.data)\n cell = cell.pre_pointer\n",
"execution_count": 19,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T21:56:48.138503",
"end_time": "2017-02-18T21:56:48.147509"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "doubly_l = DoublyLinkedList()\ndoubly_l.addLast(1)\ndoubly_l.addFirst(2)\ndoubly_l.addLast(3)\n\ndoubly_l.print()\nprint()\ndoubly_l.print_reverse()",
"execution_count": 20,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "2\n1\n3\n\n3\n1\n2\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T21:58:12.442598",
"end_time": "2017-02-18T21:58:12.450604"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "doubly_l.insert(0, 4)\ndoubly_l.insert(1, 5)\ndoubly_l.insert(2, 6)\ndoubly_l.insert(6, 7)\n\ndoubly_l.print()\nprint()\ndoubly_l.print_reverse()",
"execution_count": 21,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "4\n5\n6\n2\n1\n3\n7\n\n7\n3\n1\n2\n6\n5\n4\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T21:58:57.794296",
"end_time": "2017-02-18T21:58:57.802301"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "doubly_l.deleteFirst()\n\ndoubly_l.print()\nprint()\ndoubly_l.print_reverse()",
"execution_count": 22,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n6\n2\n1\n3\n7\n\n7\n3\n1\n2\n6\n5\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T21:59:20.129401",
"end_time": "2017-02-18T21:59:20.135406"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "doubly_l.deleteLast()\n\ndoubly_l.print()\nprint()\ndoubly_l.print_reverse()",
"execution_count": 23,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n6\n2\n1\n3\n\n3\n1\n2\n6\n5\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T22:02:15.235818",
"end_time": "2017-02-18T22:02:15.243827"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "doubly_l.delete(0)\ndoubly_l.delete(2)\ndoubly_l.delete(1)\n\ndoubly_l.print()\nprint()\ndoubly_l.print_reverse()",
"execution_count": 24,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "6\n3\n\n3\n6\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T22:02:26.944163",
"end_time": "2017-02-18T22:02:27.003712"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "doubly_l.to_list()",
"execution_count": 25,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[6, 3]"
},
"metadata": {},
"execution_count": 25
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "参考\n\n- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 循環リスト"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "前へのポインタ，次へポインタといった2つのポインタを持ったリスト\n\n双方向リストとの違いは，最後のセルの次ポインタに戦闘データのセルのアドレスを持つ．\n感情に連結したリストになる．\n\n```\nデータアドレス ポインタ\n30 (先頭ポインタ) pre:Null next:50\n ↑ ↓\n50 pre:30 next:70\n ↑ ↓\n70 pre:50 next:110\n ↑ ↓\n110 pre:70 next:90\n ↓ ↓\n90 pre:110 next:30\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 実装メモ"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "基本は，双方向リストと同じ．\n\nHeadとTailの更新があったとき，Tailのセルの次ポインタをHeadのセルに変更する．"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データを末尾へ追加（addLast）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "データを末尾へ追加（addLast）：\n\n新しいデータが末尾へ来るので，次ポインタを先頭セルへ更新する．\n\n```\nold: Head -> Cell1 <- Tail\n\nnew: -> ->\n Head -> Cell1 Cell2 newCell <- Tail\n | -> -> |\n |-------------------\n```\n"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データを先頭へ追加（addFirst）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "新しいデータが先頭になるので，末尾セルの次ポインタを先頭セルへ更新する．\n\n```\nold: Head -> Cell1 <- Tail\n\nnew: -> -> \n Head -> newCell Cell1 Cell2 <- Tail\n | <- <- |\n |--------------------\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの先頭を削除 deleteFirst()"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "先頭セルが2番目のセルに変わるので，末尾セルの次ポインタを2番目のセルへ変更する．\n\n```\n -> -> \nold: Head -> Cell1 Cell2 Cell3 <- Tail\n | <- <- |\n --------------------\n\n ->\nnew: Head -> Cell2 Cell3 <- Tail\n | <- |\n <--------\ndel Cell1\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### データの末尾を削除(deleteLast())"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "末尾セルが（後ろから）2番目のセルに変わるので，2番目のセルの次ポインタを先頭セルへ変更する．\n \n```\n --> -> \nold: Head -> Cell1 Cell(n-1) Cell(n) <- Tail\n | <-- <- |\n -------------------------\n\n -->\nnew: Head -> Cell1 Cell(n-1) <- Tail\n | <-- |\n <----------\ndel Cell(n)\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "#### 循環リストのcode"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:52:36.502597",
"end_time": "2017-02-18T23:52:36.929274"
},
"trusted": true,
"collapsed": true
},
"cell_type": "code",
"source": "class DoubleCell:\n \"\"\"\n cell of doubly-lnked list\n \"\"\" \n def __init__(self, data): # コンストラクタ\n self.data = data\n self.pre_pointer = None\n self.next_pointer = None\n \nclass CircularList:\n '''\n '''\n def __init__(self): # コンストラクタ\n self.head = None\n self.tail = None\n \n def get_index_cell(self, index):\n '''\n if index=0, return head \n '''\n cell = self.head\n for i in range(index):\n cell = cell.next_pointer\n return cell\n \n def _update_doubly_linked_2cells(self, pre_cell, next_cell):\n pre_cell.next_pointer = next_cell\n next_cell.pre_pointer = pre_cell\n \n def _add_init(self, cell):\n self.tail = cell # update list.tail\n self.head = cell # update list.head\n cell.next_pointer = self.head # update chain\n \n def addLast(self, data):\n added_cell = DoubleCell(data)\n\n # 空の場合\n if (not self.head) and (not self.tail):\n self._add_init(added_cell)\n return\n \n # not empty\n self._update_doubly_linked_2cells(self.tail, added_cell)\n self.tail = added_cell # update list.tail\n self.tail.next_pointer = self.head # update chain\n \n def addFirst(self, data):\n added_cell = DoubleCell(data)\n \n # 空の場合\n if (not self.head) and (not self.tail):\n self._add_init(added_cell)\n return\n \n # not empty\n self._update_doubly_linked_2cells(added_cell, self.head)\n self.head = added_cell # update list.head \n self.tail.next_pointer = self.head # update chain\n \n def insert(self, index, data):\n '''\n \n '''\n added_cell = DoubleCell(data)\n \n # 先頭へ追加する場合\n if index == 0:\n self.addFirst(data)\n return \n \n # index目に挿入 \n if index > 0:\n pre_cell = self.get_index_cell(index-1)\n \n # 最後に追加する場合\n if pre_cell == self.tail:\n self.addLast(data)\n return\n \n # index目に挿入 \n next_cell = pre_cell.next_pointer\n self._update_doubly_linked_2cells(pre_cell, added_cell)\n self._update_doubly_linked_2cells(added_cell, next_cell)\n \n \n def deleteFirst(self):\n head_cell = self.head\n second_cell = head_cell.next_pointer\n \n self.head = second_cell \n if not second_cell == None:\n second_cell.pre_pointer = None\n self.tail.next_pointer = self.head # update chain\n \n del head_cell\n \n def deleteLast(self):\n last_cell = self.tail\n second_cell = last_cell.pre_pointer\n \n self.tail = second_cell\n if not self.tail == None:\n self.tail.next_pointer = self.head # update chain\n \n del last_cell\n \n def delete(self, index):\n '''\n 削除対象がnullでない前提\n '''\n # 先頭の削除\n if index == 0:\n self.deleteFirst()\n return\n \n # delete cell[index]\n if index > 0:\n pre_cell = self.get_index_cell(index-1)\n del_target_cell = pre_cell.next_pointer\n \n # 末尾の削除\n if del_target_cell == self.tail:\n self.deleteLast()\n return \n \n # delete cell[index]\n next_cell = del_target_cell.next_pointer\n self._update_doubly_linked_2cells(pre_cell, next_cell)\n del del_target_cell\n \n def to_list(self):\n cell = self.head\n last_cell = self.tail\n arr = []\n # 空でないとき\n while not cell == last_cell:\n arr.append(cell.data)\n # 次のポインタが空になるまで\n cell = cell.next_pointer\n arr.append(cell.data)\n return arr\n \n def print(self):\n cell = self.head\n last_cell = self.tail\n # 空でないとき\n while not cell == last_cell:\n print(cell.data)\n cell = cell.next_pointer\n print(cell.data)\n \n def print_reverse(self):\n cell = self.tail\n first_cell = self.head\n # 空でないとき\n while not cell == first_cell:\n print(cell.data)\n cell = cell.pre_pointer\n print(cell.data)\n \n def trace(self, n):\n cell = self.head\n for i in range(n):\n print(cell.data)\n cell = cell.next_pointer\n",
"execution_count": 28,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:52:40.181310",
"end_time": "2017-02-18T23:52:40.189316"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "circular_l = CircularList()\ncircular_l.addLast(1)\ncircular_l.addFirst(2)\ncircular_l.addLast(3)\n\ncircular_l.print()\nprint()\ncircular_l.print_reverse()",
"execution_count": 29,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "2\n1\n3\n\n3\n1\n2\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:52:52.843626",
"end_time": "2017-02-18T23:52:52.852634"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "circular_l.insert(0, 4)\ncircular_l.insert(1, 5)\ncircular_l.insert(2, 6)\ncircular_l.insert(6, 7)\n\ncircular_l.print()\nprint()\ncircular_l.print_reverse()",
"execution_count": 30,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "4\n5\n6\n2\n1\n3\n7\n\n7\n3\n1\n2\n6\n5\n4\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:53:04.846240",
"end_time": "2017-02-18T23:53:04.853244"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "circular_l.deleteFirst()\n\ncircular_l.print()\nprint()\ncircular_l.print_reverse()",
"execution_count": 31,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n6\n2\n1\n3\n7\n\n7\n3\n1\n2\n6\n5\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:53:17.583508",
"end_time": "2017-02-18T23:53:17.589512"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "circular_l.deleteLast()\n\ncircular_l.print()\nprint()\ncircular_l.print_reverse()",
"execution_count": 32,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "5\n6\n2\n1\n3\n\n3\n1\n2\n6\n5\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:54:04.333112",
"end_time": "2017-02-18T23:54:04.341118"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "circular_l.delete(0)\ncircular_l.delete(2)\ncircular_l.delete(1)\n\ncircular_l.print()\nprint()\ncircular_l.print_reverse()",
"execution_count": 33,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "6\n3\n\n3\n6\n"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2017-02-18T23:54:13.934403",
"end_time": "2017-02-18T23:54:13.940407"
},
"trusted": true,
"collapsed": false
},
"cell_type": "code",
"source": "circular_l.trace(5)",
"execution_count": 34,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": "6\n3\n6\n3\n6\n"
}
]
}
],
"metadata": {
"language_info": {
"name": "python",
"mimetype": "text/x-python",
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"nbconvert_exporter": "python",
"file_extension": ".py",
"pygments_lexer": "ipython3",
"version": "3.5.2"
},
"latex_envs": {
"eqNumInitial": 1,
"eqLabelWithNumbers": true,
"current_citInitial": 1,
"cite_by": "apalike",
"bibliofile": "biblio.bib",
"LaTeX_envs_menu_present": true,
"labels_anchors": false,
"latex_user_defs": false,
"user_envs_cfg": false,
"report_style_numbering": false
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3",
"language": "python"
},
"toc": {
"threshold": "6",
"number_sections": true,
"toc_cell": true,
"toc_window_display": true,
"toc_section_display": "block",
"sideBar": true,
"navigate_menu": false,
"moveMenuLeft": false,
"colors": {
"hover_highlight": "#DAA520",
"selected_highlight": "#FFD700",
"running_highlight": "#FF0000"
},
"toc_position": {
"right": "884px",
"height": "505px",
"top": "130px",
"width": "274px",
"left": "0px"
}
},
"gist": {
"id": "3ebb2e2669fa8da0daa0b92a6e1c577e",
"data": {
"description": "DataStructure リスト構造",
"public": true
}
},
"_draft": {
"nbviewer_url": "https://gist.github.com/3ebb2e2669fa8da0daa0b92a6e1c577e"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment