👇🏻 시작하기 전 오늘의 짤
더 늦기 전에 연결리스트에 대해 더 알아보자.
2022.04.08 - [Python/[Data Structure] 자료구조] - [2] Linked List, 연결리스트 (1)
[2] Linked List, 연결리스트 (1)
자료구조 수업을 들을 때, 진짜 연결리스트가 너무 싫어서 오열한 적도 있다. 이해와 구현의 갭 차이가 너무 컸기 때문... 실습 때 집에 일찍 가고 싶어서 구글링으로 대충 복붙했다가 내 알고리
sennieworld.tistory.com
👆 저번 시간에 연결리스트로 만들어 준 18과 친구들은 잘 놀고 있었다. 그리고 그들은 오늘 올 새 친구에 설레 있었다.
새 친구 58이 도착했다. 그들은 어느때와 같이 환영인사로 기차놀이를 하려고 하는데 58은 꼭 28과 38 사이에 끼고 싶어했다. 만약 그러지 못한다면 바다에 빠져 죽을거라고 협박했다. 하지만 그들은 맨 뒤에 세우는 법 밖에 모를 뿐...
> 연결리스트 요소 삽입
28과 38 사이에 독불장군 58을 끼워놓는 거부터 오늘 이야기는 시작된다. 원리는 다음과 같다.
1. 58에게 18부터 차례로 인사하며 28을 찾으라고 한다.
2. 28의 꼬리를 잡고 있었던 38의 손을 잠시 야자수를 잡고 있으라고 한다.
3. 58이 28의 꼬리를 잡으면 야자수에 있던 손을 58의 꼬리를 잡게 한다.
이 이야기를 🖥에게 알려주는 방법은 다음과 같다.
def insert(self, insert_node, find_data):
node = self.head
find = True
while find:
if node.data == find_data:
find = False
else:
node = node.next
insert_node_next = node.next
node.next = insert_node
insert_node.next = insert_node_next
앞서 말했던 원리에 코드를 알맞게 덧붙여보겠다.
1. 58에게 18(self.head)부터 차례로 인사하며 28(find_data)을 찾으라고 한다. (while 반복문, 찾으면 find = False로 변함)
2. 28의 꼬리를 잡고 있던 38의 손(node.next)을 잠시 야자수(insert_node_next)를 잡고 있으라고 한다.
( insert_node_next = node.next )
3. 58(insert_node)이 28의 꼬리(node.next)를 잡으면( node.next = insert_node ),
야자수에 있던 손(insert_node_next)을 58의 꼬리(insert_node.next)를 잡게 한다.
( insert_node.next = node_insert_next )
😅 주저리 주저리 상세 설명
insert_node 사이에 끼고 싶은 독불장군
find_value 자리를 내어주어야 하는 두 값 중 앞에 있는 값
node = head부터 시작하는 건 이제는 기본이겠지? 하지만 새로운 변수 find가 나타났다.
find는 기차놀이 줄에서 find_data를 찾으면(node.data == find_data) False로 변하고 그 전까지는 True값을 유지하며 계속 다음 친구를 만나(node = node.next)게 해준다.
find_data를 찾으면 반복문을 빠져나오게 되고 node는 find_data를 가지고 있는 노드를 저장하게 된다.
find_data 뒤에 있던 노드를 insert_node_next에 저장한 다음 insert_node를 노드의 다음에 연결해주면 된다.
그 후 insert_node의 포인터에 insert_node_next를 연결함으로서 주소 설정을 새롭게 해준다.
메소드를 작성했으니 28과 38 사이에 58을 삽입(insert)한 후 결과를 확인해보자.
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class Linked_List:
# 초기화 메소드
def __init__(self):
self.head = None
# 노드 추가 메소드
def add(self, data):
if self.head == None:
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
# 노드 삽입 메소드
def insert(self, insert_node, find_data):
node = self.head
find = True
while find:
if node.data == find_data:
find = False
else:
node = node.next
insert_node_next = node.next
node.next = insert_node
insert_node.next = insert_node_next
# 노드 출력 메소드
def print_node(self):
node = self.head
while node:
print(node.data, end=' ')
node = node.next
LinkedList = Linked_List()
for data in range(1,5):
LinkedList.add(data * 10 + 8)
# 28 뒤에 58 삽입
LinkedList.insert(Node(58), 28)
# 연결리스트 출력
LinkedList.print_node()
# 출력 결과
18 28 58 38 48
58이 무사히 기차놀이에 합류했다. 하지만 38에게는 아무도 모르는 비밀이 하나 있었다. 바로 28을 짝사랑하고 있었던 것이다.
58에게 크게 상처받은 38은 기차놀이에서 빠져 집으로 보내달라고 한다.
38을 기차놀이에서 빼내서 안전하게 집에 보내주자. 또한 나머지 친구들은 다시 기차놀이를 즐길 수 있게 해주자.
> 연결리스트 요소 삭제 원리는 다음과 같다.
1. 18부터 시작해 기차놀이에 있는 38의 앞에 있는 58을 찾는다.
2. 38을 잠시 야자수에 가 있으라고 한다.
3. 58의 꼬리를 48에게 잡고 있으라고 한다.
4. 야자수에 있는 38을 집에 보내준다.
이 이야기를 🖥에게 알려주는 방법은 다음과 같다.
def delete(self, delete_data):
node = self.head
while node.next:
if node.next.data == delete_data:
palm_tree = node.next
node.next = node.next.next
del palm_tree
else:
node = node.next
마찬가지로, 원리에 코드 설명을 덧붙여 보겠다.
1. 18(self.head)부터 시작해 기차놀이에 있는 38(delete_data)의 앞에 있는 58(node)을 찾는다.
( node.next.data == delete_data , node.next.data 는 58 다음에 위치한 데이터이므로 38이 된다 )
2. 38(node.next)을 잠시 야자수(palm_tree)에 가 있으라고 한다. ( palm_tree = node.next )
3. 58의 꼬리(node.next)를 48(node.next.next)에게 잡고 있으라고 한다. ( node.next = node.next.next, node.next.next는 58 다음 다음 위치한 데이터이므로 48이 된다 )
4. 야자수에 있는 38(palm_tree)을 집에 보내준다. (del palm_tree, 삭제하기)
하지만, 여기서 한 가지 고려해야 할 것이 있다. 위의 원리 설명에는 기차놀이의 총 3명의 친구(삭제할 38, 앞에 있던 58과 뒤에 있던 48)가 등장한다. 우리가 이제까지 배운 연결리스트는 다음 원소를 가리키는 포인터는 존재하지만, 이전 원소를 가리키는 포인터는 존재하지 않는다. 그렇기 때문에 38을 삭제하고 싶더라도 58에 닿는 방법을 고려해야 하기에 58을 찾은 것이다. (다음 위치한 원소는 .next를 이용해 계속 닿을 수 있기 때문에)
만약에 head에 있는 18을 삭제하고 싶다면 해당 방법으로는 삭제가 안 될 것이다. 18은 맨 처음 원소이고 우리는 node.next부터 삭제할 원소를 찾기 시작하니깐 말이다. 그래서 조건문을 통해 head를 삭제하고 싶을 때의 예외처리를 해 주어야 한다.
def delete(self, delete_data):
if self.head.data == delete_data:
palm_tree = self.head
self.head = self.head.next
del palm_tree
else:
node = self.head
while node.next:
if node.next.data == delete_data:
palm_tree = node.next
node.next = node.next.next
del palm_tree
else:
node = node.next
이럴 경우 야자수에 head를 묶어두고 head를 head.next로 지정해준 후 삭제하면 된다.
이제 38을 집에 보내주고(삭제) 나머지 친구들을 출력해보자.
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class Linked_List:
# 초기화 메소드
def __init__(self):
self.head = None
# 노드 추가 메소드
def add(self, data):
if self.head == None:
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
# 노드 삽입 메소드
def insert(self, insert_node, find_data):
node = self.head
find = True
while find:
if node.data == find_data:
find = False
else:
node = node.next
insert_node_next = node.next
node.next = insert_node
insert_node.next = insert_node_next
# 노드 삭제 메소드
def delete(self, delete_data):
if self.head.data == delete_data:
palm_tree = self.head
self.head = self.head.next
del palm_tree
else:
node = self.head
while node.next:
if node.next.data == delete_data:
palm_tree = node.next
node.next = node.next.next
del palm_tree
else:
node = node.next
# 노드 출력 메소드
def print_node(self):
node = self.head
while node:
print(node.data, end=' ')
node = node.next
LinkedList = Linked_List()
for data in range(1,5):
LinkedList.add(data * 10 + 8)
LinkedList.insert(Node(58), 28)
LinkedList.delete(38)
LinkedList.print_node()
# 출력 결과
18 28 58 48
이렇게 연결리스트의 노드, 초기화, 추가, 삽입, 삭제, 출력에 대해 알아보았다.
다음 포스트에서는 연결리스트의 특징에 대해 다뤄보도록 하겠다.
'Python > [Data Structure] 자료구조' 카테고리의 다른 글
| [6] Queue, 큐 (0) | 2022.04.13 |
|---|---|
| [5] Stack, 스택 (0) | 2022.04.13 |
| [4] Linked_List, 연결리스트 (3) (0) | 2022.04.10 |
| [2] Linked List, 연결리스트 (1) (0) | 2022.04.08 |
| [1] 자료구조와 배열 (0) | 2022.04.06 |