자료구조 수업을 들을 때, 진짜 연결리스트가 너무 싫어서 오열한 적도 있다. 이해와 구현의 갭 차이가 너무 컸기 때문...
실습 때 집에 일찍 가고 싶어서 구글링으로 대충 복붙했다가 내 알고리즘, 자료구조 인생은 망했다지...
혹시나 코드 긁을 사람이라면 당장 멈춰 진심 인생 조진다.
배열의 치명적인 단점 중 하나는 '배열 크기 변경 불가'이다.
연결리스트는 이를 해결하고자 나온 개념인데 어떻게 해결했는지 스스로 제대로 아는 것이 나의 목표이다.
연결리스트( Linked List )를 직역해보면 '연결된 리스트'이다. 뭐가? 뭐가 연결되어 있을까.
바로 첫번째 알아야 할 개념인 노드(Node)가 그 '뭐'이다. 정말 머같다.
노드(Node)는 데이터(data)와 포인터(pointer)로 이루어져 있다.
데이터는 '값'이고 포인터는 '무엇인가를 가리키는 것'이다. 포인터는 그럼 무엇을 가리키고 있는가.
포인터는 다음 노드를 가리키고(이 때문에 next라는 변수명으로 사용된다) 노드 사이의 연결을 담당한다.
포인터가 계속 다음 노드를 가리키다 보면 연결되어 버렸고 결국 우리는 연결리스트를 봐버렸다.
연결리스트(Linked List)는 (데이터와 다음 노드를 가리키고 있는 포인터로 이루어진) 노드가 연결된 리스트이다.
연결리스트에도 맨 앞 노드(a[0])와 맨 뒤 노드(a[n-1])가 존재할 텐데 어떻게 알 수 있을까?
그들은 간지 나는 이름을 가지고 있다. 맨 앞은 head, 맨 뒤는 tail이라고 부른다. 정말 원초적이다.
head는 맨 앞에 있는 노드이기 때문에 연결리스트를 생성하고 싶은 마음가짐만 있다면 언제나 존재하는 노드이다.
head에 계속해서 노드들을 포인터로 이어 붙이다 보면 어느 순간 이 정도면 되겠다 하고 끝내고 싶은 순간이 있을 것이다.
그 순간 tail로 연결리스트를 마무리 지어야 하는데 그 방법은 매우 단순하고 역시나 원초적이다.
tail의 포인터가 아무것도 안 가리키면(다음 노드가 없는 상태) 된다. 이 '없는 상태'를 NULL이라고 하고 컴퓨터한테 NULL이라고 알려주면 잘 알아듣는다.
어느 정도 개념은 알아들었으니 이제 구.현.을 해보자. 뇌에 있는 내용을 손가락을 가져와서 알을 낳는 느낌이랄까.
일단 노드를 만들어야 한다. 노드를 만들기 위해서는 노드를 찍어낼 수 있는 틀을 만들어야 하는데 파이썬에서는 class로 구현한다.
# 노드 클래스
class Node:
def __init__(self, data, next = None):
self.data = data # 데이터
self.next = next # 다음 노드를 가리키는 포인터
💎 __init__ 에 대하여
__init__이란 데이터의 초기화를 위한 메소드로 객체를 생성할 때 정보의 추가 기재를 간단히 한다고 생각하면 된다.
✓ 특징
∙ 인스턴스(instance, 클래스를 호출하는 것, 인스턴스 = 클래스 ())를 할 때 반드시 처음에 호출되는 특수한 메소드이다.
∙ __init__()은 반드시 첫 번째 인수로 self를 지정해야 하고 클래스를 생성/호출할 때의 넘기는 변수는 __init__메소드의 2번째부터 작성하면 된다.
노드를 틀에서 찍어내는 법(노드 생성)은 다음과 같다.
# data = 18인 노드
node1 = Node(18)
방금 찍어낸 따끈따끈한 노드의 값을 확인해보자.
포인터에 값이 None이므로 이 노드는 지금 무인도에 혼자 뚝 떨어진 상태이다. 기차놀이라도 할 수 있게 친구를 만들고 기차에 태워보자.
노드를 연결하고 값을 확인해보자.
# 이미 만든 node1 대장으로 승진
head = node1
# 친구 1, data=28
node2 = Node(28)
# 대장과 친구 1의 연결고리는 포인터(next)
node1.next = node2
# 출력 확인
print(node1.data, node1.next)
print(node1.next.data)
print(node2.data, node2.next)
다음의 출력 결과에서 2가지를 알 수 있다.
1. node1.next.data의 값(28)과 node2.data의 값(28)이 같다는 것은 성공적으로 연결이 되었다는 것
2. 알 수 없는 출력문을 발견했다는 것
1번은 모두가 무슨 말인지 알 테니 2번을 살펴보자.
<__main__.Node object at 0x107307f70>
해석해보면 "__main__에 있는 Node 클래스의 object가 0x107307f70에 있어~" 이런 말이고 결론은 node1.next(node1의 다음에 있는 node2)의 object id가 0x107307f70라는 말이다. 후훗(이런 거 해석할 때마다 오는 희열감에 취해버려...)
파일을 실행시킬 때마다 object id가 바뀌는 이유는 컴파일할 때마다 다른 곳(메모리)에 node1을 만들고 있기 때문이다.
# object id 출력해서 비교해보기
print(node1.next, hex(id(node2)))
# 출력 결과
<__main__.Node object at 0x100a4f160> 0x100a4f160
출력 결과를 비교해보면 같은 object id가 출력됨을 알 수 있다.
💎 hex()와 id()에 대해서
hex() : 정수를 16진수로 바꿔주는 파이썬 내장 함수
id(object) : object의 고유 id(메모리 주소)를 정수로 반환해주는 함수
이렇게 해서 친구들을 만들어주다가 친구들이 무인도를 다 점령할 만큼 많아지면 곤란해지니깐 아쉽게도 마지막 친구를 만들어주자.
기차놀이의 마지막 친구를 추가하기 (Node에 tail을 추가하기)
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
def add(data):
node = head
while node.next:
node = node.next
node.next = Node(data)
node1 = Node(18)
head = node1
# node2 = Node(28)
# node1.next = node2
add(28)
오우 갑자기 코드가 길어졌다. add라는 아주 쉬운 함수가 추가되었기 때문인데 겁먹지 않아도 된다. 사실 좀 겁먹음.
def add(data):
node = head
while node.next:
node = node.next
node.next = Node(data)
앞서 연결리스트의 등장 배경이 배열의 단점을 해결하기 위해서라고 했다. 사실 배열이었다면 배열의 크기(n)를 주고 arr [n-1]=28 이렇게 쉽게 추가하면 되지만 연결리스트는 그렇게 사는 걸 허락하지 않는다.
무인도 있던 18 친구를 기억하는가. 우리는 친구를 몇 명인지 정해놓지 않고 친구를 만들어주었다. 한 마디로, 기차놀이의 길이를 모른다는 말이다. 그래서 새 친구가 온다면 head(node1, 무인도에 첫 정착인)부터 다음 친구들을 다 인사시켜 준 다음, 맨 뒤에 세워야 한다.
이것을 코드로 작성해보면,
node=head를 통해 맨 처음 친구를 인사시켜 준다.
node.next가 존재하는 동안(다음 친구가 있을 동안) 친구들과 인사를 하면서 새 친구는 기차의 끝으로 향한다.
그러다 node.next가 없다면(친구와의 환영 인사 종료), 마음 편하게 그 자리에 새 친구(data)를 위치시켜주면 된다.
# node2 = Node(28)
# node1.next = node2
add(28)
# 결과 출력
print(node1.data, node1.next.data)
# 결과
18 28
새 친구가 온다면 만들어 놓은 add() 함수를 호출하면 된다. 주석 처리해 놓은 위의 두 줄과 같은 의미가 된다. 결과를 출력해 보았을 때 기존 친구(18) 뒤에 새 친구(28)가 잘 위치했다는 것을 알 수 있다.
여기까지 잘 왔다면 스스로 연습을 해보자.
[문제] 데이터가 2, 4, 6, 8, 10인 노드 리스트를 만들고 출력하라.
👇🏻 정답 확인
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
def add(data):
node = head
while node.next:
node = node.next
node.next = Node(data)
def print_node():
node = head
while node:
print(node.data, end=' ')
node = node.next
node1 = Node(2)
head = node1
add(4)
add(6)
add(8)
add(10)
print_node()print_node() 함수는 add() 함수에 print문만 추가한 노드 출력 함수이다. 하지만, add는 추가를 할 공간을 찾기 위해 node.next가 존재하는 동안의 조건을 가지고 있고 print는 node가 존재하는 동안의 조건을 가지고 있다.
이제까지 노드를 찍어내는 틀을 만들어 노드를 찍어내고 연결하고 마무리 짓는 방법을 공부했다.
이제는 연결리스트를 찍어내는 틀을 만들고 연결리스트를 찍어내 보자.
# 노드 클래스
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
# 연결리스트 클래스
class Linked_List:
def __init__(self):
self.head = None
클래스를 이용해 연결리스트 틀을 만들었고 연결리스트(객체)를 생성할 때 가장 첫번째로 불러드릴 메소드를 작성했다. 연결리스트의 head는 아직 값을 가지고 있지 않도록 None으로 설정하였다.
앞서 노드를 생성(추가)하는 방법(add)을 알아보았는데 이를 연결리스트 안의 메소드로 작성해보자
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)
add 메소드에서 전과는 조금 달라진 것은 조건문이 포함되어 있다는 것이다. else에 해당하는 것은 기존과 동일하다.
if 조건문의 의미는 "만약 head가 None으로 되어 있다면"이다. 앞서 node1을 생성하고 head=node1으로 head를 지정해 주었지만 연결리스트를 만들 때 head가 None으로 되어 존재하지 않는다. 따라서, head가 없을 경우 추가할 데이터를 head로 만들어주는 것이다.
만약 조건문이 없다면 node=self.head에서 head가 존재하지 않기 때문에 오류가 난다.
마지막으로 연결리스트를 프린트하는 메소드도 클래스 안에 작성하고 연결리스트 생성 결과를 출력해보자.
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 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.print_node()
# 출력 결과
18 28 38 48
오늘은 여기서 끝 !
'Python > [Data Structure] 자료구조' 카테고리의 다른 글
| [6] Queue, 큐 (0) | 2022.04.13 |
|---|---|
| [5] Stack, 스택 (0) | 2022.04.13 |
| [4] Linked_List, 연결리스트 (3) (0) | 2022.04.10 |
| [3] Linked List, 연결리스트(2) (0) | 2022.04.09 |
| [1] 자료구조와 배열 (0) | 2022.04.06 |