지난 시간 단순 연결리스트의 추가 연산에 대해서 알아보았습니다.
파이썬으로 연결리스트 만들기 2탄 : 단순 연결리스트 추가 연산 (연결리스트 자동 출력 만들기)
이전에 만들었던 코드에 이어서 이번에는 추가 연산을 하는 기능을 추가해보겠습니다. 추가 연산은 두 가지 경우의 수가 있음을 유추해볼 수 있습니다. 1. 이미 있는 연결리스트의 뒤에 추가하
c-i-s.tistory.com
이번에는 원하는 위치에 삽입하는 과정에 대해서 알아보도록 하겠습니다. 그림으로 우선 알아보도록 하겠습니다.
원리는 간단합니다. 삽입할 위치에 노드를 연결시켜주면 됩니다. 이렇게만 말만하면 너무 쉽게 느껴집니다. 이 과정을 조금 더 자세하게 알아보겠습니다.
위 그림 대로라면?
1) 삽입 할 위치와 리스트에 연결할 값을 입력받는다.
2) 연결할 값으로 우선 새 노드를 만든다.
3) 삽입 할 위치 이전 노드를 찾아서 그 다음 노드가 새 노드를 바라봅니다.
4) 새 노드는 삽입할 위치를 바라봅니다.
우선 파악하고 있어야 하는 정보는 삽입할 위치의 노드와 그 이전 노드 새 노드 총 세 가지 정보에 대해서 알고 있어야 이 문제를 해결 가능합니다.
새 노드는 Node 객체를 이용해서 만들면 됩니다.
그렇다면 삽입할 위치의 노드는 어떻게 찾을 수 있을까요? 인덱스의 개념을 도입하면 알 수 있습니다.
우선 원하는 노드를 찾아보도록 코드를 작성해보겠습니다.
class Node:
def __init__(self, data):
self.data = data # 노드의 값
self.next = None # 다음 노드를 가리키는 정보
class LinkedList:
def __init__(self):
# 연결리스트를 처음 생성 시 아무것도 없으므로 다음과 같이 초기화 할 수 있다.
self.head = None
self.tail = None
self.count = 0
def append(self, value):
"""연결리스트 뒤에 추가하는 메소드"""
new_node = Node(value) # 공통 특징은 우선 새 노드를 생성한다는 것
if self.count == 0: # 연결리스트가 비었을 때
self.head = new_node # 새 노드가 head node가 된다.
self.tail = new_node # 새 노드가 tail node가 된다.
else: # 연결리스트가 안 비어있을 때
self.tail.next = new_node # tail node의 다음이 새 노드를 가리킨다
self.tail = new_node # 새 노드는 tail node가 된다
self.count += 1 # 노드가 추가 되었으니까 갯수를 하나 올린다.
def insert(self, index, value):
"""연결리스트의 원하는 위치에 삽입하는 메소드"""
new_node = Node(value)
i = self.head
for _ in range(index):
i = i.next
print(i.data) # 테스트 코드입니다.
def __str__(self):
"""자동으로 출력해주는 메소드 사용법은 인스턴스를 출력시키면됩니다."""
i = self.head
result = ""
while True:
if i.next is None:
result += str(i.data)
break
else:
result += str(i.data) + " -> "
i = i.next
return result
# 테스트 코드
s = LinkedList()
for i in range(1, 11):
s.append(i)
print(s) # 생성한 인스턴스를 출력하면 __str__이 동작합니다.
s.insert(4, 5)insert 메소드 부분만 보시면 됩니다. 아직 완성 된 것은 아닙니다.
테스트 코드를 보시면 실행결과는 다음과 같습니다.
첫 번째 출력문은 print(s)를 통해서 나왔으며
두 번째 출력문은 s.insert(4, 5)를 통해서 나왔습니다. insert 메소드는 첫 번째 파라미터로 4번째 인덱스를 의미합니다.
때문에 테스트로 insert 메소드 안에는 4번째 노드를 반복문으로 돌려 찾은 결과입니다. 인덱스는 0번 부터 시작하니 5가 나오는 게 맞습니다!
이제 삽입할 위치의 노드는 찾았습니다. 그렇다면 그 이전 노드는 어떻게 찾을까요? 사실 이전 노드를 찾으면 next 인스턴스 변수를 이용하여 삽입할 위치에 접근할 수 있습니다. 때문에 반복문의 횟수를 하나 줄이면 이전 노드를 찾을 수 있습니다.
그렇다면 이제 아래 과정을 코드로 작성하면 됩니다.
3) 삽입 할 위치 이전 노드를 찾아서 그 다음 노드가 새 노드를 바라봅니다.
4) 새 노드는 삽입할 위치를 바라봅니다.
insert 메소드는 따라서 다음과 같이 작성할 수 있습니다.
def insert(self, index, value):
"""연결리스트의 원하는 위치에 삽입하는 메소드"""
new_node = Node(value)
i = self.head
for _ in range(index-1):
i = i.next
prev_node = i # 삽입할 위치의 이전 노드
insert_node = prev_node.next # 삽입 할 위치의 노드
prev_node.next = new_node # 삽입 할 위치 이전 노드를 찾아서 그 다음 노드가 새 노드가 됩니다.
new_node.next = insert_node # 새 노드는 삽입할 위치를 바라봅니다.
self.count += 1 # 노드를 삽입했으니까 1 올림테스트 코드와 실행 결과입니다.
# 테스트 코드
s = LinkedList()
for i in range(1, 11):
s.append(i)
print(s) # 생성한 인스턴스를 출력하면 __str__이 동작합니다.
s.insert(4, "aaa")
print(s)
근데 세 가지 정보가 아니라 두 가지 정보만 알아도 할 수 있습니다.
이전 노드와 새 노드만 있어도 가능합니다.
그러면 방법을 약간 수정해서 한 줄 줄일 수 있습니다.
def insert(self, index, value):
"""연결리스트의 원하는 위치에 삽입하는 메소드"""
new_node = Node(value)
i = self.head
for _ in range(index-1):
i = i.next
prev_node = i # 삽입할 위치의 이전 노드
new_node.next = prev_node.next # 새 노드의 다음은 이전 노드의 다음을 연결해준다.
prev_node.next = new_node # 이전 노드의 다음은 새 노드를 연결한다.
self.count += 1 # 노드를 삽입했으니까 1 올림이렇게 하면 결과는 똑같고 코드는 한 줄 줄었습니다. 그림을 통해 알아보겠습니다.
그래서 이렇게만 하면 끝이냐?
삽입을 할 때 경우의 수가 있는데 잘 생각해보면
맨 앞에 삽입할 때
맨 뒤에 삽입할 때
중간에 삽입할 때
이렇게 세 가지 경우가 있습니다.
지금 만든 것은 중간에 삽일 할 때만 만든 것입니다.
그렇다면 맨 뒤와 맨 앞을 판단하여 거기에 맞는 코드를 넣어주면 됩니다.
지금까지의 내용을 잘 따라오셨다면 맨 앞과 맨 뒤에 넣는 과정은 손쉽게 이해하실 수 있습니다. 연결리스트는 단순히 선을 연결하는 과정이니까요
맨 앞과 맨 뒤는 코드를 통해서 알아보겠습니다.
class Node:
def __init__(self, data):
self.data = data # 노드의 값
self.next = None # 다음 노드를 가리키는 정보
class LinkedList:
def __init__(self):
# 연결리스트를 처음 생성 시 아무것도 없으므로 다음과 같이 초기화 할 수 있다.
self.head = None
self.tail = None
self.count = 0
def append(self, value):
"""연결리스트 뒤에 추가하는 메소드"""
new_node = Node(value) # 공통 특징은 우선 새 노드를 생성한다는 것
if self.count == 0: # 연결리스트가 비었을 때
self.head = new_node # 새 노드가 head node가 된다.
self.tail = new_node # 새 노드가 tail node가 된다.
else: # 연결리스트가 안 비어있을 때
self.tail.next = new_node # tail node의 다음이 새 노드를 가리킨다
self.tail = new_node # 새 노드는 tail node가 된다
self.count += 1 # 노드가 추가 되었으니까 갯수를 하나 올린다.
def insert(self, index, value):
"""연결리스트의 원하는 위치에 삽입하는 메소드"""
new_node = Node(value)
if 0 <= index <= self.count: # 연결리스트의 원하는 인덱스 범위에 있나?
if index == 0: # 인덱스가 0이란 맨 앞에 넣고 싶다는 뜻
head_node = self.head # head를 잠시 저장
self.head = new_node # head 노드를 새 노드로 교체
self.head.next = head_node # head(신)의 다음을 아까 잠깐 저장한 head(구)를 가리킴
elif index == self.count: # 이 말은 만약 tail 노드라면?
self.tail.next = new_node # tail의 다음을 새 노드를 가리킴
self.tail = new_node # tail을 새 노드로 교체
else: # 나머지 경우는 일반적인 중간에 넣는 것임
i = self.head
for _ in range(index - 1):
i = i.next
prev_node = i # 삽입할 위치의 이전 노드
new_node.next = prev_node.next # 새 노드의 다음은 이전 노드의 다음을 연결해준다.
prev_node.next = new_node # 이전 노드의 다음은 새 노드를 연결한다.
self.count += 1 # 노드를 삽입했으니까 1 올림
else: # 범위에 없으면 인덱스를 잘못 입력했다고 출력해줄까?
print("인덱스를 잘못 입력했습니다.")
def __str__(self):
"""자동으로 출력해주는 메소드 사용법은 인스턴스를 출력시키면됩니다."""
i = self.head
result = ""
while True:
if i.next is None:
result += str(i.data)
break
else:
result += str(i.data) + " -> "
i = i.next
return result
# 테스트 코드
s = LinkedList()
for i in range(1, 11):
s.append(i)
print(s) # 생성한 인스턴스를 출력하면 __str__이 동작합니다.
# 중간에 넣기
s.insert(5, 777)
print(s)
# 맨 앞에 넣기
s.insert(0, "aaa")
print(s)
print(s.head.data) # head가 바뀌었나 확인
# 맨 뒤에 넣기
s.insert(12, "end")
print(s)
print(s.tail.data) # tail이 바뀌었나 확인이상으로 단순 연결리스트에서 원하는 곳에 삽입하는 과정이였습니다.
'프로그래밍 > 자료구조' 카테고리의 다른 글
| 파이썬으로 이중연결리스트를 만들어보자! (추가 연산, 탐색 연산) (0) | 2023.01.29 |
|---|---|
| 단순연결리스트로 스택 구현하기(Stack 자료구조, FILO : first in Last out) (2) | 2023.01.29 |
| 파이썬으로 연결리스트 만들기 4탄 : 단순 연결리스트 삭제연산 (맨 앞 노드 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제 방법) (0) | 2023.01.01 |
| 파이썬으로 연결리스트 만들기 2탄 : 단순 연결리스트 추가 연산 (연결리스트 자동 출력 만들기) (0) | 2022.12.04 |
| 파이썬으로 연결리스트 만들기 1탄(자료구조 / 단순 연결리스트 / 이중 연결리스트 / 추가 / 삽입 / 삭제 / 접근) (0) | 2022.12.04 |
댓글