[TIL] Linked List
17572 ワード
Linked List
コンピューターに資料を保存する構造です.シリアル接続のデータを格納します.
例)AからBに移るとき,AにはBのアドレスがある.アレイと比較して、アレイが部屋全体の大きさを決定すると、増加または減少することはできません.ただし、真ん中にデータを挿入したい場合は、AとBの間に任意にデータを追加できます.
Array List
メモリ内の連続したシェイプ.
Linked List
メモリは任意に占有されますが、それぞれが接続されています.
(下図参照)
リンクリストの形式:
写真の破線の部分は1つのノードで、写真には全部で4つのノードがあります.
ノード頂点メモリはdatafieldとlinkfieldです.
単純リンクリスト(単一接続リスト)
Sivey Linked Listは、各ノードに1つのデータ空間と1つのポインタ空間(次のノードアドレスを含む空間)を有し、各ノードのポインタは次のノードを指す.
# Node 클래스 선언
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
# Singly linked list 클래스 선언
class SinglyLinkedList(object):
def __init__(self):
self.head = None
self.count = 0
# Add new node at the end of the linked list
def append(self, node):
if self.head == None:
self.head = node
else:
cur = self.head
while cur.next != None:
cur = cur.next
cur.next = node
# return first index of data in the linked list
def getdataIndex(self, data):
curn = self.head
idx = 0
while curn:
if curn.data == data:
return idx
curn = curn.next
idx += 1
return -1
# Add new node at the given index
def insertNodeAtIndex(self, idx, node):
"""
A node can be added in three ways:
1) At the front of the linked list.
2) At a given index.
3) At the end of the linked list.
"""
curn = self.head
prevn = None
cur_i = 0
# (1) Add 0 index
if idx == 0:
if self.head:
nextn = self.head
self.head = node
self.head.next = nextn
else:
self.head = node
else:
# (2) Add at given index &
# (3) At the end of the linked list
while cur_i < idx:
if curn:
prevn = curn
curn = curn.next
else:
break
cur_i += 1
if cur_i == idx:
node.next = curn
prevn.next = node
else:
return -1
# Add new node before the given data
def insertNodeAtData(self, data, node):
index = self.getdataIndex(data
if 0 <= index:
self.insertNodeIndex(index, node)
else:
return -1
# Delete data at given index.
def deleteAtIndex(self, idx):
curn_i = 0
curn = self.head
prevn = None
nextn = self.head.next
if idx == 0:
self.head = nextn
else:
while curn_i < idx:
if curn.next:
prevn = curn
curn = nextn
nextn = nextn.next
else:
break
if curn_i == idx:
prevn.next = nextn
else:
return -1
# Empty linked list
def clear(self):
self.head = None
# 출력
def print(self):
curn = self.head
string = ""
while curn:
string += str(curn.data)
if curn.next:
string += "->"
curn = curn.next
print(string)
if __name__ == "__main__":
s1 = SinglyLinkedList()
s1.append(Node(1))
s1.append(Node(2))
s1.append(Node(3))
s1.append(Node(5))
s1.insertNodeAtIndex(3, Node(4))
s1.print()
print(s1.getdataIndex(1))
print(s1.getdataIndex(2))
print(s1.getdataIndex(3))
print(s1.getdataIndex(4))
print(s1.getdataIndex(5))
s1.insertNodeAtData(1, Node(0))
s1.print()
ダブルリンクリスト
Circularチェーンテーブル(リング接続リスト)
Reference
この問題について([TIL] Linked List), 我々は、より多くの情報をここで見つけました https://velog.io/@kimsj5259/TIL-Linked-Listテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol