링크드 리스트 (Linked List)
1. 링크드 리스트 (Linked List) 구조
링크드 리스트(Linked List)란 연결 리스트라 불리기도 하는 자료구조이다. 배열은 순차적으로 연결된 공간에 데이터를 나열하는 구조인 반면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다. (파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.)
링크드 리스트의 기본 구조와 용어
- 노드(Node): 데이터 저장 단위 (데이터값, 포인터)로 구성
- 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
일반적인 링크드 리스트의 형태
위 그림에서처럼, 한 노드가 두 칸이 있다고 할 때, 하나는 저장된 데이터값을 넣고, 다른 하나는 다음 노드를 가리키는 포인터로 이해하면 된다.
2. 링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)
| 장점 | - 미리 데이터 공간을 할당하지 않아도 됨 (배열은 미리 데이터 공간을 할당해야 한다는 점에서 대조적) |
| 단점 | - 연결을 위한 별도 데이터 공간(포인터를 위한 별도 공간)이 필요해서 저장 공간 효율이 높지 않음 - 연결 정보를 찾는 시간이 필요하기 때문에 접근 속도 느림 - 중간 데이터 삭제시, 앞뒤 데이터 연결 재구성해야 하는 부가적인 작업 필요 |
3. 링크드 리스트 구현 (파이썬)
보통 파이썬으로 링크드 리스트를 구현할 때에, 파이썬 클래스를 활용한다.
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
여기서, Node와 Node를 연결할 때에는 포인터를 활용해서 이렇게 표현할 수 있다.
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1
node1의 next가 node2라고 연결함으로써 node1의 포인터가 가리키는 곳이 node2라고 설정하는 것이다. head란 해당 링크드 리스트의 첫 번째 노드를 것을 의미한다.
링크드 리스트로 데이터를 추가하는 함수(맨 마지막에 추가하는 것)를 만들어보면,
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def add(data):
node = head
while node.next: # node.next가 있을 때
node = node.next # 하나씩 다음 노드로 이동
node.next = Node(data) # 마지막에 Node(data) 추가로 이어 붙이기
위의 코드처럼 만들어진다. 우선 node에 head 값을 넣고, while문을 돌려서 node.next가 있는 경우 계속 node = node.next로 하나씩 뒤로 간다. 그리고 마지막에 next가 없는 node의 node.next에 추가하고자 하는 Node(data) 값을 추가하는 것이다.
이렇게 맨 뒤에 노드를 추가하는 함수까지 만들었으니, 실제로 링크드 리스트를 생성하고 출력해보면,
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# 첫 번째 노드 생성 및 head에 첫 번째 노드 값 담기
node1 = Node(1)
head = node1
def add(data):
node = head
while node.next:
node = node.next
node.next = Node(data)
# 첫 번째 노드에 2~9의 노드 추가하기
for index in range(2, 10):
add(index)
# 출력
node = head
while node.next:
print(node.data)
node = node.next
print(node.data)
이렇게 되고, 출력값은 1, 2, 3, ..., 9로 정상적으로 나온다.
[참고문헌]
패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료