[Python] 단순 연결 리스트

단순 연결 리스트

• 노드들이 물리적으로 떨어진 곳에 위치
• 각 노드의 번지도 순차적이지 않음
• 화살표로 표시된 연결(link)을 따라가면 선형리스트와 순서가 같음
• 데이터를 삽입/삭제할 때 해당 노드의 앞뒤 링크만 수정하면 되므로 오버헤드가 거의 발생하지 않음

• List(정렬) : 데이터들을 잘 관리하기 위해 묶어서관리할 수 있는 자료형
• Node(노드) : 데이터
• self: class 내의 요소

---

1. 노드 생성

✍ 입력

class Node:							# Node라는 class 생성
    def __init__(self) -> None:		# 함수 선언
        self.data = None  # 현재 값
        self.link = None  # 다음 노드가리킴
    
    def __str__(self) -> str:
        return f'{self.data}'

self.data : 현재 값을

2. 첫번째 노드 생성

✍ 입력

node1 = Node()
node1.data = '셔누'

print(node1)

💻 출력
셔누

3. 두번째 노드 생성

✍ 입력

node2 = Node()
node2.data = '민혁'
node1.link = node2      # 1번 노드의 링크에 두번째 노드를 연결

print(node2)

💻 출력
민혁

4. 나머지 노드 생성

✍ 입력

node3 = Node()
node3.data = '기현'
node2.link = node3

node4 = Node()
node4.data = '형원'
node3.link = node4

node5 = Node()
node5.data = '주헌'
node4.link = node5

node6 = Node()
node6.data = '아이엠'
node5.link = node6

5. 연결 리스트 출력(link)

✍ 입력

print(node1.data, end=' -> ')
print(node1.link.data, end=' -> ')                  # node2.data
print(node1.link.link.data, end=' -> ')             # node3.data
print(node1.link.link.link.data, end=' -> ')        # node4.data
print(node1.link.link.link.link.data, end=' -> ')   # node5.data
print(node1.link.link.link.link.link.data)          # node6.data

💻 출력
셔누 -> 민혁 -> 기현 -> 형원 -> 주헌 -> 아이엠

6. 연결 리스트 출력

✍ 입력

print(node1.data, end=', ')         # node1.data
print(node2.data, end=', ')         # node2.data
print(node3.data, end=', ')         # node3.data
print(node4.data, end=', ')         # node4.data
print(node5.data, end=', ')         # node5.data
print(node6.data)                   # node6.data

💻 출력
셔누, 민혁, 기현, 형원, 주헌, 아이엠

✍ 입력

current = node1
print(current.data, end=' -> ')
while current.link != None:
    current = current.link
    if current.link == None:
        print(current.data)      # 뒤에 연결링크가 없으면(마지막 노드) end=' -> ' 삭제
    else:
        print(current.data, end=' -> ')

💻 출력
셔누 -> 민혁 -> 기현 -> 형원 -> 주헌 -> 아이엠

7. 연결리스트에 새 노드 삽입

✍ 입력

newNode = Node()
newNode.data = '덕준'
newNode.link = node2.link   # node3: kihyun
node2.link = newNode

💻 출력
셔누 -> 민혁 -> 덕준 -> 기현 -> 형원 -> 주헌 -> 아이엠

8. 노드 삭제

✍ 입력

node3.link = node4.link   

💻 출력
셔누 -> 민혁 -> 덕준 -> 기현 -> 주헌 -> 아이엠

• 형원 삭제
• 메모리상에 여전히 노드는 남아 있음

✍ 입력

del(node3) 

노드 완전 삭제