まず、双方向リンクリストのノードを表すクラスを作成します。各ノードは、データと前後のノードへの参照を持ちます。
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None次に、双方向リンクリストを表すクラスを作成します。このクラスでは、リストの先頭と末尾のノードへの参照を保持します。
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None双方向リンクリストには、以下のような基本的な操作があります。
- ノードの挿入
- ノードの削除
- リストの先頭への要素の追加
- リストの末尾への要素の追加
- リストの先頭から末尾への要素の表示
- リストの末尾から先頭への要素の表示
- 特定の要素の検索
- リストの要素数の取得
それでは、各操作のコード例を示します。
- ノードの挿入
def insert(self, data, position):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
if position == 0:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
else:
current = self.head
count = 0
while current.next is not None and count < position:
current = current.next
count += 1
if count == position:
new_node.prev = current.prev
new_node.next = current
current.prev.next = new_node
current.prev = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node- ノードの削除
def delete(self, position):
if self.head is None:
return
if position == 0:
if self.head.next is None:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
else:
current = self.head
count = 0
while current.next is not None and count < position:
current = current.next
count += 1
if count == position:
if current.next is None:
self.tail = current.prev
current.prev.next = None
else:
current.prev.next = current.next
current.next.prev = current.prev- リストの先頭への要素の追加
def add_first(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node- リストの末尾への要素の追加
def add_last(self, data):
new_node = Node(data)
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node- リストの先頭から末尾への要素の表示
def display_forward(self):
以下のコードを使用して、リストの要素を先頭から末尾に表示できます。
```python
def display_forward(self):
current = self.head
while current is not None:
print(current.data)
current = current.next- リストの末尾から先頭への要素の表示
def display_backward(self): current = self.tail while current is not None: print(current.data) current = current.prev - 特定の要素の検索
def search(self, data): current = self.head while current is not None: if current.data == data: return True current = current.next return False - リストの要素数の取得
def size(self): count = 0 current = self.head while current is not None: count += 1 current = current.next return count
これらは双方向リンクリストの基本的な操作例です。さまざまな操作を組み合わせて、さらに高度な機能や応用を実装することもできます。