class Node:
def __init__(self,value = None, next = None):
self.data = value
self.next = next
self.number = 0
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self, head = None):
self.node = Node(head)
self.head = self.node
#리스트에 노드 추가
def AppendNode(self,data):
pre_node = self.node
self.node = Node(data)
pre_node.next = self.node
self.node.number = pre_node.number + 1
#loc번째 노드에 든 값
def GetNodeAt(self,loc):
new_node = self.head
while new_node.next:
if new_node.number+1 == loc:
print (new_node.data)
break
else:
new_node = new_node.next
#리스트의 길이
def GetNodeCount(self):
return self.node.number+1
#loc번째 자리에 data값의 노드 추가
def InsertNodeAt(self,loc,data):
node_head = self.head
insert_node = Node(data)
insert_node.number = loc-1
temp = Node()
while node_head.next:
if node_head.number+2 == loc:
temp = node_head.next
node_head.next = insert_node
insert_node.next = temp
break
else:
node_head = node_head.next
while True:
temp.number = temp.number + 1
temp = temp.next
if temp.next == None:
temp.number = temp.number + 1
break
#data값이 든 노드 삭제
def Remove(self,data):
node_head = self.head
node_temp = self.head
remove_node = Node(data)
while node_head.next:
if node_head.data == remove_node.data:
while True:
if node_head.number == node_temp.number:
self.head = self.head.next
break
elif node_temp.number == node_head.number - 1:
node_temp.next = node_head.next
break
else:
node_temp = node_temp.next
break
else:
node_head = node_head.next
temp = node_temp.next
while True:
temp.number = temp.number - 1
temp = temp.next
if temp.next == None:
temp.number = temp.number - 1
break
#리스트에 리스트 추가
def ExtendList(self, aList):
for k in aList:
node_add = Node(k)
self.AppendNode(node_add)
#리스트 전체 출력
def PrintLL(self):
node_print = self.head
while True :
if node_print.next == None:
print(node_print.data)
break
else:
print(node_print.data , "->", end=" ")
node_print = node_print.next
#리스트 k 생성
k = LinkedList(4)
#k 리스트에 노드 추가
k.AppendNode(1)
k.AppendNode(2)
k.AppendNode(3)
k.AppendNode(4)
k.AppendNode(5)
#k 리스트 출력
k.PrintLL()
#k리스트에 5번째 자리에 3 추가
k.InsertNodeAt(5,3)
k.PrintLL()
#데이터 4 를 가진 노드 삭제
k.Remove(4)
k.PrintLL()
#리스트[1,2,3]을 리스트k에 추가
k.ExtendList([1,2,3])
k.PrintLL()
1. class Node:
먼저 노드 클래스는 __init__함수와 __str__함수로 구성했다.
Node는 data , next, number로 구성했는데 data는 그 노드의 값, next는 그 다음 링크되어진 값을 가리킨다. 넘버는 위치를 알때 쓰기위해서 만들었다.
2. class LinkedList:
먼저 링크 클래스에서는 초기값으로 노드와 그 노드값중 제일 처음을 가리키는 헤드값을 준다.
2-1. AppendNode( self, data )
AppendNode는 노드를 하나씩 추가해주기 때문에 먼저 현재 가리키는 노드를 받은 data값으로 만들어 주고 원래 제일 마지막 노드를 가리키는 self.node의 next를 만들어준 노드로 가리키게 하고 self.node를 다시 새로만든 노드로 가리키게 해준다. 또 새로만든 노드의 number값은 그 전값의 +1을 해준다.
2-2 GetNodeAt( self, loc )
loc번째의 노드에 든 값을 나타내어 준다. 먼저 노도의 헤드부분을 가리키는 값을 만들고 while문으로 처음부터 맨 마지막값까지
if문을 써서 인덱스 값은 0 부터 시작하기에 그값에 1을 더한값의 위치일때 그 값을 출력해준다.
2-3 InsertNodeAt( self, loc, data )
loc번째 자리에 data값의 노드를 추가해주는 함수로 우선 넣어줄 자리를 알아야 한다. 그렇기 때문에 먼저 넣어줄 loc번째 자리에 -1값을 만들어준 노드의 number에 넣어주고 또 while문을 돌려준다. 우선 넣어줄 노드의 앞의 값을 알아야 하기때문에 넣어줄 자리보다 2자리 앞의 값을 찾아서 그값의 next를 넣어줄 데이터로 또 그 다음 자리를 넣어줄 노드의 next값으로 만든다. 그리고 그 뒤의 자리에 값들은 모두 number값에 1을 더해준다.
2-4 GetNodeCount(self)
self.node의 값은 항상 제일 마지막 자리를 가리키고 있기 때문에 self.node의 number값에 1을 더한 값이 전체 길이!
2-5 Remove( self, data )
먼저 변수가 node_head는 제일처음부터 차례로 내려가면서 삭제할 데이터와 비교할 값이고 node_temp는 삭제할 값 전 노드를 가리킬 변수이다. 우선 삭제할 데이터 값과 현재의 값을 비교하면서 헤드값을 차례로 내려간다. 그리고 삭제할 값과 비교값이 같을때
우선 제일 첫 헤드노드가 temp노드와 같을때 즉 self.head노드가 삭제할 값일 때 self.head를 next값으로 해줌으로써 제일 앞 노드를 삭제했다. 또 그 다음은 temp노드가 비교노드의 바로 전값이 되기 전까지 내려주고 전 값이면 temp노드의 next를 비교노드의 next와 연결해 줌으로써 가운데 값을 삭제해 준다. 그리고 그후는 삭제된 노드의 다음자리부터 모두 number값을 하나씩 줄여 줌으로써 number값도 세팅해 준다.
2-6 ExtendList( self, aList)
이 함수는 노드를 linked list형으로 바꾸어 주는 것 으로 for 문으로 리스트를 받아 하나씩 AppendNode로 이어준다.
2-7 PrintLL(self)
전체 LinkedList를 끝자리가 아니면 계속해서 이어서 출력해주는 함수이다.
'파이썬으로 구현한 알고리즘' 카테고리의 다른 글
| Regular Expression으로 전화번호 Search 구현하기 (0) | 2017.11.16 |
|---|---|
| Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기 (0) | 2017.11.16 |
| Boyer-Moore Algorithm 구현하기 (0) | 2017.11.11 |
| KMP Algorithm 구현하기 (0) | 2017.11.11 |
| Priority Que 구현하기(우선순위 큐) (0) | 2017.09.25 |