연결 리스트(linked list)에 대한 설명으로 옳지 않은 것은? … | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 11년 1회차
연결 리스트(linked list)에 대한 설명으로 옳지 않은 것은? (단, 연결 리스트의 크기는 N이다)
1
다음(next) 원소의 장소나 주소를 저장하기 위한 기억공간이 추가로 필요하다.
2
자료가 연결된 순서대로 기억공간에 저장된다.
3
특정 자료를 검색하는데 걸리는 시간은 이다.4
삭제할 노드의 이전 노드 위치를 알 경우 삭제 시간은 이다.해설
연결 리스트의 노드는 기억공간의 임의 위치에 흩어져 저장되고 포인터로 순서를 나타내므로, 연결 순서대로 저장된다는 설명이 옳지 않다.
논리적 순서와 물리적 저장 순서가 일치하는 것은 배열(순차 리스트)의 특징이다.
- 각 노드는 다음 노드 주소를 담는 링크 필드가 필요하므로 추가 공간이 든다.
- 임의 접근이 불가능해 처음부터 차례로 따라가야 하므로 검색은 선형 시간이다.
- 이전 노드를 알면 링크 하나만 바꾸면 되므로 삭제는 상수 시간이다.
오류나 개정된 내용이 보이면 알려주세요