221011 알고리즘 정리

시작하기 전.

a = head
for i in range(len(dataArray)):
    print(a.data,end=' ')
    a = a.link

이 코드를 짜서

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

이런 귀찮은 코드를 짤 필요 없게 만들었다.

---

원형연결리스트 생성

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

a = node1
for i in range(7):
    print(a.data,end=' ')
    a = a.link

>>청하 미란이 린 청하 미란이 린 청하 

---

for문을 이용한 연결 리스트 생성

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

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

current = node
for data in dataArray[1:]:
    node = Node()
    node.data = data
    current.link = node
    node.link = head
    current = node
    
a = head
for i in range(len(dataArray)):
    print(a.data,end=' ')
    a = a.link

>>수한무 거북이 두루미 삼천갑자 동방삭 

---

첫번째 위치에 노드 삽입

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

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

last.link = node
head = node

a = head
for i in range(7):
    print(a.data,end=' ')
    a = a.link

>>김 수한무 거북이 두루미 삼천갑자 동방삭 김 

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

---

중간 위치에 노드 삽입(거북이를 찾아 자라를 추가)

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

a = head
for i in range(len(dataArray)):
    print(a.data,end=' ')
    a = a.link

>>김 수한무 자라 거북이 두루미 

#1. 거북이 찾기 => pre.current에 저장하면서 이동
#2. 거북이 찾으면 새 노드 생성
#3. 새 노드에 자라입력 -> 새 노드.link = current로 -> pre.lin = 새 노드

---

첫번째 노드 삭제

current = head
head = head.link
last = head
while last.link != current:
    last = last.link
    
last.link = head
del(current)

a = head
for i in range(len(dataArray)):
    print(a.data,end=' ')
    a = a.link

>>수한무 자라 거북이 두루미 삼천갑자

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

---

중간위치 노드 삭제

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

a = head
for i in range(len(dataArray)):
    print(a.data,end=' ')
    a = a.link

>>수한무 자라 두루미 삼천갑자 동방삭

#1. 거북이 찾기
#2. pre.current에 위치 지정하면서 찾기
#3. pre.link = current.link로 수정
#4. current노드 삭제