[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
• 배열의 고정 크기의 단점을 보완하기 위해 만들어짐
• 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 연결 필요

 

연결 리스트 표현

• Head는 리스트의 처음을 나타냄
• 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성
• 각 노드는 Next 포인터를 사용해 다음 노드와 연결
• 마지막 노드는 null을 가리켜 리스트의 끝을 나타냄

 

연결 리스트 종류

1. 단일 연결 리스트

• 각 노드당 한 개의 포인터르 가지고 있음
• 포인터는 다음 노드의 위치를 가리킴

2. 이중 연결 리스트

• 각 노드당 두 개의 포인터를 가지고 있음
• 포인터는 각각 이전 노드와 다음노드의 위치를 가리킴

3. 원형 연결 리스트

• 단일 연결 리스트에서 마지막 노드(테일)의 포인터가 헤더를 가리킴

 

연결 리스트 삽입, 삭제

• 2와 4 사이에 3을 삽입
• 2에서 4를 가리키던 포인터의 연결을 해제하고, 2는 3을 3은 4를 가리키도록 포인터 연결

 

• 4를 삭제
• 2에서 4를 가리키던 포인터의 연결을 해제하고, 2에서 5를 가리키도록 포인터 연결

 

연결 리스트의 시간 복잡도

operation	time
시작 위치에 대한 삽입/삭제	Θ(1)
마지막 위치에 대한 삽입/삭제	Θ(1): 마지막 요소 위치를 아는 경우 Θ(n): 마지막 요소 위치를 모르는 경우
중간 위치에 대한 삽입/삭제	search time + Θ(1)
인덱싱	Θ(n)
공간 낭비	Θ(n)

 

연결 리스트의 특징

• 선형적 데이터 자료구조
• 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 순차적으로 탐색만 가능
• 삽입 삭제가 배열에 비해 빠르고 쉬움
• 검색이 비효율적, 포인터로 인해 추가 저장공간 필요

연결 리스트의 장점

• 크기가 가변적
• 삽입 삭제가 쉬움

연결 리스트의 단점

• 요소에 접근하기 위해서는 첫 번째 노드부터 순차적 접근만 가능
• 포인터를 위한 추가 메모리 공간 필요