4. 연결 리스트 (linked list)

1. 연결리스트 개념

 

• 원소들이 메모리에서 임의의 위치에 배치되어 있음
• 한 원소는 다음 원소를 가리키는 link를 가지고 있음 (포인터 기반)

 

 

2. 배열과 연결 리스트 비교

 

• 배열 : 원소들이 메모리에서 일정한 간격으로 나열되어 있음
• 연결 리스트 : 원소들이 메모리에 임의의 위치에 배치되어 있음

	배열	연결 리스트
메모리 공간	연속된 메모리 주소	이산된 메모리 주소
공간 할당	정적 할당 / 동적 할당	동적 할당
접근 경로	첫 번째 원소의 주소	첫 번째 원소의 주소
접근 방법	인덱스	포인터
접근 방식	Random access	Sequential access

 

3. 연결 리스트 정의

 

• node = data + link
• node는 메모리의 임의의 위치에 배치됨
• 각 node는 다음 node를 가리키는 link를 포함하고 있음

 

  *단일 연결 리스트

 

   - 각 node는 하나의 link를 가짐

   - 가장 널리 사용되는 구현 방법

   

  *이중 연결 리스트

   

   - 각 node는 두 개의 link를 가짐

 

 

 

4. 연결 리스트 연산

 

4-1. 검색

 

• 찾는 원소 (key element)를 저장하고 있는 노드의 포인터를 리턴
• 선형 탐색만 가능

    1. hnode에서 검색을 시작함

    2. key element를 가진 node를 찾음

 

   시간 복잡도 : O(n)

 

4-2. 추가

 

• 추가할 데이터를 저장하는 새로운 노드를 연결 리스트에 삽입하는 연산

 

    1. 데이터를 추가할 적절한 위치를 결정 (추가할 데이터보다 작은 원소들 중에 가장 큰 원소)

    2. 데이터를 저장할 새로운 노드를 생성

    3. 새로운 노드가 연결 리스트에 포함되도록 링크를 갱신

 

   시간 복잡도 : O(n)

 

4-3. 제거

 

• 리스트로부터 원하는 원소의 연결을 해제하여 리스트에서 그 원소를 삭제하는 연산

    1. 제거할 원소를 찾음

    2. 링크를 갱신해서 제거할 원소를 리스트에서 분리

    3. 제거된 노드의 메모리를 free

 

   시간 복잡도 : O(n)

 

 

 

5. 리스트 정리 (성능)

 

Type	연산
	검색(search)		추가(insert)	제거 (delete)
배열 (array)	선형 검색(linear search)	이진 검색(binary search)	O(n)	O(n)
	O(n)	O(logn)
연결 리스트(linked list)	선형 검색(linear search)		O(n)	O(n)
	O(n)