자료구조 14강 - 이중 연결 리스트

이중 연결 리스트

각 node가 다음(next, rlink-right) node를 가리키는 link와

이전(prev, llink-left) node를 가리키는 link를 동시에 가지고 있는 연결 리스트

 

이중 연결 리스트 추가(insert)

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

 

이중 연결 리스트 추가 과정

1. 데이터를 추가할 적절한 위치를 결정

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

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

이중 연결 리스트 추가 시간 복잡도(insert time complexity) : O(n)

 

이중 연결 리스트 제거(delete)

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

 

이중 연결 리스트 제거 과정

1. 제거할 원소를 찾음

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

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

이중 연결 리스트 제거 시간 복잡도(delete time complexity) : O(n)