2022.10.11 알고리즘 정리

6주차 알고리즘 정리

 

원형 연결 리스트
- 시작 위치와 다음 위치가 계속 이어진 후 마지막에 다시 시작으로 돌아오는 형태

class Node():
    def __init__(self):
        self.data = None
        self.link = None
    

node1 = Node()
node1.data = '청하'
node1.link = node1

node2 = Node()
node2.data = '미란이'
node1.link = node2
node2.link = node1

node3 = Node()
node3.data = '린'
node2.link = node3
node3.link = node1

print(node1.data, end = ' ')
print(node1.link.data, end = ' ')
print(node1.link.link.data, end = ' ')

 

for문으로 원형 리스트 만들기

dataArray = ['수한무','거북이','두루미','삼천갑자','동방삭']

node = Node()
node.data = dataArray[0]
head = node
node.link = head

current = node
for i in dataArray[1:]:
    node = Node()
    node.data = i
    current.link = node
    node.link = head
    current = node

print(head.data, end = ' ')
print(head.link.data, end = ' ')
print(head.link.link.data, end = ' ')
print(head.link.link.link.data, end = ' ')
print(head.link.link.link.link.data, end = ' ')

 

노드 삽입
첫 번째 위치에 노드 삽입

1. 새 노드 생성
2. 새 노드.link = head로
3. 마지막 노드 찾기 (while 노드.link != head)
4. 마지막노드.link = 새노드
5. head = 새노드

node = Node()
node.data = '김'
node.link = head

last = head
while last.link != head:
    last = last.link

last.link = node
head = node

print(head.data, end = ' ')
print(head.link.data, end = ' ')
print(head.link.link.data, end = ' ')
print(head.link.link.link.data, end = ' ')
print(head.link.link.link.link.data, end = ' ')

 

중간 위치에 노드 삽입 (거북이를 찾아 자라를 추가) -> 두 번째 노드부터 삽입하는 로직
1. 거북이 찾기 : pre.current에 저장하면서 이동
2. 거북이를 찾으면 새 노드 생성
3. 새노드에 자라 저장
4. 새노드.link = current
5. pre.link = 새노드

pre = head
current = head

while current.link != head:
    pre = current
    current = current.link
    if current.data == '거북이':
        node = Node()
        node.data = '자라'
        node.link = current
        pre.link = node
        break

print(head.data, end = ' ')
print(head.link.data, end = ' ')
print(head.link.link.data, end = ' ')
print(head.link.link.link.data, end = ' ')
print(head.link.link.link.link.data, end = ' ')

 

노드 삭제

첫 번째 위치 노드 삭제
1. 첫 번째 노드를 current로 지정
2. head를 다음 위치 노드로 지정
3. 마지막 노드를 찾아서 한 노드 씩 이동하며 검색
4. 마지막노드.link = head
5. current노드 삭제

current = head
head = head.link

last = head

while last.link != current:
    last = last.link

last.link = head
del(current)

print(head.data, end = ' ')
print(head.link.data, end = ' ')
print(head.link.link.data, end = ' ')
print(head.link.link.link.data, end = ' ')
print(head.link.link.link.link.data, end = ' ')

 

중간 위치 노드 삭제

pre = head
current = head
while current.link != head:
    pre = current
    current = current.link
    if current.data == '거북이':
        pre.link = current.link
        del(current)
        break

print(head.data, end = ' ')
print(head.link.data, end = ' ')
print(head.link.link.data, end = ' ')
print(head.link.link.link.data, end = ' ')
print(head.link.link.link.link.data, end = ' ')