C 언어에서 배열과 연결리스트에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

각 요소에 +1을 하는 경우 연결리스트가 배열보다 메모리를 적게 차지한다는 설명이 옳지 않다. 연결리스트는 노드마다 다음 노드를 가리키는 포인터를 추가로 저장하므로 같은 개수의 정수를 담으면 배열보다 메모리를 더 쓴다.
대신 연결리스트는 삽입·연결·재배치를 포인터 변경만으로 처리할 수 있어, 원소 이동이나 복사가 필요한 배열보다 유리하다.
두 집합의 합병은 앞 리스트의 마지막 노드를 뒤 리스트의 첫 노드에 연결하면 되지만 배열은 원소를 새 공간에 복사해야 하므로, 연결리스트 쪽이 시간 복잡도가 낮다.
{1,2,3,4}를 {4,1,2,3}으로 바꾸는 것은 마지막 노드를 떼어 앞에 붙이면 되므로, 모든 원소를 한 칸씩 밀어야 하는 배열보다 빠르다.
맨 앞에 0을 추가하는 것은 새 노드를 head 앞에 연결하면 끝나지만 배열은 기존 원소를 모두 뒤로 옮겨야 하므로 연결리스트가 빠르다.