데이터를 노드로 연결해 구성하는 연결 리스트(Linked List)
연결 리스트(Linked List)는 데이터 요소들이 노드(Node)라는 단위로 구성되어 서로 연결된 구조를 갖는 자료구조입니다.
각 노드는 데이터와 다음 노드를 가리키는 포인터(Pointer)로 이루어져 있습니다.
연결 리스트의 구조와 특성
연결 리스트는 다음과 같은 구조와 특성을 갖습니다.
노드(Node)
연결 리스트의 기본 단위입니다.
각 노드는 데이터와 하나 또는 두 개의 포인터를 포함하며, 포인터는 다음 노드(또는 경우에 따라 이전 노드)를 가리킵니다.
헤드(Head)
연결 리스트의 첫 번째 노드를 가리키는 포인터입니다.
연결 리스트의 시작점을 나타냅니다.
테일(Tail)
연결 리스트의 마지막 노드를 가리키는 포인터입니다.
테일 노드의 포인터는 일반적으로 None을 가리킵니다.
연결 리스트는 어떻게 구현할 수 있나요?
아래 코드는 파이썬으로 단순 연결 리스트(Singly Linked List)를 구현한 예제입니다.
파이썬 연결 리스트 구현 예시
class Node:
def __init__(self, data):
# 노드의 데이터
self.data = data
# 다음 노드를 가리키는 포인터
self.next = None
class LinkedList:
def __init__(self, data):
# 첫 번째 노드 생성
self.head = Node(data)
# 초기에는 헤드와 테일이 동일
self.tail = self.head
def append(self, data):
# 새 노드 생성 및 연결
node = Node(data)
# 테일 노드의 다음 노드로 새 노드를 연결
self.tail.next = node
# 새 노드를 테일로 지정
self.tail = node
def print_all(self):
# 연결 리스트 출력
node = self.head
# 노드를 순회하며 데이터 출력
while node:
print(node.data, end=" ")
node = node.next
print()
# 연결 리스트 생성
linked_list = LinkedList(5)
# 노드 추가
linked_list.append(12)
linked_list.append(7)
# 연결 리스트 출력
linked_list.print_all()
# 출력: 5 12 7
연결 리스트는 어떤 종류가 있나요?
연결 리스트는 노드가 연결되는 방식에 따라 다음과 같이 나뉩니다.
단일 연결 리스트 (Singly Linked List)
각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트입니다.
이중 연결 리스트 (Doubly Linked List)
각 노드가 이전 노드와 다음 노드를 모두 가리킵니다.
양방향 탐색이 가능하며, 삽입과 삭제가 더욱 효율적입니다.
원형 연결 리스트 (Circular Linked List)
마지막 노드가 첫 번째 노드를 가리키는 구조로, 리스트가 순환됩니다.
순환적 작업에 유용합니다.
연결 리스트와 배열의 비교
| 특성 | 연결 리스트 | 배열 |
|---|---|---|
| 메모리 할당 | 동적으로 메모리를 할당 | 고정 크기의 연속된 메모리 공간 사용 |
| 삽입/삭제 연산 | 특정 위치에서의 삽입/삭제가 빠름 | 특정 위치에서 삽입/삭제가 비효율적 |
| 임의 접근 | 순차적으로만 접근 가능 | 인덱스를 통한 즉시 접근 가능 |
연결 리스트는 메모리 관리와 삽입/삭제 연산이 중요한 경우 유리한 반면, 배열은 임의 접근과 데이터 처리 속도가 중요한 경우 적합합니다.
다음 내용이 궁금하다면?
코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!