面接準備/資料構造4/リンクリスト
一般的なデータ構造:リンクリスト
1.リンクリスト構造
接続リストとも呼ばれます
配列は、順次接続された空間にデータがリストされるデータ構造です.
「リンク」(Link)リストは、分散したデータを矢印で接続して管理するデータ構造です.
C言語では主要なデータ構造であるが、Pythonのリストタイプはリンクリストのすべての機能をサポートしている.
リンクリストの基本構造と用語
(出典:wikipedia、https://en.wikipedia.org/wiki/Linked_list)
2.簡単なリンクリストの例
Node実装
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
ノードとノードの接続(ポインタを使用)
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1
リンクリストへのデータの追加
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def add(data):
node = head
while node.next:
node = node.next
node.next = Node(data)
node1 = Node(1)
head = node1
for index in range(2, 10):
add(index)
リンクリストデータの出力(検索)
node = head
while node.next:
print(node.data)
node = node.next
print (node.data)
1
2
3
4
5
6
7
8
9
3.リンクリストの長所と短所(従来のC言語の配列とリンクリスト)
4.リンクリストの複雑な機能1(リンクリストデータ間にデータを追加)
(出典:wikipedia、https://en.wikipedia.org/wiki/Linked_list)
node = head
while node.next:
print(node.data)
node = node.next
print (node.data)
1
2
3
4
5
6
7
8
9
node3 = Node(1.5)
node = head
search = True
while search:
if node.data == 1:
search = False
else:
node = node.next
node_next = node.next
node.next = node3
node3.next = node_next
node = head
while node.next:
print(node.data)
node = node.next
print (node.data)
1
1.5
2
3
4
5
6
7
8
9
5.オブジェクト向けPythonプログラミングによるリンクリストの実装
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
def add(self, data):
if self.head == '':
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
0
for data in range(1, 10):
linkedlist1.add(data)
linkedlist1.desc()
0
1
2
3
4
5
6
7
8
9
6.リンクリストの複雑な機能2(特定のノードを削除)
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
def add(self, data):
if self.head == '':
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
def delete(self, data):
if self.head == '':
print ("해당 값을 가진 노드가 없습니다.")
return
if self.head.data == data:
temp = self.head
self.head = self.head.next
del temp
else:
node = self.head
while node.next:
if node.next.data == data:
temp = node.next
node.next = node.next.next
del temp
return
else:
node = node.next
テスト用のノードを作成
linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
0
headが生きていることを確認する
linkedlist1.head
<__main__.Node at 0x1099fc6a0>
クリアヘッド(前述の数字1)
linkedlist1.delete(0)
Linkedlist 1は、次のコードの実行時に何も表示されないことを示します。headが正常に削除されたことを示します
linkedlist1.head
ノードを再作成
linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
0
今回追加するノード
for data in range(1, 10):
linkedlist1.add(data)
linkedlist1.desc()
0
1
2
3
4
5
6
7
8
9
ノードの1つを削除します(前述の数2)
linkedlist1.delete(4)
特定のノードが削除されたことを示すメッセージ
linkedlist1.desc()
0
1
2
3
5
6
7
8
9
linkedlist1.delete(9)
linkedlist1.desc()
0
1
2
3
5
6
7
8
練習1:上記コードからノードデータが2のノードを削除してみるnode_mgmt.delete(2)
node_mgmt.desc()
練習2:上記のコードで関数を作成し、テストして、ノードデータが特定の数値のノードを検索します.テスト:ランダムに1から9までのデータをリンクリストに入れ、データ値が4のノードのデータ値を出力しようとします.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
def add(self, data):
if self.head == '':
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
def delete(self, data):
if self.head == '':
print ('해당 값을 가진 노드가 없습니다.')
return
if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
del temp
else:
node = self.head
while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
if node.next.data == data:
temp = node.next
node.next = node.next.next
del temp
pass
else:
node = node.next
def search_node(self, data):
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
# 테스트
node_mgmt = NodeMgmt(0)
for data in range(1, 10):
node_mgmt.add(data)
node = node_mgmt.search_node(4)
print (node.data)
7.複数のリンクリスト構造
(出典:wikipedia、https://en.wikipedia.org/wiki/Linked_list)
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
double_linked_list = NodeMgmt(0)
for data in range(1, 10):
double_linked_list.insert(data)
double_linked_list.desc()
0
1
2
3
4
5
6
7
8
9
練習3:上記のコードでは、ノードデータが特定の数値のノードになる前にデータを追加する関数を作成してテストします.-二重リンクリストのtailから後ろに移動し、ノードの特定の番号を検索して関数を実装します.
-テスト:リンクリスト0~9にランダムにデータを入れ、データ値2のノードの前に1.5個のデータ値のノードを追加します.
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
def search_from_head(self, data):
if self.head == None:
return False
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
return False
def search_from_tail(self, data):
if self.head == None:
return False
node = self.tail
while node:
if node.data == data:
return node
else:
node = node.prev
return False
def insert_before(self, data, before_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node == None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new
return True
double_linked_list = NodeMgmt(0)
for data in range(1, 10):
double_linked_list.insert(data)
double_linked_list.desc()
0
1
2
3
4
5
6
7
8
9
node_3 = double_linked_list.search_from_tail(3)
node_3.data
3
double_linked_list.insert_before(1.5, 2)
double_linked_list.desc()
0
1
1.5
2
3
4
5
6
7
8
9
node_3 = double_linked_list.search_from_tail(1.5)
node_3.data
1.5
練習4:上記のコードでは、ノードデータが特定の数値のノードの後にデータを追加する関数を作成してテストします.-二重リンクリストのheadから次のノードに移動し、特定の番号のノードを検索することで関数を実装します.
-テスト:リンクリストにランダムにデータを入れ、データ値が1のノードの後に1.7個のデータ値のノードを追加しようとします.
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert_before(self, data, before_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node == None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.next = node
return True
def insert_after(self, data, after_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.head
while node.data != after_data:
node = node.next
if node == None:
return False
new = Node(data)
after_new = node.next
new.next = after_new
new.prev = node
node.next = new
if new.next == None:
self.tail = new
return True
def insert(self, data):
if self.head == None:
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
node_mgmt = NodeMgmt(0)
for data in range(1, 10):
node_mgmt.insert(data)
node_mgmt.desc()
node_mgmt.insert_after(1.5, 1)
node_mgmt.desc()
Reference
この問題について(面接準備/資料構造4/リンクリスト), 我々は、より多くの情報をここで見つけました https://velog.io/@bbkyoo/면접준비자료구조4링크드-리스트テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol