자료구조 13강 - 단일 연결 리스트

단일 연결 리스트(with head node)

 

단일 연결 리스트 생성(create)

원소가 없는 연결 리스트를 생성

 

단일 연결 리스트 검색(search)

찾는 원소(key element)를 저장하고 있는 노드의 포인터를 리턴

선형 탐색만 가능

→ 이진 검색 시에는 차례대로 검색하는 방법밖에 없으므로 비효율적이기 때문에 선형 검색만 가능하다

 

단일 연결 리스트 검색 과정

1. hnode에서 검색을 시작함

2. node에서의 검색

검색 시간 복잡도(search time complexity) : O(n)

 

단일 연결 리스트 추가(insert)

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

 

단일 연결 리스트 추가 과정

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

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

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

추가 시간 복잡도(insert time complexity) : O(n)

 

단일 연결 리스트 제거(delete)

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

 

단일 연결 리스트 제거 과정

1. 제거할 원소를 찾음

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

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

제거 시간 복잡도(delete time complexity) : O(n)