지난 시간에는 기본 자료 구조인 배열에 대해 배웠습니다.
이번 시간에는 또 다른 자료 구조인 링크드 리스트의 개념과 링크드 리스트 만드는 방법, 그리고 추가 연산에 대해 함께 알아보겠습니다.
🤼♀️ 링크드 리스트
링크드 리스트(Linked List), 우리말로는 연결 리스트라는 자료 구조는 배열처럼 데이터를 순서대로 저장해 주는 자료 구조입니다. 또한, 동적 배열처럼 계속해서 새로운 요소를 추가할 수 있습니다.
그런데 링크드 리스트는 구현 방식이 동적 배열보다 조금 복잡한데요. 그래서 이걸 왜 배우나 싶은 생각이 들 수도 있습니다만😂😂😂 상황에 따라 동적 배열보다 더 효율적일 때가 있기 때문에 반드시 알아두어야 합니다.
그럼 링크드 리스트가 어떻게 동작하는지 간단히 알아보겠습니다. 링크드 리스트는 노드(Node)라는 단위의 데이터를 저장하고 데이터가 저장된 각 노드들을 순서대로 연결시켜서 만든 구조입니다.
노드가 생소하다면 일단 그냥 어떤 박스라고 생각해 보세요. 각 박스에는 이름이 있고 박스 하나당 하나의 칸막이가 있어 총 두 개의 칸을 가지고 있는데요. 그 중, 왼쪽 칸에는 저장하고 싶은 값을 넣어주면 됩니다.
노드가 4개 있다고 가정하고 각 노드에는 A, B, C, D라는 이름을 붙여줍니다. 저장하고 싶은 데이터는 각각 2,4,6,8인데요. 그럼 각 박스의 왼쪽 칸에 하나씩 수를 넣어주면 됩니다. 그런데 이 박스들은 순서대로 나열되어 있는 것이 아니라 이곳저곳에 퍼져 있습니다. 따라서, 그 안의 수들도 무작위로 나열되어 있죠.
그럼 이 수들을 순서대로 나열하려면 어떻게 해야 할까요? 앞서 각 박스들에 이름을 붙여줬었는데요. 박스의 오른쪽 칸에 연결하고 싶은 수를 가진 다른 박스의 이름을 적어주면 됩니다.
예를 들어, A가 2, B가 6, C가 8, D가 4라면 A 박스의 오른쪽 칸에 D를 넣어주고 D의 오른쪽 칸에는 B를, B의 오른쪽 칸에는 C를 넣어주면 됩니다. 8 뒤의 수는 없으므로 C 박스의 오른쪽 칸은 비워두면 됩니다.
자, 그럼 다시 A 박스부터 봅시다. A 박스의 오른쪽 칸을 보면 다음 박스가 어떤 건지 알 수 있겠죠? 다음 박스는 D이네요. D의 오른쪽 칸은 B이니 다음은 B입니다. 마지막으로 B의 오른쪽 칸에는 C가 있으므로 B 다음은 C입니다. C의 마지막 칸은 비워져 있으므로 8이 마지막 수라는 것을 알 수 있습니다.
정리하자면, 박스 즉, 노드들은 순서 없이 아무렇게나 흩어져 있지만 노드의 오른쪽 칸에 다음 노드의 이름을 저장하여 다음 노드와 연결 합니다. 이렇게 하면 노드들을 순서대로 연결할 수 있습니다. 이러한 자료 구조를 연결 리스트라고 부릅니다.
🤼♀️ 링크드 리스트 - 프로그래밍
그럼 링크드 리스트를 실제 코드로 어떻게 구현할 수 있을까요? 각 박스 즉, 노드는 하나의 객체로 표현됩니다.
각 노드 객체에는 두 가지 속성이 있는데요. 하나는 data라는 속성이고 다른 하나는 next라는 속성입니다. data에는 우리가 저장하고 싶은 정보를 넣어줍니다. next에는 다음 노드에 대한 레퍼런스가 담깁니다. 앞서 박스의 왼쪽 칸에 해당하는 부분이 바로 data이고 오른쪽 칸에 해당하는 부분이 바로 next입니다. next에는 이름 대신 레퍼런스가 들어간다는 차이가 있죠.
예를 들어, n1이라는 노드 객체와 n2라는 노드 객체가 있다고 가정해봅시다. 만약 n1의 다음 노드를 n2로 설정해 주고 싶다면 다음과 같이 코드를 작성하면 됩니다.
n1.next = n2이렇게 하면 n1.next가 n2를 가리키고 있으므로 n1.next는 n2에 대한 레퍼런스라고 할 수 있습니다.
처음 노드 객체들은 메모리에 연속적으로 저장되어 있지 않고 각자 알아서 어딘가에 흩어져 있습니다. 따라서, 서로 아무런 관련이 없죠.
하지만 각 노드에 다음 노드에 대한 레퍼런스가 있다면, 노드 객체의 next 속성을 통해 다음 노드가 어디 저장되어 있는지 알 수 있습니다. 사실 가장 첫 번째 노드 객체의 메모리 주소만 알아도 나머지 노드들은 next를 통해 타고타고 가서 접근할 수 있습니다. 이러한 시작 노드 객체를 head라고 합니다.
이렇게 head 노드만 있으면 흩어져 있는 다른 노드들을 연결하여 배열과 동적 배열처럼 데이터를 원하는 순서대로 저장할 수 있습니다.
🤼♀️ 노드 클래스 만들기
노드 객체를 코드로 구현해봅시다. 우선, 노드 객체를 만드려면 노드 클래스를 정의해야 합니다.
class Node:
"""링크드 리스트의 노드 클래스"""
def __init__(self, data):클래스를 정의한 후, 가장 먼저 해야할 일은 객체를 생성할 때 호출되는 이닛 메소드를 정의하는 것입니다. 첫번째 파라미터에는 self가 들어가야겠죠? 다음으로 노드를 생성할 때, 이 노드가 저장할 정보를 받아올 파라미터가 필요합니다. 이 파라미터를 data라 하겠습니다.
이제 이닛 메소드 안에 인스턴스 변수들의 초깃값을 설정해줘야 합니다. 노드는 두 개의 속성이 있다고 했죠?
self.data = data # 노드가 저장하는 데이터첫번째는 저장할 데이터를 담는 속성 data입니다. 여기에는 파라미터로 받은 data의 값을 넣으면 됩니다.
self.next = None # 다음 노드에 대한 레퍼런스다음으로 두번째 속성은 다음 노드에 대한 레퍼런스 next입니다. 객체를 처음 생성할 때는 일단 비워두기로 하겠습니다.
이렇게 노드 클래스가 완성되었습니다. 이제 이 클래스를 활용하여 여러 개의 노드 인스턴스를 만들어보겠습니다. 링크드 리스트에 2,4,6,8을 저장한다고 가정해 봅시다. 그럼 각각의 값을 담는 노드 인스턴스를 만들면 됩니다.
Node(2)이렇게 하면 2를 담는 노드 인스턴스가 생성되는데요. 인스턴스가 생성되는 순간, 2라는 수가 클래스 속 이닛 메서드의 파라미터로 들어갑니다. 그 다음, self.data에 저장되죠. 나머지 인스턴스도 만들어보겠습니다.
Node(4)
Node(6)
Node(8)이제 해야할 일은 각 인스턴스를 변수에 지정해주는 것입니다. 링크드 리스트의 첫 번째 노드는 헤드 노드라고 했었죠? 그러니까 첫번째 노드 인스턴스는 head_node라는 변수에 지정해줍니다.
head_node = Node(2)나머지는 간단한 변수명을 지정해주겠습니다.
node1 = Node(4)
node2 = Node(6)
node3 = Node(8)이때, 마지막 노드 또한 별도의 이름이 있는데요. 꼬리 부분에 있기 때문에 테일(tail) 노드라고 부릅니다. 따라서, node3을 tail_node라는 이름으로 바꾸어 저장하겠습니다.
tail_node = Node(8)🤼♀️ 간단한 링크드 리스트 만들기
앞서 노드 인스턴스 네 개를 만들었고 각각 2, 4, 6, 8을 저장했습니다. 현재 이 노드들은 각자 흩어져서 자기만의 공간에 있습니다. 그렇기 때문에 서로 아무런 관계가 없죠. 이 노드들을 연결시켜 보겠습니다.
head_node의 다음 노드는 node1로 설정해야겠죠? 그럼 head_node.next 속성에 node1을 넣어 주기만 하면 됩니다.
head_node.next = node1이런 식으로 하나씩 연결하면 되는데요. 나머지도 해보겠습니다.
node1.next = node2
node2.next = tail_nodetail 노드는 마지막 노드이므로 next 속성을 비워두면 됩니다. 이렇게 하면 노드들이 순서대로 다 연결됩니다. 아주 간단하죠? 정말 서로 연결 되었는지 한 번 확인해봅시다.
헤드부터 시작해서 노드에 저장된 데이터를 하나씩 출력해보겠습니다.
i = head_node
while i is not None:
print(i.data)
i = i.nexti는 반복문으로 리스트를 돌 때 필요한 인덱스입니다. 첫 i의 값은 첫번째 노드인 헤드 노드로 설정했습니다.
위 반복문은 반복적으로 i에 있는 값(i.data)을 출력합니다. 처음에는 i가 head_node이므로 2가 출력되겠죠? 다음으로 i에 next 속성이 가리키고 있는 새로운 값을 넣어줍니다. 앞서, head_node의 다음 노드로 node1을 설정했으므로 i는 node1이 됩니다.
다시 node1에 있는 값 4가 출력되고 i는 node2가 됩니다. 이런 식으로 데이터가 하나씩 출력되면서 i가 다음 노드로 바뀌는 과정이 반복되는데요. while문의 조건 부분을 보면, i가 None이 아닌 동안 반복한다고 되어 있습니다. 마지막 tail_node는 next 속성이 None이기 때문에 tail_node 다음에는 i가 None으로 바뀌므로 반복문이 종료됩니다.
2
4
6
8결과를 보면, 우리가 원하는대로 2, 4, 6, 8이 순서대로 출력됩니다.
다시 한 번 강조 드리지만 노드를 처음 선언할 당시에는 메모리의 이곳저곳에 흩어져 저장되기 때문에 각 노드끼리 아무런 관련이 없었습니다. 따라서, 이 상태로 실행하면 순서와 상관 없이 결과가 출력됩니다. 노드의 next 속성에 다음 노드를 지정해주고 나서야 비로소 두 노드가 연결되어 우리가 원하는 결과가 나오게 됩니다.
🤼♀️ 링크드 리스트 추가 연산
이번에는 링크드 리스트를 체계적으로 관리하기 위해서 링크드 리스트 클래스를 만들어 보겠습니다.
class LinkedList:
"""링크드 리스트 클래스"""이닛 메소드부터 선언하겠습니다.
def __init__(self):
self.head = None
self.tail = None해당 클래스의 이닛 메소드에는 self 외에 추가적인 파라미터가 없습니다. 링크드 리스트의 속성은 두 가지만 추가했습니다. 하나는 링크드 리스트의 가장 앞에 있는 헤드 노드, 다른 하나는 링크드 리스트의 가장 뒤에 있는 테일 노드입니다. 이 인스턴스 변수들의 값은 None으로 설정하겠습니다.
다음으로, 링크드 리스트 맨 끝에 노드 정보를 추가하는 메서드 append를 선언해봅시다. 이와 같은 과정을 추가 연산이라고 했었죠?
def append(self, data):
"""링크드 리스트 추가 연산 메소드"""
new_node = Node(data)append는 인스턴스 메서드이므로 첫 파라미터로 self를 받고 추가하려는 정보도 받아야 하기 때문에 data라는 파라미터도 넣어주겠습니다.
다음으로, 링크드 리스트에 정보를 추가하기 위해서 그 정보를 담는 노드(Node(data))를 만들고 new_node라는 변수에 넣어줬습니다. 이제 이 변수를 다른 노드들과 연결시키면 되는데요.
추가 연산은 두 가지 경우로 나누어 진행할 수 있습니다. 하나는 링크드 리스트가 비어 있을 때, 다른 하나는 비어있지 않을 때입니다. 첫번째 경우부터 봅시다.
if self.head is None: # 링크드 리스트가 빈 경우
self.head = new_node
self.tail = new_node링크드 리스트가 비어 있다는 건 헤드 속성도 비어있다는 뜻입니다. 그럼 위와 같이 self.head가 None인 경우에 대해서 처리하면 되는데요. 이때, 새로 추가한 노드가 유일한 노드이므로 이 노드가 링크드 리스트의 머리이면서 꼬리이기도 합니다. 따라서, 헤드와 테일을 모두 이 새로운 노드로 설정한 것이죠.
이제 두번째 경우를 보겠습니다. 먼저, 2, 4, 6이 저장되어 있는 링크드 리스트 하나를 가정해봅시다. 이때, 2가 담긴 노드가 헤드 노드이고 6이 담긴 노드가 테일 노드입니다. 이 링크드 리스트에 11을 추가하려 하는데요. 이를 위해 11이 담긴 new 노드를 만들었습니다.
여기서 해야 할 일은 두 가지인데요. 그 중 첫번째는 기존 테일 노드와 new 노드를 연결시키는 일입니다. 그러기 위해서는 self.tail의 다음 노드로 new_node를 설정하면 됩니다. self.tail.next = new_node 이런 식으로 말이죠. 이때, self.tail이 아닌 self.tail.next에 new_node를 넣어야 한다는 사실을 잊지 마세요!
두번째는 new_node가 링크드 리스트의 가장 끝에 추가되므로 new_node를 테일로 설정해주는 일입니다. 코드로는 self.tail = new_node 이렇게 구현해주면 됩니다.
두 과정을 코드로 정리하면 다음과 같습니다.
else: # 링크드 리스트가 비어있지 않은 경우
self.tail.next = new_node
self.tail = new_node이렇게 링크드 리스트 클래스를 만들고 추가 연산까지 정의했습니다. 이 클래스가 잘 동작하는지 확인해보겠습니다.
우선, 링크드 리스트 인스턴스를 하나 생성해 봅시다.
my_list = LinkedList()다음으로 데이터 2, 4, 6, 8을 추가해주겠습니다.
my_list.append(2)
my_list.append(4)
my_list.append(6)
my_list.append(8)지금까지 한 과정을 요약하자면, 링크드 리스트 하나를 생성해서 my_list에 저장하고 그 안에 2, 4, 6, 8을 추가했습니다. 그러니까 my_list에는 네 개의 노드가 있는데 그 노드들에는 각각 2, 4, 6, 8이 저장되어 있는 거죠. 이 값들이 잘 저장되어 있는지 확인해보겠습니다.
앞서, 노드 데이터를 순서대로 출력하는 코드를 배웠습니다. 다시 한 번, 사용해보겠습니다.
i = head_node
while i is not None:
print(i.data)
i = i.next2
4
6
8잘 저장되어 있네요 :)
🤼♀️ 링크드 리스트 str 메소드
링크드 리스트를 클래스로 만들었으니 이번에는 링크드 리스트를 문자열로 표현해주는 던더 str 메소드를 정의해봅시다. 기억이 안 나시는 분들을 위해 설명 드리자면, 던더 str은 링크드 리스트의 내용을 사람들이 이해할 수 있는 문자열로 리턴해주는 메소드입니다.
def __str__(self):
"""링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
res_str = '|'
i = self.head
while i is not None:
res_str += f" {i.data} |"
i = i.next
return res_str던더 str 메소드는 문자열을 리턴하므로 리턴시킬 res_str 변수를 빈 문자열로 정의합니다. 그런 다음, 링크드 리스트 내부를 하나씩 돌면 됩니다.
먼저, i 변수를 링크드 리스트의 헤드를 가리키게 하고 i 변수가 None이 아닐 때까지 즉, 링크드 리스트의 처음부터 끝 노드까지 i 변수의 data를 res_str 변수에 추가해줍니다. 다음으로, i 변수의 next 속성을 이용해서 while문을 돌 때마다 다음 노드로 이동합니다. 마지막으로 링크드 리스트를 다 돈 후에는 res_str 변수를 리턴하면 됩니다.
코드가 제대로 작성되었는지 확인해보겠습니다.
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(3)
linked_list.append(5)
linked_list.append(7)print(linked_list)| 1 | 3 | 5 | 7 |잘 출력되네요!
앞으로 링크드 리스트에 저장되어 있는 데이터를 확인하기 위해 던더 str 메소드를 사용하겠습니다.
이번 시간에는 노드와 노드 간 연결을 통해 순서대로 데이터를 나열하는 링크드 리스트의 개념과 그 동작 원리, 구현 방법, 그리고 추가 연산까지 배웠습니다. 노드라는 개념이 아직 생소하시죠? 아주 간단하게 값과 다음 노드 주소로 이루어졌다고 생각해보시면 될 것 같습니다.
중간에 클래스 개념이 등장했는데 이 부분이 헷갈리시다면 객체 지향 프로그래밍 부분을 복습해보시길 권장해드립니다.
다음 시간에는 추가 연산 외에 링크드 리스트의 다른 연산들에 대해 함께 배워보겠습니다.
* 이 자료는 CODEIT의 '자료 구조' 강의를 기반으로 작성되었습니다.