2019-06-11に投稿

Pythonで学ぶ データ構造入門 List編

TL;DR

データ構造の基本であるList(LinkedList)やHashMap、Queue、Dequeを自分で実装して理解を深めようという趣旨でやっていきます。

まずはLinkedListを作ってみる

LinkedListとは、リストの各々の要素に次の要素への参照をつけておくことで一連のデータを表現できるデータ構造です。

data structure.png

このように、それぞれの要素が次への参照とデータを持っています。
これをPythonで実装してみます。
まずはそれぞれの要素のクラスです。

```python:要素
class Element:
"""
Element(data, next)

LinkedListのそれぞれの要素のクラス。
dataはこの要素が表すデータ。
nextはこの次の要素の参照。
"""
def __init__(self, data, next=None):
    self.data = data
    self.next = next

次にリスト本体を実装してみます。 ```python:LinkedList class LinkedList: def __init__(self): self.first = None @property def is_empty(self): return self.first is None def append(self, data): if self.is_empty: self.first = Element(data) return nxt = self.first while nxt.next is not None: nxt = nxt.next nxt.next = Element(data) def pop(self): if self.is_empty: raise ValueError nxt = self.first while nxt.next is not None: nxt = nxt.next # 最後の要素のデータを一時変数に退避 last = nxt.next.data # 最後の要素への参照を消す nxt.next = None return last def remove(self, idx): # 最初ならself.firstを変更 if idx == 0: f = self.first self.first = f.next return f.data size = len(self) if idx >= size or idx < 0: raise IndexError(idx) if self.is_empty: raise ValueError # 最後ならpop if idx == size - 1: return self.pop() nxt = self.first for _ in range(idx - 1): nxt = nxt.next rem = nxt.next nxt.next = rem.next return rem.data def insert(self, idx, data): # 最初ならself.firstを変更 if idx == 0: self.first = Element(data, self.first) return size = len(self) if idx > size or idx < 0: raise IndexError(idx) # 最後+1ならappend if idx == size: self.append(data) return nxt = self.first for _ in range(idx): nxt = nxt.next nxt.next = Element(data, nxt.next) def __iter__(self): nxt = self.first while nxt.next is not None: yield nxt.data nxt = nxt.next def __len__(self): if self.is_empty: return 0 nxt = self.first ret = 1 while nxt.next is not None: nxt = nxt.next ret += 1 return ret def __getitem__(self, idx): if idx >= len(self) or idx < 0: raise IndexError(idx) if self.is_empty: raise ValueError nxt = self.first for _ in range(idx): nxt = nxt.next return nxt.data def __setitem__(self, idx, val): if idx >= len(self) or idx < 0: raise IndexError(idx) if self.is_empty: raise ValueError nxt = self.first for _ in range(idx): nxt = nxt.next nxt.data = val

こんな感じですね。
これが一番単純なLinkedListの実装です。
ですけど、結構非効率的ですね。

例えば、一番後ろのデータを取得するために最初から全部辿っています。
データにアクセスするためにすべて前からアクセスするのでは、後半のデータにアクセスする際に非効率になってしまいます。
これを解決するのが双方向リストというものです。

(次回があれば)これを双方向リストに改造してみたいと思います。
今日のところはここまでにしましょう。それがいい。


frodo821

Pythonをこよなく愛するプログラマ。広く浅くアンテナを張っている(つもり)。 出来ることと言えばフロントエンド全般やJava、Kotlinを使ったアプリ開発、PHP/Pythonでバックエンドが少々にC#、Python、Java、Kotlin、Scalaなどを使ったデスクトップ開発くらいのもの。PyPIで自作ライブラリ公開したりもしている。https://pypi.org/project/rattlepy/ 好きなフロントエンドフレームワークはReact、バックエンドフレームワークはCodeIgniterとMasonite。自分のサイトもReactを使って構築した。

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

関連記事

コメント