2022.10.04 알고리즘 정리

알고리즘 5주차 정리

단순연결리스트

class Node():
    def __init__(self):
        self.data = None
        self.link = None
    
node1 = Node()
node1.data = '선모'

head = node1
node1 = Node()
node1.data = '재서'

head.link = node1

node2 = Node()
node2.data = '승권'
node1.link = node2

node3 = Node()
node3.data = '평화'
node2.link = node3

node4 = Node()
node4.data = '나'
node3.link = node4

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=' ')

출력 결과
선모 재서 승권 평화 나 

반복문을 이용하여 한 번에 생성

 

dataArray = ['1','2','3','4','5']

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

for data in dataArray[1:]:
    pre=node
    node = Node()
    node.data = data
    pre.link = node
    
print(head.data, end=' ')
print(head.link.data, end=' ')
print(head.link.link.data, end=' ')

출력 결과
1 2 3

 

맨 앞에 노드 추가

node = Node()
node.link = head
node.data = '처음'
head = node

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

출력 결과
처음 1 2

 

원하는 자리에 노드를 생성하고 해당하는 값이 없는 경우 맨 끝에 생성

1. pre, current 지정
2. 노드 검색
3. 새 노드 생성
4. 새 노드.link를 current 노드로 지정
5. pre노드의 link를 새 노드로 지정

pre = head
current = head.link

while current.link != None:
    if current.data == '3':
        node = Node()
        node.link = current
        node.data = '이점오'
        pre.link = node
        break
        
    pre = current
    current = current.link

node = Node()
node.data = '마지막'
current.link = 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=' ')
print(head.link.link.link.link.link.data, end=' ')

 

첫 번째 노드 삭제 구현

current = head
head = head.link
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=' ')

 

원하는 노드 삭제 구현

1. 두번째 노드를 cuurrent로 지정하여 시작
2. current노드 이전 노드를 pre 노드로 지정
3. 삭제할 노드를 찾을 때까지 current와 pre 노드를 이동
4. pre 노드 링크를 current노드 링크로 변경
5. current 노드 삭제

current = head

while current.link != None:
    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=' ')